數據結構(c版)王紅梅版課后答案khdaw(已修改)

　

【正文】 課后答案網第 1 章 緒 論課后習題講解1. 填空⑴（ ）是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。【解答】數據元素⑵（ ）是數據的最小單位，（ ）是討論數據結構時涉及的最小數據單位。【解答】數據項，數據元素【分析】數據結構指的是數據元素以及數據元素之間的關系。⑶ 從邏輯關系上講，數據結構主要分為（ ）、（ ）、（ ）和（ ）。【解答】集合，線性結構，樹結構，圖結構⑷ 數據的存儲結構主要有（ ）和（ ）兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：（ ） 和（ ）。【解答】順序存儲結構，鏈接存儲結構，數據元素，數據元素之間的關系⑸ 算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言。【解答】自然語言，程序設計語言，流程圖，偽代碼，偽代碼⑺ 在一般情況下，一個算法的時間復雜度是（ ）的函數。【解答】問題規模⑻ 設待處理問題的規模為 n，若一個算法的時間復雜度為一個常數，則表示成數量級的形式為（ ），若 為 n*log25n，則表示成數量級的形式為（ ）。【解答】Ο(1)，Ο(nlog2n)【分析】用大 O 記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數去掉。2. 選擇題⑴ 順序存儲結構中數據元素之間的邏輯關系是由（ ）表示的，鏈接存儲結構中的數據元素之間的邏輯關 系是由（ ）表示的。A 線性結構 B 非線性結構 C 存儲位置 D 指針【解答】C，D【分析】順序存儲結構就是用一維數組存儲數據結構中的數據元素，其邏輯關系由存儲位置（即元素在數 組中的下標）表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中 的指針表示。⑵ 假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不 能相互繼承。則表示該遺產繼承關系的最合適的數據結構應該是（ ）。A 樹 B 圖 C 線性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數據元素，根據題意畫出邏輯結構圖。⑶ 算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數據處理【解答】A【分析】計算機程序是對算法的具體實現；簡單地說，算法是解決問題的方法；數據處理是通過算法完成 的。所以，只有 A 是算法的準確定義。⑷ 下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法應具備的特性。⑸ 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數據結構的合理性 B 研究算法中輸入和輸出的關系 C 分析算法的效率以求改進 D 分析算法的易讀性和文檔性 E 空間性能和時間性能 F 正確性和簡明性G 可讀性和文檔性 H 數據復雜性和程序復雜性【解答】C，E3. 判斷題⑴ 算法的時間復雜度都要通過算法中的基本語句的執行次數來確定。【解答】錯。時間復雜度要通過算法中基本語句執行次數的數量級來確定。⑵ 每種數據結構都具備三個基本操作：插入、刪除和查找。【解答】錯。如數組就沒有插入和刪除操作。此題注意是每種數據結構。⑶ 所謂數據的邏輯結構指的是數據之間的邏輯關系。【解答】錯。是數據之間的邏輯關系的整體。⑷ 邏輯結構與數據元素本身的內容和形式無關。【解答】對。因此邏輯結構是數據組織的主要方面。⑸ 基于某種邏輯結構之上的基本操作，其實現是唯一的。【解答】錯。基本操作的實現是基于某種存儲結構設計的，因而不是唯一的。4. 分析以下各程序段，并用大 O 記號表示其執行時間。【解答】⑴ 基本語句是 k=k+10*i，共執行了 n2 次，所以 T(n)=O(n)。⑵ 基本語句是 k=k+10*i，共執行了 n 次，所以 T(n)=O(n)。⑶ 分析條件語句，每循環一次，i+j 整體加 1，共循環 n 次，所以 T(n)=O(n)。⑷ 設循環體共執行 T(n)次，每循環一次，循環變量 y 加 1，最終 T(n)=y，即：(T(n)+1)2≤n，所以 T(n)=O(n 1/2)。⑸ x++是基本語句，所以 5．設有數據結構（D，R），其中 D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結構圖并指出屬于何種結構。【解答】其邏輯結構圖如圖 13 所示，它是一種圖結構。6. 為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件。【解答】整數的抽象數據類型定義如下：ADT integerData整數 a：可以是正整數(1, 2, 3, … )、負整數(1, 2, 3, …)和零OperationConstructor 前置條件：整數 a 不存在 輸入：一個整數 b 功能：構造一個與輸入值相同的整數輸出：無后置條件：整數 a 具有輸入的值Set 前置條件：存在一個整數 a 輸入：一個整數 b功能：修改整數 a 的值，使之與輸入的整數值相同 輸出：無后置條件：整數 a 的值發生改變Add 前置條件：存在一個整數 a 輸入：一個整數 b功能：將整數 a 與輸入的整數 b 相加 輸出：相加后的結果后置條件：整數 a 的值發生改變Sub 前置條件：存在一個整數 a 輸入：一個整數 b功能：將整數 a 與輸入的整數 b 相減 輸出：相減的結果后置條件：整數 a 的值發生改變Multi 前置條件：存在一個整數 a 輸入：一個整數 b功能：將整數 a 與輸入的整數 b 相乘 輸出：相乘的結果后置條件：整數 a 的值發生改變Div 前置條件：存在一個整數 a 輸入：一個整數 b功能：將整數 a 與輸入的整數 b 相除輸出：若整數 b 為零，則拋出除零異常，否則輸出相除的結果 后置條件：整數 a 的值發生改變Mod 前置條件：存在一個整數 a 輸入：一個整數 b功能：求當前整數與輸入整數的模，即正的余數輸出：若整數 b 為零，則拋出除零異常，否則輸出取模的結果 后置條件：整數 a 的值發生改變Equal 前置條件：存在一個整數 a 輸入：一個整數 b功能：判斷整數 a 與輸入的整數 b 是否相等 輸出：若相等返回 1，否則返回 0后置條件：整數 a 的值不發生改變endADT7. 求多項式 A(x)的算法可根據下列兩個公式之一來設計：⑴ A(x)=anxn+an1xn1+…+a1x+a0⑵ A(x)=(…(anx+an1)x+…+a1)x)+a0根據算法的時間復雜度分析比較這兩種算法的優劣。【解答】第二種算法的時間性能要好些。第一種算法需執行大量的乘法運算，而第二種算法進行了優化， 減少了不必要的乘法運算。8. 算法設計（要求：算法用偽代碼和 C++描述，并分析最壞情況下的時間復雜度）⑴ 對一個整型數組 A[n]設計一個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。下面是簡單選擇排序算法的 C++描述。分析算法，有兩層嵌套的 for 循環，所以， 。⑵ 找出整型數組 A[n]中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：算法的 C++描述如下：分析算法，只有一層循環，共執行 n2 次，所以，T(n)=O(n)。學習自測及答案1．順序存儲結構的特點是（ ），鏈接存儲結構的特點是（ ）。【解答】用元素在存儲器中的相對位置來表示數據元素之間的邏輯關系，用指示元素存儲地址的指針表示 數據元素之間的邏輯關系。2. 算法在發生非法操作時可以作出處理的特性稱為（ ）。【解答】健壯性3. 常見的算法時間復雜度用大Ｏ記號表示為：常數階( )、對數階( )、線性階 ( )、平方階( )和指數階( )。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．將下列函數按它們在 n 時的無窮大階數，從小到大排列。n, nn3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, nn3+7n5, 2n/2, (3/2)n, n!5．試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。【解答】數據結構是指相互之間存在一定關系的數據元素的集合。而抽象數據類型是指一個數據結構以及 定義在該結構上的一組操作。程序設計語言中的數據類型是一個值的集合和定義在這個值集上一組操作的 總稱。抽象數據類型可以看成是對數據類型的一種抽象。6. 對下列用二元組表示的數據結構,試分別畫出對應的邏輯結構圖，并指出屬于何種結構。⑴ A=(D，R)， 其中 D={a1, a2, a3, a4}，R={ }⑵ B=(D，R)， 其中 D={a, b, c, d, e, f}，R={,}⑶ C=( D，R)，其中 D={a，b，c，d，e，f}，R={,,}⑷ D=(D，R)， 其中 D={1, 2, 3, 4, 5, 6}，R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}【解答】⑴ 屬于集合，其邏輯結構圖如圖 14(a)所示；⑵ 屬于線性結構，其邏輯結構圖如圖 14(b)所示；⑶ 屬于樹結構，其邏輯結構圖如圖 14(c)所示；⑷ 屬于圖結構，其邏輯結構圖如圖 14(d)所示。7. 求下列算法的時間復雜度。count=0。 x=1。 while (x { x*=2。 count++。}return count。【解答】Ｏ(log2n)第 2 章 線性表課后習題講解1. 填空⑴ 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數與（ ） 和（ ）有關。【解答】表長的一半，表長，該元素在表中的位置⑵ 順序表中第一個元素的存儲地址是 100，每個元素的長度為 2，則第 5 個元素的存儲地址是（ ）。【解答】108【分析】第 5 個元素的存儲地址=第 1 個元素的存儲地址＋(5－1)2=108⑶ 設單鏈表中指針 p 指向結點 A，若要刪除 A 的后繼結點（假設 A 存在后繼結點），則需修改指針的操 作為（ ）。【解答】pnext=(pnext)next⑷ 單鏈表中設置頭結點的作用是（ ）。【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。⑸ 非空的單循環鏈表由頭指針 head 指示，則其尾結點（由指針 p 所指）滿足（ ）。【解答】pnext=head【分析】如圖 28 所示。⑹ 在由尾指針 rear 指示的單循環鏈表中，在表尾插入一個結點 s 的操作序列是（ ）；刪除開始結點的操作序列為（ ）。【解答】snext =rearnext。 rearnext =s。 rear =s。q=rearnextnext。 rearnextnext=qnext。 delete q。【分析】操作示意圖如圖 29 所示：⑺ 一個具有 n 個結點的單鏈表，在指針 p 所指結點后插入一個新結點的時間復雜度為（ ）；在給定值為x 的結點后插入一個新結點的時間復雜度為（ ）。【解答】Ο(1)，Ο(n)【分析】在 p 所指結點后插入一個新結點只需修改指針，所以時間復雜度為 Ο(1)；而在給定值為 x 的結點 后插入一個新結點需要先查找值為 x 的結點，所以時間復雜度為 Ο(n)。⑻ 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環鏈表，循環雙鏈表，雙鏈表2. 選擇題⑴ 線性表的順序存儲結構是一種（ ）的存儲結構，線性表的鏈接存儲結構是一種（ ）的存儲結構。A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】參見 。⑵ 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續的 B 部分地址必須是連續的C 一定是不連續的 D 連續與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也 可以不連續，甚至可以零散分布在內存中任意位置。⑶ 單循環鏈表的主要優點是（ ）。A 不再需要頭指針了B 從表中任一結點出發都能掃描到整個鏈表；C 已知某個結點的位置后，能夠容易找到它的直接前趨；D 在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】B⑷ 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不