北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研例題解析6

1、理碩教育專注于北理工考研輔導(dǎo)本資料由理碩教育整理，理碩教育是全國(guó)唯一專注于北理工考研輔導(dǎo)的學(xué)校，相對(duì)于其它機(jī)構(gòu)理碩教育有得天獨(dú)厚的優(yōu)勢(shì)。豐富的理工內(nèi)部資料資源與人力資源確保每個(gè)學(xué)員都受益匪淺，確保理碩教育的學(xué)員初試通過(guò)率89%以上，復(fù)試通過(guò)率接近100%，理碩教育現(xiàn)開(kāi)設(shè)初試專業(yè)課VIP一對(duì)一，初試專業(yè)課網(wǎng)絡(luò)小班，假期集訓(xùn)營(yíng)，復(fù)試VIP一對(duì)一輔導(dǎo)，復(fù)試網(wǎng)絡(luò)小班，考前專業(yè)課網(wǎng)絡(luò)小班，滿足學(xué)員不同的需求。因?yàn)閷Ｒ凰詫I(yè)，理碩教育助您圓北理之夢(mèng)。詳情請(qǐng)查閱理碩教育官網(wǎng)第 6 章 圖 課后習(xí)題講解 1. 填空題 設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n，則圖G至少有（ ）條邊，至多有（ ）條邊；若G為有向圖，則至少有（

2、 ）條邊，至多有（ ）條邊?！窘獯稹?，n(n-1)/2，0，n(n-1)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。 任何連通圖的連通分量只有一個(gè)，即是（ ）。【解答】其自身 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（ ）和（ ）。【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。 已知無(wú)向圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為（ ）。【解答】(n+e)【分析】在無(wú)向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有n+2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為(n+2e)

3、=(n+e)。 已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是（ ）?！窘獯稹壳蟮趈列的所有元素之和 有向圖G用鄰接矩陣Ann存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的（ ）?！窘獯稹砍龆?圖的深度優(yōu)先遍歷類似于樹(shù)的（ ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（ ）；圖的廣度優(yōu)先遍歷類似于樹(shù)的（ ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（ ）?！窘獯稹壳靶?，棧，層序，隊(duì)列 對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（ ），利用Kruskal算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（ ）?！窘獯稹?n2)，(elog2e)【分析】Prim算法采用鄰接矩陣做存儲(chǔ)結(jié)構(gòu)，適合于求稠密圖的最小生

4、成樹(shù)；Kruskal算法采用邊集數(shù)組做存儲(chǔ)結(jié)構(gòu)，適合于求稀疏圖的最小生成樹(shù)。 如果一個(gè)有向圖不存在（ ），則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄?。【解答】回?在一個(gè)有向圖中，若存在弧、，則在其拓?fù)湫蛄兄?，頂點(diǎn)vi, vj, vk的相對(duì)次序?yàn)椋?）?！窘獯稹縱i, vj, vk【分析】對(duì)由頂點(diǎn)vi, vj, vk組成的圖進(jìn)行拓?fù)渑判颉?. 選擇題 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。A 1/2 B 1 C 2 D 4【解答】C【分析】設(shè)無(wú)向圖中含有n個(gè)頂點(diǎn)e條邊，則。 n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）條邊，其形狀是（ ）。A n B n+1 C n-1 D n×(n

5、-1)E 無(wú)回路F 有回路 G 環(huán)狀 H 樹(shù)狀【解答】A，G 含n 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（ ）。A 1 B n/2 C n-1 D n 【解答】C【分析】若超過(guò)n-1，則路徑中必存在重復(fù)的頂點(diǎn)。 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（ ）。A n B (n-1)2 C n-1 D n2【解答】D 圖的生成樹(shù)（），n個(gè)頂點(diǎn)的生成樹(shù)有（ ）條邊。A 唯一 B 不唯一 C 唯一性不能確定D n E n +1 F n-1【解答】C，F(xiàn) 設(shè)無(wú)向圖G=(V, E)和G' =(V', E' )，如果G' 是G的生成

6、樹(shù)，則下面的說(shuō)法中錯(cuò)誤的是（ ）。A G' 為 G的子圖 B G' 為 G的連通分量C G' 為G的極小連通子圖且V = V' D G' 是G的一個(gè)無(wú)環(huán)子圖【解答】B【分析】連通分量是無(wú)向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊都加上，所以，連通分量中可能存在回路。 G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有（ ）個(gè)頂點(diǎn)。A 6 B 7 C 8 D 9 【解答】D【分析】n個(gè)頂點(diǎn)的無(wú)向圖中，邊數(shù)en(n-1)/2，將e=28代入，有n8，現(xiàn)已知無(wú)向圖非連通，則n=9。 最小生成樹(shù)指的是（ ） 。A 由連通網(wǎng)所得到的邊數(shù)最少的

7、生成樹(shù)B 由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)C 連通網(wǎng)中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)D 連通網(wǎng)的極小連通子圖 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（ ）。A 求關(guān)鍵路徑的方法 B 求最短路徑的方法C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法【解答】D【分析】當(dāng)有向圖中無(wú)回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序（退出DFSTraverse算法）即為逆向的拓?fù)湫蛄小?下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（ ）?br /> A 關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B 任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C 所有的關(guān)鍵活

8、動(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. 判斷題 一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等?！窘獯稹繉?duì)。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。 用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)?！窘獯稹繉?duì)。鄰接矩陣的空間復(fù)雜度為(n2)，與邊的個(gè)數(shù)無(wú)關(guān)。 圖G的生成樹(shù)是該圖的一個(gè)極小連通子圖【解答】錯(cuò)。必須包含全部頂點(diǎn)。 無(wú)向

9、圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的【解答】錯(cuò)。有向圖的鄰接矩陣不一定對(duì)稱，例如有向完全圖的鄰接矩陣就是對(duì)稱的。 對(duì)任意一個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問(wèn)圖的所有頂點(diǎn)?！窘獯稹垮e(cuò)。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問(wèn)圖的所有頂點(diǎn)。 在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧?！窘獯稹垮e(cuò)。只能說(shuō)明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。 若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖??！窘獯稹繉?duì)。參見(jiàn)第11題的證明。 在AOE網(wǎng)中一定只有一條關(guān)鍵路徑?br />【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，

10、他們的路徑長(zhǎng)度相同。4n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接表存儲(chǔ)，回答下列問(wèn)題?br /> 圖中有多少條邊？ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？ 任意一個(gè)頂點(diǎn)的度是多少?br />【解答】 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。 第i個(gè)邊表中是否含有結(jié)點(diǎn)j。 該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。5n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣存儲(chǔ)，回答下列問(wèn)題： 圖中有多少條邊？ 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？ 任意一個(gè)頂點(diǎn)的度是多少？【解答】 鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。 當(dāng)鄰接矩陣A中Aij=1（或Aji=1）時(shí)，表示兩頂點(diǎn)之間有邊相連。 計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。6證明：生成樹(shù)中最長(zhǎng)路

11、徑的起點(diǎn)和終點(diǎn)的度均為。【解答】用反證法證明。設(shè)v1, v2, , vk是生成樹(shù)的一條最長(zhǎng)路徑，其中，v1為起點(diǎn)，vk為終點(diǎn)。若vk的度為2，取vk的另一個(gè)鄰接點(diǎn)v，由于生成樹(shù)中無(wú)回路，所以，v在最長(zhǎng)路徑上，顯然v1, v2, , vk , v的路徑最長(zhǎng)，與假設(shè)矛盾。所以生成樹(shù)中最長(zhǎng)路徑的終點(diǎn)的度為1。同理可證起點(diǎn)v1的度不能大于1，只能為1。7已知一個(gè)連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)v1出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。 【解答】鄰接矩陣表示如下： 深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列

12、為：v1 v2 v4 v6 v3 v5鄰接表表示如下：8圖6-7所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別按Prim算法和Kruskal算法求最小生成樹(shù)。 【解答】按Prim算法求最小生成樹(shù)的過(guò)程如下：按Kruskal算法求最小生成樹(shù)的過(guò)程如下：9對(duì)于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑。 【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度v1 v7 v1 v7 7v1 v5 v1 v5 11v1 v4 v1 v7 v4 13v1 v6 v1 v7 v4 v6 16v1 v2 v1 v7 v2 22v1 v3 v1 v7 v4 v6 v3 2510

13、如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑。 【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度v1 v3 v1 v3 15v1 v5 v1 v5 15v1 v2 v1 v3 v2 25v1 v6 v1 v3 v2 v6 40v1 v4 v1 v3 v2 v4 4511證明：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無(wú)環(huán)圖的鄰接矩陣中主對(duì)角線以下的元素全部為0?！窘獯稹咳我鈔個(gè)結(jié)點(diǎn)的有向無(wú)環(huán)圖都可以得到一個(gè)拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2vn-1，我們來(lái)證明此時(shí)的鄰接矩陣A為上三角矩陣。證明采用反證法。假設(shè)此時(shí)的鄰接矩陣

14、不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得Aij不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄校瑅i的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。12. 算法設(shè)計(jì) 設(shè)計(jì)算法，將一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換為鄰接表?！窘獯稹肯仍O(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10;template struct AdjMatrix T vertexMa

15、xSize; /存放圖中頂點(diǎn)的數(shù)組int arcMaxSizeMaxSize; /存放圖中邊的數(shù)組int vertexNum, arcNum; /圖的頂點(diǎn)數(shù)和邊數(shù);鄰接表存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10;struct ArcNode /定義邊表結(jié)點(diǎn)int adjvex; /鄰接點(diǎn)域ArcNode *next;template struct VertexNode /定義頂點(diǎn)表結(jié)點(diǎn)T vertex;ArcNode *firstedge;struct AdjListVertexNode adjlistMaxSize;int vertexNum, arcNum; /圖的頂點(diǎn)數(shù)

16、和邊數(shù);具體算法如下： 設(shè)計(jì)算法，將一個(gè)無(wú)向圖的鄰接表轉(zhuǎn)換成鄰接矩陣?！窘獯稹吭卩徑颖砩享樞虻厝∶總€(gè)邊表中的結(jié)點(diǎn)，將鄰接矩陣中對(duì)應(yīng)單元的值置為1。鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)定義與上題相同。具體算法如下： 設(shè)計(jì)算法，計(jì)算圖中出度為零的頂點(diǎn)個(gè)數(shù)。【解答】在有向圖的鄰接矩陣中，一行對(duì)應(yīng)一個(gè)頂點(diǎn)，每行的非零元素的個(gè)數(shù)等于對(duì)應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，則對(duì)應(yīng)頂點(diǎn)的出度為零。據(jù)此，從第一行開(kāi)始，查找每行的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下： 以鄰接表作存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)按深度優(yōu)先遍歷圖的非遞歸算法?！窘獯稹繀⒁?jiàn)6.2.1。 已知一個(gè)有向圖的鄰接表，編寫算法建立其逆鄰接表。

17、【解答】在有向圖中，若鄰接表中頂點(diǎn)vi有鄰接點(diǎn)vj，在逆鄰接表中vj一定有鄰接點(diǎn)vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點(diǎn)firstedge域置空，然后逐行將表頭結(jié)點(diǎn)的鄰接點(diǎn)進(jìn)行轉(zhuǎn)化。 分別基于深度優(yōu)先搜索和廣度優(yōu)先搜索編寫算法，判斷以鄰接表存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（ij）?！窘獯稹?基于深度優(yōu)先遍歷： 基于廣度優(yōu)先遍歷：學(xué)習(xí)自測(cè)及答案 1某無(wú)向圖的鄰接矩陣A=，可以看出，該圖共有（ ）個(gè)頂點(diǎn)。A 3 B 6 C 9 D 以上答案均不正確【解答】A2無(wú)向圖的鄰接矩陣是一個(gè)（ ），有向圖的鄰接矩陣是一個(gè)（ ）A 上三角矩陣 B 下三角矩陣 C 對(duì)稱矩陣 D 無(wú)規(guī)

18、律【解答】C，D3下列命題正確的是（ ）。A 一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B 一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C 一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D 一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一【解答】B4十字鏈表適合存儲(chǔ)（ ），鄰接多重表適合存儲(chǔ)（ ）?！窘獯稹坑邢驁D，無(wú)向圖5. 在一個(gè)具有n 個(gè)頂點(diǎn)的有向完全圖中包含有（ ）條邊：A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2【解答】B6n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有（ ）個(gè)非零元素?！窘獯稹?(n-1)7表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有（ ）個(gè)非零矩陣元素?！窘獯稹?0008一個(gè)具有n個(gè)頂點(diǎn)k條邊的無(wú)向圖是一個(gè)森林（n>k），則該森林中必有（ ）棵樹(shù)。A k B n C n - k D 1【解答】C9用深度優(yōu)先遍歷方法遍歷一個(gè)有向無(wú)環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（ ）。A 逆拓?fù)溆行?B 拓?fù)溆行?C 無(wú)序 D 深度優(yōu)先遍歷序列【解答】A10. 關(guān)鍵路徑是AOE網(wǎng)中（ ）。A