數據結構第7章答案[共14頁]

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

2、圖進行深度優(yōu)先遍歷時，通常是采用 來實現算法的。 A)棧 B)隊列 C)樹 D)圖A08、一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時間復雜度為 。 A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知圖的鄰接矩陣，根據算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是 。 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、已知圖的鄰接矩陣同上題，根據算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結點序列是 。 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、已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是 。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是 。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、圖的深度優(yōu)先遍歷類似于二叉樹的 。 A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷D14、圖的廣度優(yōu)先遍歷類似于二叉樹的 。 A)先序遍歷 B)中序遍歷 C)后序遍歷

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

5、jkstra算法的時間復雜度是_。 A)O(n) B)O(n+e) C)O(n2) D)O(n*e)B20、設圖G采用鄰接表存儲，則拓撲排序算法的時間復雜度為 。 A)O(n) B)O(n+e) C)O(n2) D)O(n*e)D21、帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中 。 A)第i行非的元素之和 B)第i列非的元素之和 C)第i行非且非0的元素個數 D)第i列非且非0的元素個數C22、一個有n個頂點的無向圖最多有 條邊。 A)n B)n(n-1) C)n(n-1)/2 D)2nD23、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。 A)n B)(n-

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

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

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

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

10、、下列_的鄰接矩陣是對稱矩陣。 A)有向圖 B)無向圖 C)AOV網 D)AOE網BBD40、從鄰接陣矩 可以看出，該圖共有 個頂點；如果是有向圖該圖共有 條??；如果是無向圖，則共有 條邊。 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、當一個有N 個頂點的圖用鄰接矩陣A 表示時，頂點Vi 的度是_。 B42、下列說法不正確的是_。 A)圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次 B)圖的深度遍歷不適用于有向圖 C)遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D)圖的深

11、度遍歷是一個遞歸過程D43、無向圖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)，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是_。 A)abecdf B)acfebd C)aebcfd D)aedfcbD44、如圖所示，在5個序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度優(yōu)先遍歷的序列有_個。 A)5 B)4 C)3 D)2CC45、圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍歷得到的序列是 ，進行廣度優(yōu)先遍歷得到的頂點序列是 。 A)1354

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

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

14、算法中弧上權不能為負的原因是在實際應用中無意義； 利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3)；(圖用鄰接矩陣表示) Floyd求每對不同頂點對的算法中允許弧上的權為負，但不能有權和為負的回路。 A) B) C) D)A49、已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, , , , , , , , ，則G的拓撲序列是_。 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的拓撲序列

15、中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是_。 A)G中有弧 B)G中有一條從Vi到Vj的路徑 C)G中沒有弧 D)G 中有一條從Vj到Vi的路徑A51、關鍵路徑是事件結點網絡中_。 A)從源點到匯點的最長路徑 B)從源點到匯點的最短路徑 C)最長回路 D)最短回路C52、下面關于求關鍵路徑的說法不正確的是_。 A)求關鍵路徑是以拓撲排序為基礎的 B)一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同 C)一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差 D)關鍵活動一定位于關鍵路徑上B53、下列關于AOE網的敘述中，不正確的是_。 A)

16、關鍵活動不按期完成就會影響整個工程的完成時間 B)任何一個關鍵活動提前完成，那么整個工程將會提前完成 C)所有的關鍵活動提前完成，那么整個工程將會提前完成 D)某些關鍵活動提前完成，那么整個工程將會提前完成二、填空題01、在有向圖中，以頂點v為終點的邊的數目稱為v的入度。02、含n個頂點的無向連通圖中至少含有n-1條邊。03、圖的存儲結構表示有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等多種存儲結構。04、圖的存儲結構中，十字鏈表可以看成是有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。05、遍歷圖的2種常見方法是深度遍歷和廣度遍歷。06、有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i

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

18、；用克魯斯卡爾(Kruskal)算法的時間復雜度是O(elog2e)。14、對稀疏圖最好用克魯斯卡爾(Kruskal)算法求最小生成樹，對稠密圖最好用普里姆(Prim)算法來求解最小生成樹。15、用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度遞增的次序來得到最短路徑的。16、拓撲排序算法是通過重復選擇具有0個前驅頂點的過程來完成的。17、有向圖G用鄰接矩陣存儲，則第i行的所有元素之和等于頂點i的出度。18、有n個頂點的強連通有向圖G至少有n條弧。19、設有向圖G的鄰接矩陣為A，如果圖中不存在弧，則Ai,j的值為0。20、在n個頂點的無向圖中，若邊數n-1，則該圖必是連通圖

19、，此斷言是錯誤的。(正確/錯誤)21、在有n個頂點的有向圖中，每個頂點的度最大可達2(n-1)。22、若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲排序序列必定存在。(存在/不存在)23、一個有向無環(huán)圖的拓撲排序序列不一定是唯一的。(一定/不一定)24、判斷一個無向圖是一棵樹的條件是有n個頂點，n-1條邊的無向連通圖。25、有向圖G 的強連通分量是指有向圖的極大強連通子圖。26、一個連通圖的生成樹是一個極小連通子圖。27、具有10個頂點的無向圖，邊的總數最多為45。28、若用n表示圖中頂點數目，則有n(n-1)/2條邊的無向圖成為完全圖。29、G 是一個非連通無向圖，共有28條邊，

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

21、無向圖G=(V,E)，其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現用某一種圖遍歷方法從頂點a 開始遍歷圖，得到的序列為abecd，則采用的是深度優(yōu)先遍歷方法。38、一無向圖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)，對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得一生成樹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、為了實現圖的廣度優(yōu)先搜索，除了一個標志數組標志已訪問的圖的結點外，還需隊列存放被訪問的結點以實現遍歷。40、構造連通網最小生成樹的兩個典型算法是普里姆(prim)算法和克魯斯卡爾(Kruskal)算法。41、Prim(普里姆)算法適用于求邊稠密的網的最小生成樹；kruskal(克魯斯卡爾)算法適用于求邊稀疏的網的最小生成樹。42、下面描述的是一種構造最小生成樹算法的基本思想。設要處理的無向圖包括n 個節(jié)點V1，V2，Vn，用相鄰矩陣A 表示，邊的權全是正數。請在下列劃線處填上正確敘述。 (1)若(Vi,Vj)是邊，則A(i,j)的值等于(Vi,Vj)邊上的權值，若(

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

24、法，T2 中的邊構成圖的最小生成樹。44、有向圖G可拓撲排序的判別條件是不存在環(huán)。45、Dijkstra 最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按遞增次序依次產生，該算法弧上的權出現負值情況時，不能正確產生最短路徑。46、有向圖G=(V,E),其中 V(G)=0,1,2,3,4,5，用三元組表示弧及弧上的權d.E(G)為, , , , , , , ，則從源點0到頂點3的最短路徑長度是50，經過的中間頂點是頂點4。47、上面的圖去掉有向弧看成無向圖則對應的最小生成樹的邊權之和為75。48、在AOE網中，從源點到匯點路徑上各活動時間總和最長的路徑稱為關鍵路徑。49、當一個AOV 網用鄰

25、接表表示時，可按下列方法進行拓撲排序。 (1)查鄰接表中入度為0的頂點，并進棧； (2)若棧不空，則輸出棧頂元素Vj，并退棧；查Vj 的直接后繼Vk，對Vk 入度處理，處理方法是Vk度減1，若Vk入度己減到零，則Vk頂點入棧； (3)若?？諘r，輸出頂點數小于圖的頂點數，說明有環(huán)，否則拓撲排序完成。三、判斷題01、樹中的結點和圖中的頂點就是指數據結構中的數據元素。02、在n 個結點的無向圖中，若邊數大于n-1,則該圖必是連通圖。03、有e 條邊的無向圖，在鄰接表中有e 個結點。04、有向圖中頂點V 的度等于其鄰接矩陣中第V 行中的1 的個數。05、強連通圖的各頂點間均可達。06、強連通分量是無向

26、圖的極大強連通子圖。07、連通分量指的是有向圖中的極大連通子圖。08、十字鏈表是無向圖的一種存儲結構。09、無向圖的鄰接矩陣可用一維數組存儲。10、用鄰接矩陣法存儲一個圖所需的存儲單元數目與圖的邊數有關。11、有n 個頂點的無向圖, 采用鄰接矩陣表示, 圖中的邊數等于鄰接矩陣中非零元素之和的一半。12、有向圖的鄰接矩陣是對稱的。13、無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。14、鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它。15、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數

27、有關，而與圖的邊數無關。16、一個有向圖的鄰接表和逆鄰接表中結點的個數可能不等。17、廣度遍歷生成樹描述了從起點到各頂點的最短路徑。18、不同的求最小生成樹的方法最后得到的生成樹是相同的。19、連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。20、在圖G 的最小生成樹G1 中，可能會有某條邊的權值超過未選邊的權值。21、拓撲排序算法把一個無向圖中的頂點排成一個有序序列。22、拓撲排序算法僅能適用于有向無環(huán)圖。23、無環(huán)有向圖才能進行拓撲排序。24、有環(huán)圖也能進行拓撲排序。25、拓撲排序的有向圖中，最多存在一條環(huán)路。26、任何有向圖的結點都可以排成拓撲排序，而且拓撲序列不唯一。27、既使有

28、向無環(huán)圖的拓撲序列唯一，也不能唯一確定該圖。28、若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓撲有序序列必定存在。29、對一個AOV 網，從源點到終點的路徑最長的路徑稱作關鍵路徑。30、關鍵路徑是AOE 網中從源點到終點的最長路徑。31、在表示某工程的AOE 網中，加速其關鍵路徑上的任意關鍵活動均可縮短整個工程的完成時間。32、在AOE 圖中，關鍵路徑上某個活動的時間縮短，整個工程的時間也就必定縮短。33、在AOE 圖中，關鍵路徑上活動的時間延長多少，整個工程的時間也就隨之延長多少。34、當改變網上某一關鍵路徑上任一關鍵活動后，必將產生不同的關鍵路徑。四、簡答題01、寫出下面有向圖的

29、所有強連通分量。答：3個，分別是：a,bce,dfg02、已知圖的鄰接表如下，畫出圖G的所有連通分量。答：03、如下圖，分別用普里姆算法和克魯斯卡爾算法從頂點1開始求最小生成樹，寫出按次序產生邊的序列。說明：邊用(i,j)方式表示。答：普里姆算法產生邊的序列：(1,3),(3,4),(4,6),(6,5),(1,2) 克魯斯卡爾算法產生邊的序列：(4,6),(1,3),(4,3),(6,5),(1,2)04、如下圖，寫出所有的拓撲序列，并求在添加什么邊之后僅可能有惟一的拓撲序列。答：v1,v2,v3,v4 v1,v3,v2,v4 v2,v1,v3,v4 05、已知如圖所示的有向圖，請給出該圖的

30、:(1) 每個頂點的入/出度；(2) 鄰接矩陣；(3) 鄰接表；(4) 逆鄰接表。答：(1) 每個頂點的入/出度 (2) 鄰接矩陣 (3) 鄰接表 (4) 逆鄰接表 06、寫出無向帶樹圖的鄰接矩陣，并按普里姆算法填寫表格中的內容，最后畫出最小生成樹；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 最小生成樹07、按克魯斯卡爾算法寫出下面無向帶權圖求最小生成樹產生的邊序列。答：fg(2)ac(3)fe(3)ab(4)dh(4)bd(5)dg(5)

32、08、已知二維數組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。答：09、利用Dijkstra算法填寫表格求圖中從頂點a到其他各頂點間的最短路徑，并寫出最終結果。終點DistbcDefgS(終點集)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、求出下圖中從頂點1出發(fā)到其余各頂點的最短路徑。答：11、設圖G=(V，E)，V=1，2，3，4，5，6，E=，。畫出圖G，并寫出圖G中頂點的所有拓撲序列。答：1

33、，2，3，6，5，41，3，2，6，5，41，3，6，2，5，4五、代碼填空題01、圖的存儲結構定義如下：typedef struct ArcCell VRType adj; /*圖中有1/0表示是否有邊，網中表示邊上的權值*/ /* InfoType *info; 與邊相關的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*頂點向量*/ AdjMatrix arcs; /*鄰接矩陣*/ int vexnum,arcnum; /*圖中當前頂點數和

34、邊數*/ MGraph; (1) 請寫出下面函數實現的功能：頂點在頂點向量中的定位。 int LocateVex(MGraph G,VertexType v) int i; for(i=0;iG.vexnum;i+) if (strcmp(v,G.vexsi)=0) break; return i; (2) 下面函數的功能是在圖中查找第1個鄰接點，請?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) 下面函數的功能是

35、在圖中查找下一個鄰接點，請?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、已知圖的鄰接表表示的形式說明如下：#define MaxNum 80typedef struct node int adjvex; /鄰接點域 struct node *next; /鏈指針域 EdgeNode; /邊表結點結構描述typedef struct char vertex; /頂點域 EdgeNode *firste

36、dge; /邊表頭指針 VertexNode; /頂點表結點結構描述typedef struct VertexNode adjlistMaxNum; /鄰接表 int n,e; AlGraph; /鄰接表結構描述 下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊，閱讀算法，并在空缺處填入合適的內容，使其成為一個完整的算法。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; 六、算法設計題01、編寫編歷算法，完成對圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。答：深度優(yōu)先搜索：課本P169算法7.4和算法7.5 廣度優(yōu)先搜索：課本P170算法7.602、編寫算法，

38、由依次輸入的頂點數目、弧的數目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。答：Status Build_AdjList(ALGraph &G) /輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /頂點數不能為負 G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /邊數不能為負 G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /輸入各頂點的符號 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、試在鄰接矩陣存儲結構上實現圖的基本操作：DeleteArc(G,v,w) ，即刪除一條邊的操作。提示：要刪除所有從第i個頂點出發(fā)的邊，即將鄰接矩陣的第i行全部置0。答：/本題中的圖G均為有向無權圖。 Status Delete_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上刪除邊(v,w) if(i=LocateVex(G,v)0) return ERROR;