數(shù)據(jù)結(jié)構(gòu)第7章答案[共14頁(yè)]

1、第7章 圖數(shù)據(jù)結(jié)構(gòu)作業(yè)答案一、單選題C01、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A)1/2 B)1 C)2 D)4B02、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A)1/2 B)1 C)2 D)4B03、有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有 條邊。 A)14 B)28 C)56 D)112C04、有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有 條邊。 A)5 B)6 C)7 D)8C05、有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A)14 B)28 C)56 D)112B06、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。 A)棧 B)隊(duì)列 C)樹(shù) D)圖A07、用鄰接表表示

2、圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。 A)棧 B)隊(duì)列 C)樹(shù) D)圖A08、一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為 。 A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是 。 A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知圖的鄰接矩陣同上題，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是 。 A)0 2 4 3 6 5 1 B)0 1

3、 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是 。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是 。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的 。 A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷D14、圖的廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的 。 A)先序遍歷 B)中序遍歷 C)后序遍歷

4、D)層次遍歷B15、任何一個(gè)無(wú)向連通圖的最小生成樹(shù) 。 A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在A16、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為 ，所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為 。 A)n、2e B)n、e C)n、n+e D)2n、2eC17、判斷有向圖是否存在回路，可以利用_算法。 A)關(guān)鍵路徑 B)最短路徑的Dijkstra C)拓?fù)渑判?D)廣度優(yōu)先遍歷A18、若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的“1”的個(gè)數(shù)為 。 A)圖中每個(gè)頂點(diǎn)的入度 B)圖中每個(gè)頂點(diǎn)的出度 C)圖中弧的條數(shù) D)圖中連通分量的數(shù)目C19、求最短路徑的Di

5、jkstra算法的時(shí)間復(fù)雜度是_。 A)O(n) B)O(n+e) C)O(n2) D)O(n*e)B20、設(shè)圖G采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為 。 A)O(n) B)O(n+e) C)O(n2) D)O(n*e)D21、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中 。 A)第i行非的元素之和 B)第i列非的元素之和 C)第i行非且非0的元素個(gè)數(shù) D)第i列非且非0的元素個(gè)數(shù)C22、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有 條邊。 A)n B)n(n-1) C)n(n-1)/2 D)2nD23、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。 A)n B)(n-

6、1)2 C)n-1 D)n2A24、對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)， 。 A)第i行上的非零元素個(gè)數(shù)和第i列的非零元素個(gè)數(shù)一定相等 B)矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù) C)第i行上，第i列上非零元素總數(shù)等于頂點(diǎn)vi的度數(shù) D)矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)D25、已知圖的表示如下，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 。 A)abecdf B)acfebd C)aebcfd D)aedfcbB26、已知圖的表示如上題，若從頂點(diǎn)a出發(fā)按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 。 A)abcedf B)abcefd C)aebcfd D)acfdebC27、

7、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，則根據(jù)有向圖的深度遍歷算法，從頂點(diǎn)v1出發(fā)得到的頂點(diǎn)序列是 。 A)v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v2B28、有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如上題所示，則根據(jù)有向圖的廣度遍歷算法，從頂點(diǎn)v1出發(fā)得到的頂點(diǎn)序列是 。 A)v1,v2,v3,v4,v5 B)v1,v3,v2,v4,v5 C)v1,v2,v3,v5,v4 D)v1,v4,v3,v5,v2A29、一個(gè)圖中有n個(gè)頂點(diǎn)且包含k個(gè)連通分量，若按深度優(yōu)先搜索方法訪(fǎng)問(wèn)所有結(jié)點(diǎn)，則必須調(diào)用 次深度優(yōu)先遍歷算法。 A)k B)1

8、 C)n-k D)nD30、以下不正確的說(shuō)法是 。 A)無(wú)向圖中的極大連通子圖稱(chēng)為連通分量 B)連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn) C)圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn) D)有向圖的遍歷不可采用廣度優(yōu)先搜索方法A31、圖中有關(guān)路徑的定義是_。 A)由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B)由不同頂點(diǎn)所形成的序列 C)由不同邊所形成的序列 D)上述定義都不是B32、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有_條邊。 A)n-1 B)n(n-1)/2 C)n(n+1)/2 D)n A33、一個(gè)n 個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為_(kāi)。 A)n-1 B)n C

9、)n+1 D)nlognB34、要連通具有n 個(gè)頂點(diǎn)的有向圖，至少需要_條邊。 A)n-l B)n C)n+l D)2nB35、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)_倍。 A)1/2 B)2 C)1 D)4C36、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的_倍。 A)1/2 B)2 C)1 D)4A37、用有向無(wú)環(huán)圖描述表達(dá)式(A+B)*（A+B）/A），至少需要頂點(diǎn)的數(shù)目為_(kāi)。 A)5 B)6 C)8 D)9A38、用DFS 遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS 算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是_。 A)逆拓?fù)溆行?B)拓?fù)溆行?C)無(wú)序的 D)原順序B39

10、、下列_的鄰接矩陣是對(duì)稱(chēng)矩陣。 A)有向圖 B)無(wú)向圖 C)AOV網(wǎng) D)AOE網(wǎng)BBD40、從鄰接陣矩 可以看出，該圖共有 個(gè)頂點(diǎn)；如果是有向圖該圖共有 條弧；如果是無(wú)向圖，則共有 條邊。 A)9 B)3 C)6 D)1 E)以上答案均不正確 A)5 B)4 C)3 D)2 E)以上答案均不正確 A)5 B)4 C)3 D)2 E)以上答案均不正確B41、當(dāng)一個(gè)有N 個(gè)頂點(diǎn)的圖用鄰接矩陣A 表示時(shí)，頂點(diǎn)Vi 的度是_。 B42、下列說(shuō)法不正確的是_。 A)圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次 B)圖的深度遍歷不適用于有向圖 C)遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D)圖的深

11、度遍歷是一個(gè)遞歸過(guò)程D43、無(wú)向圖G=(V,E)，其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是_。 A)abecdf B)acfebd C)aebcfd D)aedfcbD44、如圖所示，在5個(gè)序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度優(yōu)先遍歷的序列有_個(gè)。 A)5 B)4 C)3 D)2CC45、圖中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的序列是 ，進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是 。 A)1354

12、267 B)1347652 C)1534276 D)1247653 E)以上答案均不正確 A)1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正確B46、在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度為_(kāi)。 A)O(n) B)O(n+e) C)O(n2) D)O(n3)CABA47、下面是求連通網(wǎng)的最小生成樹(shù)的prim算法：集合VT，ET分別放頂點(diǎn)和邊，初始為 ，下面步驟重復(fù)n-1次： ； ；最后： 。 A)VT，ET 為空 B)VT為所有頂點(diǎn)，ET為空 C)VT為網(wǎng)中任意一點(diǎn)，ET為空 D)VT為空，ET為網(wǎng)中所有邊 A)選i屬于VT

13、，j不屬于VT，且(i,j)上的權(quán)最小 B)選i屬于VT，j不屬于VT，且(i,j)上的權(quán)最大 C)選i不屬于VT，j不屬于VT，且(i,j)上的權(quán)最小 D)選i不屬于VT，j不屬于VT，且(i,j)上的權(quán)最大 A)頂點(diǎn)i加入VT，(i,j)加入ET B)頂點(diǎn)j加入VT，(i,j)加入ET C)頂點(diǎn)j加入VT，(i,j)從ET中刪去 D)頂點(diǎn)i,j加入VT，(i,j)加入ET A)ET中為最小生成樹(shù) B)不在ET中的邊構(gòu)成最小生成樹(shù) C)ET 中有n-1條邊時(shí)為生成樹(shù)，否則無(wú)解 D)ET中無(wú)回路時(shí)，為生成樹(shù)，否則無(wú)解A48、下面不正確的是_。 求從指定源點(diǎn)到其余各頂點(diǎn)的Dijkstra最短路徑

14、算法中弧上權(quán)不能為負(fù)的原因是在實(shí)際應(yīng)用中無(wú)意義； 利用Dijkstra求每一對(duì)不同頂點(diǎn)之間的最短路徑的算法時(shí)間是O(n3)；(圖用鄰接矩陣表示) Floyd求每對(duì)不同頂點(diǎn)對(duì)的算法中允許弧上的權(quán)為負(fù)，但不能有權(quán)和為負(fù)的回路。 A) B) C) D)A49、已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, , , , , , , , ，則G的拓?fù)湫蛄惺莀。 A)V1,V3,V4,V6,V2,V5,V7 B)V1,V3,V2,V6,V4,V5,V7 C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7D50、在有向圖G的拓?fù)湫蛄?/p>

15、中，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是_。 A)G中有弧 B)G中有一條從Vi到Vj的路徑 C)G中沒(méi)有弧 D)G 中有一條從Vj到Vi的路徑A51、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中_。 A)從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B)從源點(diǎn)到匯點(diǎn)的最短路徑 C)最長(zhǎng)回路 D)最短回路C52、下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是_。 A)求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的 B)一個(gè)事件的最早開(kāi)始時(shí)間同以該事件為尾的弧的活動(dòng)最早開(kāi)始時(shí)間相同 C)一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差 D)關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上B53、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是_。 A)

16、關(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ì)提前完成二、填空題01、在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱(chēng)為v的入度。02、含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有n-1條邊。03、圖的存儲(chǔ)結(jié)構(gòu)表示有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等多種存儲(chǔ)結(jié)構(gòu)。04、圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表可以看成是有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。05、遍歷圖的2種常見(jiàn)方法是深度遍歷和廣度遍歷。06、有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i

17、的出度。07、如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有n棵生成樹(shù)。08、n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為O(n2)。若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為O(n+e)。09、圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。10、已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。11、圖采用鄰接矩陣表示，則計(jì)算第i個(gè)頂點(diǎn)入度的方法是求鄰接矩陣第i列非0元素之和。12、用鄰接矩陣表示圖時(shí)，則判斷任意兩個(gè)頂點(diǎn)vi和vj之間是否有路徑相連，只需要檢查第i行第j列的元素是否為0即可。13、用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹(shù)的時(shí)間復(fù)雜度為O(n2)

18、；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是O(elog2e)。14、對(duì)稀疏圖最好用克魯斯卡爾(Kruskal)算法求最小生成樹(shù)，對(duì)稠密圖最好用普里姆(Prim)算法來(lái)求解最小生成樹(shù)。15、用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度遞增的次序來(lái)得到最短路徑的。16、拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。17、有向圖G用鄰接矩陣存儲(chǔ)，則第i行的所有元素之和等于頂點(diǎn)i的出度。18、有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有n條弧。19、設(shè)有向圖G的鄰接矩陣為A，如果圖中不存在弧，則Ai,j的值為0。20、在n個(gè)頂點(diǎn)的無(wú)向圖中，若邊數(shù)n-1，則該圖必是連通圖

19、，此斷言是錯(cuò)誤的。(正確/錯(cuò)誤)21、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2(n-1)。22、若一個(gè)有向圖的鄰接矩陣中對(duì)角線(xiàn)以下元素均為零，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖凇?存在/不存在)23、一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄胁灰欢ㄊ俏ㄒ坏摹?一定/不一定)24、判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是有n個(gè)頂點(diǎn)，n-1條邊的無(wú)向連通圖。25、有向圖G 的強(qiáng)連通分量是指有向圖的極大強(qiáng)連通子圖。26、一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖。27、具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45。28、若用n表示圖中頂點(diǎn)數(shù)目，則有n(n-1)/2條邊的無(wú)向圖成為完全圖。29、G 是一個(gè)非連通無(wú)向圖，共有28條邊，

20、則該圖至少有9個(gè)頂點(diǎn)。30、在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要n條弧。31、構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有n條弧。32、有n個(gè)頂點(diǎn)的有向圖，至少需要量n條弧才能保證是連通的。33、N 個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有2(N-1)個(gè)非零元素。34、在圖G 的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的度；對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的出度。35、在有向圖的鄰接矩陣表示中，計(jì)算第i個(gè)頂點(diǎn)入度的方法是第i列非0元素個(gè)數(shù)。36、對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)e 條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為n，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為2e。37、已知一

21、無(wú)向圖G=(V,E)，其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a 開(kāi)始遍歷圖，得到的序列為abecd，則采用的是深度優(yōu)先遍歷方法。38、一無(wú)向圖G(V,E)，其中V(G)=1,2,3,4,5,6,7， E(G)=(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (6,7), (5,1)，對(duì)該圖從頂點(diǎn)3開(kāi)始進(jìn)行遍歷，去掉遍歷中未走過(guò)的邊，得一生成樹(shù)G(V,E), V(G)=V(G), E(G)= (1,3), (3,6), (7,3), (1,2), (1,5), (2,4)，則采用的遍

22、歷方法是廣度優(yōu)先遍歷。39、為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪(fǎng)問(wèn)的圖的結(jié)點(diǎn)外，還需隊(duì)列存放被訪(fǎng)問(wèn)的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。40、構(gòu)造連通網(wǎng)最小生成樹(shù)的兩個(gè)典型算法是普里姆(prim)算法和克魯斯卡爾(Kruskal)算法。41、Prim(普里姆)算法適用于求邊稠密的網(wǎng)的最小生成樹(shù)；kruskal(克魯斯卡爾)算法適用于求邊稀疏的網(wǎng)的最小生成樹(shù)。42、下面描述的是一種構(gòu)造最小生成樹(shù)算法的基本思想。設(shè)要處理的無(wú)向圖包括n 個(gè)節(jié)點(diǎn)V1，V2，Vn，用相鄰矩陣A 表示，邊的權(quán)全是正數(shù)。請(qǐng)?jiān)谙铝袆澗€(xiàn)處填上正確敘述。 (1)若(Vi,Vj)是邊，則A(i,j)的值等于(Vi,Vj)邊上的權(quán)值，若(

23、Vi,Vj)不是邊，則A(i,j)的值是一個(gè)比任何邊的權(quán)都大的數(shù)， 矩陣的對(duì)角線(xiàn)元素全為0。 (2)構(gòu)造最小生成樹(shù)過(guò)程中，若節(jié)點(diǎn)Vi 已包括進(jìn)生成樹(shù)，就把相鄰矩陣的對(duì)角線(xiàn)元素A(i,i)置成1，若(Vi,Vj)已包括進(jìn)生成樹(shù)，就把矩陣元素A(i,j)置成負(fù)值。 (3)算法結(jié)束時(shí)，相鄰矩陣中為負(fù)的元素指出最小生成樹(shù)的邊。43、有一個(gè)用于n 個(gè)頂點(diǎn)連通帶權(quán)無(wú)向圖的算法描述如下：(1)設(shè)集合T1與T2，初始均為空；(2)在連通圖上任選一點(diǎn)加入T1；(3)以下步驟重復(fù)n-1 次：a)在i屬于T1，j不屬于T1的邊中選最小權(quán)的邊；b)該邊加入T2。上述算法完成后，T2 中共有n-1條邊，該算法稱(chēng)普里姆算

24、法，T2 中的邊構(gòu)成圖的最小生成樹(shù)。44、有向圖G可拓?fù)渑判虻呐袆e條件是不存在環(huán)。45、Dijkstra 最短路徑算法從源點(diǎn)到其余各頂點(diǎn)的最短路徑的路徑長(zhǎng)度按遞增次序依次產(chǎn)生，該算法弧上的權(quán)出現(xiàn)負(fù)值情況時(shí)，不能正確產(chǎn)生最短路徑。46、有向圖G=(V,E),其中 V(G)=0,1,2,3,4,5，用三元組表示弧及弧上的權(quán)d.E(G)為, , , , , , , ，則從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度是50，經(jīng)過(guò)的中間頂點(diǎn)是頂點(diǎn)4。47、上面的圖去掉有向弧看成無(wú)向圖則對(duì)應(yīng)的最小生成樹(shù)的邊權(quán)之和為75。48、在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)路徑上各活動(dòng)時(shí)間總和最長(zhǎng)的路徑稱(chēng)為關(guān)鍵路徑。49、當(dāng)一個(gè)AOV 網(wǎng)用鄰

25、接表表示時(shí)，可按下列方法進(jìn)行拓?fù)渑判颉?(1)查鄰接表中入度為0的頂點(diǎn)，并進(jìn)棧； (2)若棧不空，則輸出棧頂元素Vj，并退棧；查Vj 的直接后繼Vk，對(duì)Vk 入度處理，處理方法是Vk度減1，若Vk入度己減到零，則Vk頂點(diǎn)入棧； (3)若?？諘r(shí)，輸出頂點(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，說(shuō)明有環(huán)，否則拓?fù)渑判蛲瓿伞Ｈ?、判斷題01、樹(shù)中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素。02、在n 個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。03、有e 條邊的無(wú)向圖，在鄰接表中有e 個(gè)結(jié)點(diǎn)。04、有向圖中頂點(diǎn)V 的度等于其鄰接矩陣中第V 行中的1 的個(gè)數(shù)。05、強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。06、強(qiáng)連通分量是無(wú)向

26、圖的極大強(qiáng)連通子圖。07、連通分量指的是有向圖中的極大連通子圖。08、十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。09、無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)。10、用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。11、有n 個(gè)頂點(diǎn)的無(wú)向圖, 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。12、有向圖的鄰接矩陣是對(duì)稱(chēng)的。13、無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)矩陣，有向圖的鄰接矩陣一定是非對(duì)稱(chēng)矩陣。14、鄰接矩陣適用于有向圖和無(wú)向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無(wú)向圖，而只能使用鄰接表存儲(chǔ)形式來(lái)存儲(chǔ)它。15、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)

27、有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。16、一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。17、廣度遍歷生成樹(shù)描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。18、不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的。19、連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。20、在圖G 的最小生成樹(shù)G1 中，可能會(huì)有某條邊的權(quán)值超過(guò)未選邊的權(quán)值。21、拓?fù)渑判蛩惴ò岩粋€(gè)無(wú)向圖中的頂點(diǎn)排成一個(gè)有序序列。22、拓?fù)渑判蛩惴▋H能適用于有向無(wú)環(huán)圖。23、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判颉?4、有環(huán)圖也能進(jìn)行拓?fù)渑判颉?5、拓?fù)渑判虻挠邢驁D中，最多存在一條環(huán)路。26、任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ弧?7、既使有

28、向無(wú)環(huán)圖的拓?fù)湫蛄形ㄒ?，也不能唯一確定該圖。28、若一個(gè)有向圖的鄰接矩陣對(duì)角線(xiàn)以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇?9、對(duì)一個(gè)AOV 網(wǎng)，從源點(diǎn)到終點(diǎn)的路徑最長(zhǎng)的路徑稱(chēng)作關(guān)鍵路徑。30、關(guān)鍵路徑是AOE 網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑。31、在表示某工程的AOE 網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動(dòng)均可縮短整個(gè)工程的完成時(shí)間。32、在AOE 圖中，關(guān)鍵路徑上某個(gè)活動(dòng)的時(shí)間縮短，整個(gè)工程的時(shí)間也就必定縮短。33、在AOE 圖中，關(guān)鍵路徑上活動(dòng)的時(shí)間延長(zhǎng)多少，整個(gè)工程的時(shí)間也就隨之延長(zhǎng)多少。34、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。四、簡(jiǎn)答題01、寫(xiě)出下面有向圖的

29、所有強(qiáng)連通分量。答：3個(gè)，分別是：a,bce,dfg02、已知圖的鄰接表如下，畫(huà)出圖G的所有連通分量。答：03、如下圖，分別用普里姆算法和克魯斯卡爾算法從頂點(diǎn)1開(kāi)始求最小生成樹(shù)，寫(xiě)出按次序產(chǎn)生邊的序列。說(shuō)明：邊用(i,j)方式表示。答：普里姆算法產(chǎn)生邊的序列：(1,3),(3,4),(4,6),(6,5),(1,2) 克魯斯卡爾算法產(chǎn)生邊的序列：(4,6),(1,3),(4,3),(6,5),(1,2)04、如下圖，寫(xiě)出所有的拓?fù)湫蛄?，并求在添加什么邊之后僅可能有惟一的拓?fù)湫蛄?。答：v1,v2,v3,v4 v1,v3,v2,v4 v2,v1,v3,v4 05、已知如圖所示的有向圖，請(qǐng)給出該圖的

30、:(1) 每個(gè)頂點(diǎn)的入/出度；(2) 鄰接矩陣；(3) 鄰接表；(4) 逆鄰接表。答：(1) 每個(gè)頂點(diǎn)的入/出度 (2) 鄰接矩陣 (3) 鄰接表 (4) 逆鄰接表 06、寫(xiě)出無(wú)向帶樹(shù)圖的鄰接矩陣，并按普里姆算法填寫(xiě)表格中的內(nèi)容，最后畫(huà)出最小生成樹(shù)；VbcDeFghUV-UVexlowcosta4a3AaaaaabcdefghVexlowcostVexlowcostVexlowcostVexlowcostVexlowcostVexLowcostVexlowcost答：(1)鄰接矩陣為：VbcdefghUV-UVexlowcosta4a3aaaaaab,c,d,e,f,g,hVexlowcost

31、a40c5aaac5a,cb,d,e,f,g,hVexlowcost00c5b9aac5a,c,bd,e,f,g,hVexlowcost000d7d6d5d4a,c,b,de,f,g,hVexlowcost000d7d6d50a,c,b,d,he,f,gVexlowcost000d7g200a,c,b,d,h,gf,eVexlowcost000f3000a,c,b,d,h,g,feVexlowcost0000000a,c,b,d,h,g,f,e 最小生成樹(shù)07、按克魯斯卡爾算法寫(xiě)出下面無(wú)向帶權(quán)圖求最小生成樹(shù)產(chǎn)生的邊序列。答：fg(2)ac(3)fe(3)ab(4)dh(4)bd(5)dg(5)

32、08、已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。答：09、利用Dijkstra算法填寫(xiě)表格求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，并寫(xiě)出最終結(jié)果。終點(diǎn)DistbcDefgS(終點(diǎn)集)k=1k=2k=3k=4k=5k=6答：ac：2(a,c)af：6(a,c,f)ae：10(a,c,e)ad：11(a,c,f,d)ag：14(a,c,f,d,g)ab：15(a,b)10、求出下圖中從頂點(diǎn)1出發(fā)到其余各頂點(diǎn)的最短路徑。答：11、設(shè)圖G=(V，E)，V=1，2，3，4，5，6，E=，。畫(huà)出圖G，并寫(xiě)出圖G中頂點(diǎn)的所有拓?fù)湫蛄?。答?

33、，2，3，6，5，41，3，2，6，5，41，3，6，2，5，4五、代碼填空題01、圖的存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct ArcCell VRType adj; /*圖中有1/0表示是否有邊，網(wǎng)中表示邊上的權(quán)值*/ /* InfoType *info; 與邊相關(guān)的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*頂點(diǎn)向量*/ AdjMatrix arcs; /*鄰接矩陣*/ int vexnum,arcnum; /*圖中當(dāng)前頂點(diǎn)數(shù)和

34、邊數(shù)*/ MGraph; (1) 請(qǐng)寫(xiě)出下面函數(shù)實(shí)現(xiàn)的功能：頂點(diǎn)在頂點(diǎn)向量中的定位。 int LocateVex(MGraph G,VertexType v) int i; for(i=0;iG.vexnum;i+) if (strcmp(v,G.vexsi)=0) break; return i; (2) 下面函數(shù)的功能是在圖中查找第1個(gè)鄰接點(diǎn)，請(qǐng)?zhí)羁铡?int FirstAdjVex(MGraph G,int v) int j,p=-1; for(j=0;jG.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p; (3) 下面函數(shù)的功能是

35、在圖中查找下一個(gè)鄰接點(diǎn)，請(qǐng)?zhí)羁铡?int NextAdjVex(MGraph G,int v,int w) int j,p=-1; for(j=w+1;jG.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p; 02、已知圖的鄰接表表示的形式說(shuō)明如下：#define MaxNum 80typedef struct node int adjvex; /鄰接點(diǎn)域 struct node *next; /鏈指針域 EdgeNode; /邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedef struct char vertex; /頂點(diǎn)域 EdgeNode *firste

36、dge; /邊表頭指針 VertexNode; /頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedef struct VertexNode adjlistMaxNum; /鄰接表 int n,e; AlGraph; /鄰接表結(jié)構(gòu)描述 下列算法輸出圖G的深度優(yōu)先生成樹(shù)(或森林)的邊，閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。typedef enum FALSE,TRUE Boolean;Boolean visitedMaxNum;void DFSForest(AlGraph *G) for(i=0; in; i+) visitedi=FALSE; for(i=0;in;i+) if (!visit

37、edi) DFSTree(G,i);void DFSTree(AlGraph *G, int i) visitedi=TRUE; p=G-adjlisti.firstedge; while(p!=NULL) if (!visitedp-adjves) printf(G-adjlisti.vertex, G-adjlistp-adjvex.vertex); DSFTree(G, p-adjvex); p=p-next; 六、算法設(shè)計(jì)題01、編寫(xiě)編歷算法，完成對(duì)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。答：深度優(yōu)先搜索：課本P169算法7.4和算法7.5 廣度優(yōu)先搜索：課本P170算法7.602、編寫(xiě)算法，

38、由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。答：Status Build_AdjList(ALGraph &G) /輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /頂點(diǎn)數(shù)不能為負(fù) G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /邊數(shù)不能為負(fù) G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /輸入各頂點(diǎn)的符號(hào) for(m=1;m=a;m+) t

39、=getchar();h=getchar(); /t為弧尾,h為弧頭 if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)nextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 03、試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w) ，即刪除一條邊的操作。提示：要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊，即將鄰接矩陣的第i行全部置0。答：/本題中的圖G均為有向無(wú)權(quán)圖。 Status Delete_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上刪除邊(v,w) if(i=LocateVex(G,v)0) return ERROR;