數據結構(C++版)課后作業(yè)6-8章附答案

1、精選文本第6章圖課后習題講解1. 填空題（1）設無向圖G中頂點數為n,則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n（n-1）/2，0，n（n-1）【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。任何連通圖的連通分量只有一個，即是（）。【解答】其自身圖的存儲結構主要有兩種，分別是（）和（）?！窘獯稹苦徑泳仃嚕徑颖硪阎粋€有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（）?！窘獯稹壳蟮趈列的所有元素之和有向圖G用鄰接矩陣Ann存儲，其第i行的所有元素之和等于頂點泊勺（

2、）?！窘獯稹砍龆葓D的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數據結構是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數據結構是（）?！窘獯稹壳靶?，棧，層序，隊列（ 8） 如果一個有向圖不存在（），則該圖的全部頂點可以排列成一個拓撲序列?！窘獯稹炕芈?. 選擇題n個頂點的強連通圖至少有（）條邊，其形狀是（）。AnBn+1Cn-1Dnx-n）E無回路F有回路G環(huán)狀H樹狀【解答】A，G含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（）。A1Bn/2Cn-1Dn【解答】C【分析】若超過n-1,則路徑中必存在重復的頂點。（4）最小生成樹指的是（）。A由連通網所得到的邊數最少的生成樹B由

3、連通網所得到的頂點數相對較少的生成樹C連通網中所有生成樹中權值之和為最小的生成樹D連通網的極小連通子圖【解答】C（5）下面關于工程計劃的AOE網的敘述中，不正確的是（）A關鍵活動不按期完成就會影響整個工程的完成時間B任何一個關鍵活動提前完成，那么整個工程將會提前完成C所有的關鍵活動都提前完成，那么整個工程將會提前完成D某些關鍵活動若提前完成，那么整個工程將會提前完【解答】B【分析】AOE網中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關鍵路徑上的關鍵活動。3. 判斷題(1)用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數有關，而與圖的邊數無

4、關?！窘獯稹繉?。鄰接矩陣的空間復雜度為O(n2),與邊的個數無關。(2)圖G的生成樹是該圖的一個極小連通子圖【解答】錯。必須包含全部頂點。(3)在一個有向圖的拓撲序列中，若頂點胞頂點b之前，則圖中必有一條弧?！窘獯稹垮e。只能說明從頂點a到頂點b有一條路徑。7 .已知一個連通圖如圖所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點v1出發(fā)對該圖進行遍歷,分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列?！窘獯?鄰接矩鞫表示如下工0101011 01L10010010110011011L00J00L00、一一-J深度優(yōu)先遍歷序列為；vlv2v3V5v4V6廣度優(yōu)先遍歷序列為:vlv2v4v6v

5、3v5鄰接表表示如下；1234568 .圖所示是一個無向帶權圖，請分別按Prim算法和Kruskal算法求最小生成樹。自己做第7章查找技術(3)在各種查找方法中，平均查找長度與結點個數無關的查找方法是()?！窘獯稹可⒘胁檎摇痉治觥可⒘斜淼钠骄檎议L度是裝填因子的函數，而不是記錄個數n的函數。2 .選擇題(1)設散列表表長m=14,散列函數H(k)=kmod11。表中已有15、38、61、84四個元素，如果用線性探側法處理沖突，則元素49的存儲地址是()?！窘獯稹緼【分析】元素15、38、61、84分別存儲在4、5、6、7單元，而元素49的散列地址為5,發(fā)生沖突，向后探測好單元，其存儲地址為8。

6、3 .判斷題(1)二叉排序樹的充要條件是任一結點的值均大于其左孩子的值，小于其右孩子的值。【解答】錯。分析二叉排序樹的定義，是左子樹上的所有結點的值都小于根結點的值，右子樹上的所有結精選文本點的值都大于根結點的值。精選文本二叉排序樹的查找和折半查找的時間性能相同?！窘獯稹垮e。二叉排序樹的查找性能在最好情況和折半查找相同計算題（1）將數列（24,15,38,27,121,76,130）的各元素依次插入一棵初始為空的二叉排序樹中，請畫出最后的結果并求等概率情況下查找成功的平均查找長度。I解牌】二叉排序樹如圖7-11所示.其平均查找長度=1十2x2+3*2+4乂2=19/7第8章排序技術課后習題講解

7、1 .填空題（1）排序的主要目的是為了以后對已排序的數據元素進行（）?！窘獯稹坎檎摇痉治觥繉σ雅判虻挠涗浶蛄羞M行查找通常能提高查找效率。對一組記錄（54,38,96,23,15,72,60,45,83進行直接插入排序，當把第7個記錄60畝入到有序表時，為尋找插入位置需比較（）次。【解答】3【分析】當把第7個記錄60雷人到有序表時，該有序表中有2個記錄大于60。對一組記錄（54,38,96,23,15,72,60,45,8）進行快速排序，在遞歸調用中使用的棧所能達到的最大深3度為（）?！窘獯稹?2 .選擇題（1）下述排序方法中，比較次數與待排序記錄的初始狀態(tài)無關的是（）。A插入排序和快速排序B歸

8、并排序和快速排序C選擇排序和U3并排序D插入排序和歸并排序【解答】C【分析】選擇排序在最好、最壞、平均情況下的時間性能均為O（n2）,歸并排序在最好、最壞、平均情況下的時間性能均為O（nlog2n）。（2） 對初始狀態(tài)為遞增有序的序列進行排序，最省時間的是（），最費時間的是（）。已知待排序序列中每個元素距其最終位置不遠，則采用（）方法最節(jié)省時間。A堆排序B插入排序C快速排序D直接選擇排序【解答】B，C，B【分析】待排序序列中每個元素距其最終位置不遠意味著該序列基本有序。（3） 當待排序序列基本有序或個數較小的情況下，最佳的內部排序方法是（），就平均時間而言，（）最佳。A直接插入排序B起泡排序C

9、簡單選擇排序D快速排序【解答】A,D（4）設有5000f元素，希望用最快的速度挑選出前10個最大的，采用（）方法最好。A快速排序B堆排序C希爾排序D歸并排序【解答】B【分析】堆排序不必將整個序列排序即可確定前若干個最大（或最?。┰?。（5）設要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關鍵碼按升序排列，則（）是起泡排序一趟掃描的結果，（）是增量為4的希爾排序一趟掃描的結果，（）二路歸并排序一趟掃描的結果，（）是以第一個元素為軸值的快速排序一趟掃描的結果.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，

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

11、排序【解答】C，A，D，B，B，D，F(xiàn)（7） 快速排序在（）情況下最不利于發(fā)揮其長處。A待排序的數據量太大B待排序的數據中含有多個相同值C待排序的數據已基本有序D待排序的數據數量為奇數【解答】C【分析】快速排序等改進的排序方法均適用于待排序數據量較大的情況，各種排序方法對待排序的數據中是否含有多個相同值，待排序的數據數量為奇數或偶數都沒有影響。(8)()方法是從未排序序列中挑選元素，并將其放入已排序序列的一端。A歸并排序B插入排序C快速排序D選擇排序【解答】D(9)對數列(25,84,21,47,15,27,68,35,20進行排序，元素序列的變化情況如下：25,84,21,47,15,27,

12、68,35,2020,15,21,25,47,27,68,35,843)15,20,21,25,35,27,47,68,844)15,20,21,25,27,35,47,68,84則采用的排序方法是()。計算題：已知數據序列為(12,5,9,20,6,31,24),對該數據序列進行排序，寫出插入排序、起泡排序、快速排序、簡單選擇排序、二路歸并排序每趟的結果。插入拄序：初始腱值序列12 59第一趟結果5129第二超結果59第三趟結果59第四趟結果56第五趟結果56第六趟結果C56206312420831241212063124122063124g1220312491220313249122024

13、31起泡排序；初始稗值序列125第一趟結果59第二趟結果59第三垣結果56第四趟結果5692063124126202431612202431912202431912202431快速拄序工初始鍵值序列125第一場結果65第二趟結果56第三趟結果56第四趟結果56?2063124912203124E912203124912202431912202431精選文本簡單選擇排序；初始解值序列L125第一遺結果512第二趟結果58第三趟結果58第四垣結果58第五埴結果58第六迨結果58。2063124192083124;920123124J；920123124；9122U3124;912203124II912202431;I二路歸并拄序,初始錯值序列12592063124第一超結果512