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

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

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

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

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

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

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

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

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

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

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） 排序的方法有很多種，（）法從未排序序列中依次取出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確位置上。（）法從未排序序列中挑選元素，并將其依次放入已排序序列的一端。交換排序是對序列中元素進(jìn)行一系列比較，當(dāng)被比較的兩元素為逆序時(shí)，進(jìn)行交換；（）和（）是基于這類方法的兩種排序方法，而（）是比（）效率更高的方法；（）法是基于選擇排序的一種方法，是完全二叉樹結(jié)構(gòu)的一個(gè)重要應(yīng)用。A選擇排序B快速排序C插入排序D起泡排序E歸并

11、排序【解答】C，A，D，B，B，D，F(xiàn)（7） 快速排序在（）情況下最不利于發(fā)揮其長處。A待排序的數(shù)據(jù)量太大B待排序的數(shù)據(jù)中含有多個(gè)相同值C待排序的數(shù)據(jù)已基本有序D待排序的數(shù)據(jù)數(shù)量為奇數(shù)【解答】C【分析】快速排序等改進(jìn)的排序方法均適用于待排序數(shù)據(jù)量較大的情況，各種排序方法對待排序的數(shù)據(jù)中是否含有多個(gè)相同值，待排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒有影響。(8)()方法是從未排序序列中挑選元素，并將其放入已排序序列的一端。A歸并排序B插入排序C快速排序D選擇排序【解答】D(9)對數(shù)列(25,84,21,47,15,27,68,35,20進(jìn)行排序，元素序列的變化情況如下：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則采用的排序方法是()。計(jì)算題：已知數(shù)據(jù)序列為(12,5,9,20,6,31,24),對該數(shù)據(jù)序列進(jìn)行排序，寫出插入排序、起泡排序、快速排序、簡單選擇排序、二路歸并排序每趟的結(jié)果。插入拄序：初始腱值序列12 59第一趟結(jié)果5129第二超結(jié)果59第三趟結(jié)果59第四趟結(jié)果56第五趟結(jié)果56第六趟結(jié)果C56206312420831241212063124122063124g1220312491220313249122024

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