數(shù)據(jù)結(jié)構(gòu)(C++版)課后作業(yè)6-8章附答案

1、WORD格式第6章圖課后習(xí)題講解1. 填空題專業(yè)資料整理WORD格式設(shè)無向圖 G中頂點數(shù)為n ，那么圖 G至少有條邊，至多有條邊；假設(shè)G為有向圖，那么至少有條專業(yè)資料整理WORD格式邊，至多有條邊。專業(yè)資料整理WORD格式【解答】 0，n(n-1)/2 ，0 ，n(n-1) 【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數(shù)到達(dá)最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。 任何連通圖的連通分量只有一個，即是?！窘獯稹科渥陨?圖的存儲構(gòu)造主要有兩種，分別是和?！窘獯稹苦徑泳仃嚕徑颖韺I(yè)資料整理WORD格式 一個有向圖的鄰接矩陣表示，計算第j 個頂點的入度的方法是?！窘獯稹壳?/p>

2、第j列的所有元素之專業(yè)資料整理WORD格式和專業(yè)資料整理WORD格式有向圖 G用鄰接矩陣 Ann存儲，其第 i行的所有元素之和等于頂點i的?！窘獯稹砍龆葘I(yè)資料整理WORD格式 圖的深度優(yōu)先遍歷類似于樹的遍歷，它所用到的數(shù)據(jù)構(gòu)造是遍歷，它所用到的數(shù)據(jù)構(gòu)造是。；圖的廣度優(yōu)先遍歷類似于樹的專業(yè)資料整理WORD格式【解答】前序，棧，層序，隊列專業(yè)資料整理WORD格式（ 8 如果一個有向圖不存在，那么該圖的全部頂點可以排列成一個拓?fù)湫蛄??！窘獯稹炕芈?. 選擇題專業(yè)資料整理WORD格式 n個頂點的強連通圖至少有條邊，其形狀是路 G 環(huán)狀 H 樹狀 【解答】 A，G。A n B n+1 C n-1 D

3、n×(n-1) E無回路F 有回專業(yè)資料整理WORD格式含n【解答】個頂點的連通圖中的任意一條簡單路徑 ，其長度不可能超過C 【分析】假設(shè)超過n-1 ，那么路徑中必存在重復(fù)的頂點。A 1 B n/2 C n-1 D n專業(yè)資料整理WORD格式4最小生成樹指的是 。 A 由連通網(wǎng)所得到的邊數(shù)最少的生成樹對較少的生成樹C 連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹D【解答】 CB 由連通網(wǎng)所得到的頂點數(shù)相連通網(wǎng)的極小連通子圖專業(yè)資料整理WORD格式5下面關(guān)于工程方案的AOE網(wǎng)的表達(dá)中，不正確的選項是專業(yè)資料整理WORD格式A 關(guān)鍵活動不按期完成就會影響整個工程的完成時間B 任何一個關(guān)鍵活

4、動提前完成，那么整個工程將會專業(yè)資料整理WORD格式提前完成C 所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成D 某些關(guān)鍵活動假設(shè)提前完成，那么專業(yè)資料整理WORD格式整個工程將會提前完【解答】 B 【分析】 AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個關(guān)鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關(guān)鍵路徑上的關(guān)鍵活動。3. 判斷題（ 1用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)?！窘獯稹繉?。鄰接矩陣的空間復(fù)雜度為(n2) ，與邊的個數(shù)無關(guān)。2 圖 G的生成樹是該圖的一個極小連通子圖【解答】錯。必須包含全部頂點。（ 3在一個有向圖的拓?fù)湫蛄兄校?/p>

5、假設(shè)頂點 a在頂點 b之前，那么圖中必有一條弧。【解答】錯。只能說明從頂點 a到頂點 b有一條路徑。7一個連通圖如下列圖，試給出圖的鄰接矩陣和鄰接表存儲示意圖， 假設(shè)從頂點 v1出發(fā)對該圖進(jìn)展遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。專業(yè)資料整理WORD格式8圖所示是一個無向帶權(quán)圖，請分別按Prim算法和 Kruskal 算法求最小生成樹。自己做。第7章查找技術(shù)專業(yè)資料整理WORD格式3 在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找方法是?！窘獯稹可⒘胁檎?【分析】散列表的平均查找長度是裝填因子的函數(shù)，而不是記錄個數(shù)n 的函數(shù)。專業(yè)資料整理WORD格式2. 選擇題專業(yè)資料

6、整理WORD格式1 設(shè)散列表表長 m=14 ，散列函數(shù) H(k)=k mod 11。表中已有 15 、38 、 61、 84 四個元素，如果用線性探側(cè)法處理沖突，那么元素49 的存儲地址是?！窘獯稹?A 【分析】元素 15 、38 、 61、 84 分別存儲在5、6、7 單元，而元素 49的散列地址為 5，發(fā)生沖突，向后探測3個單元，其存儲地址為8 。4、專業(yè)資料整理WORD格式3. 判斷題 二叉排序樹的充要條件是任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值。【解答】錯。分析二叉排序樹的定義，是左子樹上的所有結(jié)點的值都小于根結(jié)點的值，右子樹上的所有結(jié)專業(yè)資料整理WORD格式點的值都大于根結(jié)

7、點的值。 二叉排序樹的查找和折半查找的時間性能一樣?！窘獯稹垮e。二叉排序樹的查找性能在最好情況和折半查找一樣。計算題（ 1將數(shù)列 24 ，15 ，38 ，27 ， 121 ，76 ，130 的各元素依次插入一棵初始為空的二叉排序樹中，請畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。第 8 章排序技術(shù)課后習(xí)題講解1. 填空題 排序的主要目的是為了以后對已排序的數(shù)據(jù)元素進(jìn)展?！窘獯稹坎檎摇痉治觥繉σ雅判虻挠涗浶蛄羞M(jìn)展查找通常能提高查找效率。專業(yè)資料整理WORD格式對一組記錄 54, 38, 96, 23, 15, 72, 60, 45, 83時，為尋找插入位置需比較次。【解答】 3有2個記

8、錄大于 60 。進(jìn)展直接插入排序，當(dāng)把第7個記錄 60 插入到有序表【分析】當(dāng)把第7個記錄 60插入到有序表時，該有序表中專業(yè)資料整理WORD格式對一組記錄 54, 38, 96, 23, 15, 72, 60, 45, 83大深度為?！窘獯稹?3進(jìn)展快速排序，在遞歸調(diào)用中使用的棧所能到達(dá)的最專業(yè)資料整理WORD格式2. 選擇題 下述排序方法中，比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)的是序和快速排序C選擇排序和歸并排序D插入排序和歸并排序【解答】 C 【分析】選擇排序在最好、最壞、平均情況下的時間性能均為平均情況下的時間性能均為O(nlog2n) 。A插入排序和快速排序B歸并排O(n2) ，歸并排

9、序在最好、最壞、專業(yè)資料整理WORD格式(2)對初始狀態(tài)為遞增有序的序列進(jìn)展排序，最省時間的是，最費時間的是。待排序序列中每個元素距其最終位置不遠(yuǎn)，那么采用方法最節(jié)省時間。A 堆排序B插入排序C快速排序D 直接選擇排序【解答】 B， C， B 【分析】待排序序列中每個元素距其最終位置不遠(yuǎn)意味著該序列根本有序。專業(yè)資料整理WORD格式(3)當(dāng)待排序序列根本有序或個數(shù)較小的情況下，最正確的內(nèi)部排序方法是最正確。 A 直接插入排序B 起泡排序C簡單項選擇擇排序D快速排序【解答】，就平均時間而言，A， D專業(yè)資料整理WORD格式(4) 設(shè)有 5000 個元素，希望用最快的速度挑選出前 10 個最大的，

10、采用方法最好。 A快速排序 B堆排序 C希爾排序 D 歸并排序【解答】 B 【分析】堆排序不必將整個序列排序即可確定前假設(shè)干個最大或最小元素。(5) 設(shè)要將序列 Q， H，C，Y，P，A， M， S， R， D，F(xiàn)， X中的關(guān)鍵碼按升序排列，那么是起泡排序一趟掃描的結(jié)果， 是增量為 4的希爾排序一趟掃描的結(jié)果， 二路歸并排序一趟掃描的結(jié)果， 是以第一個元素為軸值的快速排序一趟掃描的結(jié)果. A F，H，C，D，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y C A，D，C，R， F，Q，M，S，Y，P，H，X D H，C，Q，P，A，M， S，R， D， F，

11、X， Y E H， Q， C， Y， A，P，M，S，D，R，F(xiàn)， X【解答】 D，B， E， A，C(6) 排序的方法有很多種， 法從未排序序列中依次取出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確位置上。 法從未排序序列中挑選元素，并將其依次放入已排序序列的一端。交換排序是對序列中元素進(jìn)展一系列比較，當(dāng)被比較的兩元素為逆序時，進(jìn)展交換；和是基于這類方法的兩種排序方法，而是比效率更高的方法；法是基于選擇排序的一種方法，是完全二叉樹構(gòu)造的一個重要應(yīng)用。 A 選擇排序 B 快速排序 C 插入排序 D 起泡排序 E 歸并排序【解答】 C，A， D，B， B，D， F專業(yè)資料整理WOR

12、D格式(7) 快速排序在情況下最不利于發(fā)揮其長處。 A 待排序的數(shù)據(jù)量太大一樣值 C 待排序的數(shù)據(jù)已根本有序 D 待排序的數(shù)據(jù)數(shù)量為奇數(shù)B 待排序的數(shù)據(jù)中含有多個專業(yè)資料整理WORD格式【解答】 C 【分析】快速排序等改進(jìn)的排序方法均適用于待排序數(shù)據(jù)量較大的情況，各種排序方法對待排序的數(shù)據(jù)中是否含有多個一樣值，待排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒有影響。專業(yè)資料整理WORD格式(8)方法是從未排序序列中挑選元素，并將其放入已排序序列的一端。A 歸并排序B 插入排序C快速排序D 選擇排序【解答】 D9 對數(shù)列 25, 84, 21,47, 15, 27, 68, 35, 20 進(jìn)展排序，元素序列的變化情況如下： 25, 84, 21,47, 15, 27, 68, 35,20 20, 15, 21, 25, 47, 27, 68, 35, 84 15, 20, 21, 25, 35, 27, 47, 68, 84 15,20, 21, 25, 27, 35,47, 68, 84那么采用的排序方法是。計算題：數(shù)據(jù)序列為(12 ， 5，9 ，20 ，6，31 ， 24) ，對該數(shù)據(jù)序列進(jìn)展排序，寫出插入排序、起泡排序、快速排