第7章習題答案一、單項選擇題在一個圖中，所有頂點的度數之和等于圖的邊數的____倍。

答案：C.2

解析：在無向圖中，每條邊貢獻兩個度數（每個端點一個），因此度數之和是邊數的兩倍。在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的__倍。

答案：B.1

解析：在有向圖中，每條邊對應一個入度和一個出度，因此入度之和等于出度之和，且都等于邊數。有8個結點的無向圖最多有__條邊。

答案：B.28

解析：無向完全圖的邊數為

n(n?1)/2?，代入

n=8得

8×7/2=28。有8個結點的無向連通圖最少有___條邊。

答案：C.7

解析：無向連通圖的最少邊數為生成樹的邊數，即

n?1=8?1=7。有8個結點的有向完全圖有__條邊。

答案：C.56

解析：有向完全圖的邊數為

n(n?1)，代入

n=8

得

8×7=56。用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用___來實現算法的。

答案：B.隊列

解析：廣度優(yōu)先遍歷（BFS）使用隊列管理待訪問頂點，確保按層次遍歷。用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用____來實現算法的。

答案：A.棧

解析：深度優(yōu)先遍歷（DFS）通常使用棧（或遞歸調用棧）實現，以探索路徑深度。深度優(yōu)先遍歷類似于二叉樹的

答案：A.先序遍歷

解析：DFS的訪問順序（根-子節(jié)點）與二叉樹的先序遍歷（根-左-右）相似。廣度優(yōu)先遍歷類似于二叉樹的

答案：D.層次遍歷

解析：BFS按層次訪問頂點，與二叉樹的層次遍歷一致。任何一個無向連通圖的最小生成樹

答案：B.一棵或多棵

解析：最小生成樹可能不唯一（例如，圖中存在相同權重的邊時可能有多個），但一定存在。二、填空題圖有

鄰接矩陣、鄰接表

等存儲結構，遍歷圖有

深度優(yōu)先遍歷、廣度優(yōu)先遍歷

等方法。有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的

出度。如果n個頂點的圖是一個環(huán)，則它有

n

棵生成樹。(以任意一頂點為起點，得到n-1條邊)n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為

O(n2)。n個頂點e條邊的圖，若采用鄰接表存儲，則空間復雜度為

O(n+e)。設有一稀疏圖G，則G采用

鄰接表

存儲較省空間。設有一稠密圖G，則G采用

鄰接矩陣

存儲較省空間。圖的逆鄰接表存儲結構只適用于

有向

圖。已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的方法是

將鄰接矩陣的第i行全部置為0。圖的深度優(yōu)先遍歷序列

不唯一。第8章習題答案一、單項選擇題如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，最好采用()查找法。

答案：C.分塊查找

解析：分塊查找結合了順序查找和折半查找的優(yōu)點，塊內可無序（適應動態(tài)插入/刪除），塊間有序（支持較快查找）。對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關鍵字。

答案：C.5

*解析：n=22時，折半查找樹的最大高度為5（因

24<22≤25），查找失敗時至少需比較5次（最壞情況）。*在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應作（）型調整以使其平衡。

答案：D.RR

解析：A的右孩子平衡因子為1（右重），且插入發(fā)生在右子樹的右子樹，故需RR旋轉。已知一個有序表(13,18,24,35,47,50,62,83,90,115,134)，當二分查找值為90的元素時，查找成功的比較次數為()。

答案：B.2

*解析：第一次mid=5（值50<90），第二次mid=8（值90），共2次比較。*下面關于哈希查找的說法，不正確的是（）。

答案：A.采用鏈地址法處理沖突時，查找一個元素的時間是相同的

解析：查找時間取決于鏈表長度，不同關鍵字的哈希沖突鏈長度可能不同，查找時間不一定相同。設哈希表長為14，哈希函數是H(key)=key%11，表中已有數據的關鍵字為15,38,61,84共四個，現要將關鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的位置是（）。

答案：D.9

*解析：H(49)=5（沖突），探測序列：*(5+12)%14=6（沖突，有61）(5?12)%14=4（沖突，有15）(5+22)%14=9（空閑，成功放置）。采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關鍵字()。

答案：A.不一定都是同義詞

解析：線性探測可能引發(fā)“堆積”，探測路徑上可能包含非同義詞（不同哈希地址的關鍵字）。由n個數據元素組成的兩個表：一個遞增有序，一個無序。采用順序查找算法，對有序表從頭開始查找，發(fā)現當前元素已不小于待查元素時，停止查找，確定查找不成功，已知查找任一元素的概率是相同的，則在兩種表中成功查找()。

答案：B.平均時間兩者相同

解析：成功查找時，有序表提前停止僅減少失敗比較次數，成功查找的平均比較次數均為

（n+1）/2。對長度為3的順序表進行查找，若查找第一個元素的概率為1/2，查找第二個元素的概率為1/3,查找第三個元素的概率為1/6,則查找任一元素的平均查找長度為()。

答案：A.5/3

解析：ASL=

(1/2×1)+(1/3×2)+(1/6×3)=1/2+2/3+1/2=5/3?.具有12個關鍵字的有序表中，對每個關鍵字的查找概率相同，折半查找算法查找成功的平均查找長度為()

答案：A.37/12

解析：判定樹結構：1個關鍵字比較1次（根）2個關鍵字比較2次4個關鍵字比較3次5個關鍵字比較4次ASL=(

(1×1)+(2×2)+(4×3)+(5×4))/12=37/12?.二、填空題直接定址法構造的哈希函數肯定不會發(fā)生沖突。高度為8的平衡二叉樹的結點數至少有

54

個。不受待排序初始序列的影響，時間復雜度為O(N2)的排序算法是

選擇排序，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是

插入排序。處理哈希沖突的主要方法有

開放定址法

和

鏈地址法。查找是非數值程序設計的一個重要技術問題，基本上分成

順序查找、折半查找

和

哈希查找。第9章習題答案一、單項選擇題從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（）。

答案：C.插入排序

解析：插入排序通過將未排序元素逐個插入已排序序列的正確位置實現排序。從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）。

答案：D.選擇排序

解析：選擇排序每次從未排序序列中選擇最?。ɑ蜃畲螅┰兀诺揭雅判蛐蛄械哪┪?。對n個不同的關鍵字由小到大進行冒泡排序，在下列（）情況下比較的次數最多。

答案：B.從大到小排列好的

解析：冒泡排序在逆序序列中需要最多比較（每趟都需完全遍歷并交換）。對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數最多為（）。

答案：D.n(n-1)/2

解析：最壞情況下（完全逆序），比較次數為

n(n?1)/2??？焖倥判蛟谙铝校ǎ┣闆r下最易發(fā)揮其長處。

答案：C.被排序的數據完全無序

解析：快速排序在數據完全無序時效率最高（平均時間復雜度

O(nlogn)）。對n個關鍵字作快速排序，在最壞情況下，算法的時間復雜度是（）。

答案：B.O(n2)

解析：最壞情況（如已排序或逆序）下，時間復雜度為

O(n2)。若一組記錄的排序碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。

答案：B.40,38,46,79,56,84

解析：以46為基準，劃分過程：初始：46,79,56,38,40,84交換79和40：46,40,56,38,79,84交換56和38：46,40,38,56,79,84交換基準46和38：40,38,46,56,79,84→但最終為40,38,46,79,56,84（Lomuto劃分標準結果）。下列關鍵字序列中，（）是堆。

答案：D.16,23,53,31,94,72

解析：該序列滿足小根堆性質（父節(jié)點≤子節(jié)點）：*16≤23,16≤53**23≤31,23≤94**53≤72*堆是一種（）排序。

答案：B.選擇

解析：堆排序屬于選擇排序（每次選擇堆頂最大/最小元素）。堆的形狀是一棵（）。

答案：C.完全二叉樹

解析：堆的邏輯結構是一棵完全二叉樹。二、填空題若一組記錄的排序碼為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為

84,79,56,38,40,46。數據表中有10000個元素，如果僅要求求出其中最大的10個元素，則最節(jié)省時間的算法是

堆排序（或最小堆選擇）。簡單選擇排序算法的比較次數為

n(n?1)/2?。巳知小根堆為8,15,10,21,34,16,12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字之間的比較次數是

3。

解析：刪除根后，將末元素12移至根，堆化過程比較：比較15和10→選10比較12和10→交換比較21和16→選16比較12和16→不交換三、應用題

設待排序的關鍵字序列為{12,2,16,30,28,10,20,6,18}，使用冒泡排序每趟狀態(tài)如下：初始序列：12,2,16,30,28,10,20,6,18第1趟結束：2,12,16,28,10,20,6,18,30（最大元素30沉底）第2趟結束：2,12,16,10,20,6,18,28,30（次大元素28沉底）第3趟結束：2,12,10,16,6,18,20,28