《數據結構》習題匯編07-第七章-圖-試題

1、第七章 圖 試題7、單項選擇題）的數目。C. 權D. 權值1. 在無向圖中定義頂點的度為與它相關聯的（A. 頂點 B. 邊2. 在無向圖中定義頂點 v i 與 vj 之間的路徑為從v i 到達 v j 的一個（ ） 。A. 頂點序列 B. 邊序列 C. 權值總和 D. 邊的條數3. 圖的簡單路徑是指（A. 權值）不重復的路徑。B. 頂點C. 邊D. 邊與頂點均4. 設無向圖的頂點個數為A. n-1n ，則該圖最多有（B. n（n-1）/2)條邊。C. n(n+1)/2D. n(n-1)5. n 個頂點的連通圖至少有（ ）條邊。A. n-1B. nC. n+1D. 06. 在一個無向圖中，所有頂

2、點的度數之和等于所有邊數的 （）A. 3B. 2C. 1倍。D. 1/27. 若采用鄰接矩陣法存儲一個n 個頂點的無向圖，則該鄰接矩陣是一個（）A. 上三角矩陣B. 稀疏矩陣8. 圖的深度優(yōu)先搜索類似于樹的（A. 先根B. 中根9. 圖的廣度優(yōu)先搜索類似于樹的（A. 先根B. 中根C. 對角矩陣D. 對稱矩陣）次序遍歷。C. 后根D. 層次）次序遍歷。C. 后根D. 層次10. 在 用 Kruskal 算法求解帶權連通圖的最小（代價）生成樹時，通常采用一個（）輔助結構，判斷一條邊的兩個端點是否在同一個連通分量上。A. 位向量B. 堆C. 并查集D. 生成樹頂點集合11. 在 用 Kruskal

3、在圖中構成（A. 重邊12. 在 用 Dijkstra()。A. 非零算法求解帶權連通圖的最?。ù鷥r）生成樹時，選擇權值最小的邊的原則是該邊不能）。B. 有向環(huán)C. 回路D. 權值重復的邊算法求解帶權有向圖的最短路徑問題時，要求圖中每條邊所帶的權值必須是C. 非整C. 非負 D. 非正13. 在 一個連通圖中進行深度優(yōu)先搜索得到一棵深度優(yōu)先生成樹，樹根結點是關節(jié)點的充要條件是它至少有（ ）子女。A. 1B. 2C. 3D. 015.設有向圖有n個頂點和( )。A. O(nlog 2e)16.設 G1=(V1,E1) 和 G2 = (V2,E2)A. G1 是G2的子圖C. G1 是G2的連通分

4、量為兩個圖，如果 V1 V2 , E1 E2 ,則稱(B. G2 是G1的子圖D. G2是G1的連通分量14.設有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓撲排序時，總的計算時間為 ( )。A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n 2)e條邊，采用鄰接矩陣作為其存儲表示，在進行拓撲排序時，總的計算時間為B.O(n+e)C.O(ne)D.O(n 2)。B.出度D.(入度+出度)/217. 有向圖的一個頂點的度為該頂點的(A.入度C.入度與出度之和18. 一個連通圖的生成樹是包含圖中所有頂點的一個()子圖。A.極小B.連通C.極小連通D.無環(huán)19. n (n

5、1)個頂點的強連通圖中至少含有()條有向邊。A. n-1B. nn(n-1)/2D. n(n-1)20. 在一個帶權連通圖 G中，權值最小的邊一定包含在6的()生成樹中。A.某個最小B.任何最小C.廣度優(yōu)先D.深度優(yōu)先21. 對于具有e條邊的無向圖，它的鄰接表中有()個邊結點。A.e-1B. eC.2(e-1)D. 2e22. 對于如圖所示的帶權有向圖，從頂點 1到頂點5的最短路徑為()。A.1,4,5B.1,2,3,5C.1,4,3,5D. 1,2,4, 3,523. 具有n個頂點的有向無環(huán)圖最多可包含()條有向邊。A.n-1B. nC.n(n-1)/2D.n(n-1)24. 一個有n個頂點

6、和n條邊的無向圖一定是()。A.連通的 B.不連通的C.無環(huán)的D.有環(huán)的25. 在n個頂點的有向無環(huán)圖的鄰接矩陣中至少有()個零元素。A. nB.n(n-1)/2C. n(n+1)/2D. n(n-1)26. 對 于有向圖，其鄰接矩陣表示比鄰接表表示更易于( ) 。A.求一個頂點的度B. 求一個頂點的鄰接點C. 進行圖的深度優(yōu)先遍歷D. 進行圖的廣度優(yōu)先遍歷27. 在 一個有向圖的鄰接矩陣表示中，刪除一條邊 需要耗費的時間是( ) 。A. O(1)B. O(i)C. O(j)D. O(i+j)28. 與 鄰接矩陣相比，鄰接表更適合于存儲( )圖。A. 無向 B. 連通C. 稀疏D. 稠密圖29

7、. 設 一個有 n 個頂點和 e 條邊的有向圖采用鄰接矩陣表示，要計算某個頂點的出度所耗費的時間是()。A. O(n)B. O(e)C. O(n+e)D. O(n 2)30. 為 了實現圖的廣度優(yōu)先遍歷， BFS 算法使用的一個輔助數據結構是( ) 。A.棧B. 隊列C. 二叉樹D. 樹參考答案：1. B2. A3. B4. B5. A6. B7. D8. A9. D10. C11.C12. C13. B14. B15. D16. A17. C18. C19. B20. A21. D22. D23. C24. D25. C26. A27. A28. C29. A30. B二、填空題1. 圖的定

8、義包含一個頂點集合和一個邊集合。其中，頂點集合是一個有窮 集合。2. 用鄰接矩陣存儲圖，占用存儲空間數與圖中頂點個數 關，與邊數 關。3. n (n 0)個頂點的無向圖最多有 條邊，最少有 條邊。4. n (n 0)個頂點的連通無向圖最少有 條邊。0101005. 若3個頂點的圖G的鄰接矩陣為 01 0 ,則圖G一定是 向圖。6. n (n 0)個頂點的連通無向圖各頂點的度之和最少為 。7. 設圖 G = (V, E) ， V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1,V3) ，則從頂點 V0 開始的圖 G 的不同深度優(yōu)先序

9、列有 種，例如 8. 設圖 G = (V, E) ， V = P, Q, R, S, T, E = , , , 從頂點 P 出發(fā)，對圖 G 進行廣度優(yōu)先搜索所得的所有序列為 和9. n (n 0)個頂點的無向圖中頂點的度的最大值為 。10. 在 重連通圖中每個頂點的度至少為 。11. 在 非重連通圖中進行深度優(yōu)先搜索，則深度優(yōu)先生成樹的根為關節(jié)點的充要條件是它至少有 個子女。12. (n0)個頂點的連通無向圖的生成樹至少有 條邊。13. 1 01 個頂點的連通網絡N 有 100 條邊，其中權值為 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 的邊各10 條，則網絡N 的最小生成樹

10、各邊的權值之和為 。14. 在 使用 Kruskal算法構造連通網絡的最小生成樹時，只有當一條候選邊的兩個端點不在同一個 上，才有可能加入到生成樹中。15. 深 度優(yōu)先生成樹的高度比廣度優(yōu)先生成樹的高度 。16. 求 解帶權連通圖最小生成樹的 Prim 算法適合于 圖的情形，而Kruskal 算法適合于 圖的情形。17. 求解最短路徑的 Dijkstra 算法適用于各邊上的權值 的情形。若設圖的頂點數為 n ，則該算法的時間復雜度為 。18. 若 對一個有向無環(huán)圖進行拓撲排序，再對排在拓撲有序序列中的所有頂點按其先后次序重新編號，則在相應的鄰接矩陣中所有 元素將集中到對角線以上。參考答案： 1

11、. 非空2. 有, 無3. n(n-1)/2, 04. n-15. 有6. 2(n-1)7. 4 ， V0V1V3V2 (或 V0V2V1V3, V0V2V3V1, V0V3V1V2 )8. PQRST 和 PRQTS11. 214. 連通分量17. 非負， O(n2)9. n-110. 212. n-113. 55015. 高16. 稠密，稀疏18. 非零(或值為 1 的)三、判斷題1. 一個圖的子圖可以是空圖，頂點個數為 0 。2. 存儲圖的鄰接矩陣中，矩陣元素個數不但與圖的頂點個數有關，而且與圖的邊數也有關。3. 一個有 1000 個頂點和 1000 條邊的有向圖的鄰接矩陣是一個稀疏矩陣

12、。)可以遍訪圖中的所有頂點。4. 對一個連通圖進行一次深度優(yōu)先搜索( depth first search5. 有n（n 1）個頂點的無向連通圖最少有n-1條邊。6. 有n（n 1）個頂點的有向強連通圖最少有n條邊。7. 圖中各個頂點的編號是人為的，不是它本身固有的，因此可以因為某種需要改變頂點的編號。8. 如果無向圖中各個頂點的度都大于2 ，則該圖中必有回路。9. 如果有向圖中各個頂點的度都大于2 ，則該圖中必有回路。10. 圖 的深度優(yōu)先搜索（ depth first search ）是一種典型的回溯搜索的例子，可以通過遞歸算法求 解。）算法不是遞歸算法。11. 圖 的廣度優(yōu)先搜索（ br

13、eadth first searchn 個頂點和 n-1 條邊組成。算法可以求一個頂點到其它各個頂點的最短路） ，一定可以將圖的所有頂點按其關鍵碼大小12. 有 n 個頂點、 e 條邊的帶權有向圖的最小生成樹一般由13. 對 于一個邊上權值任意的帶權有向圖，使用 Dijkstra徑。14. 對 一個有向圖進行拓撲排序（topological sorting排列到一個拓撲有序的序列中。15. 有 回路的有向圖不能完成拓撲排序。16. 對任何用頂點表示活動的網絡（ AOV 網）進行拓撲排序的結果都是唯一的。17. 用 邊表示活動的網絡（ AOE 網）的關鍵路徑是指從源點到終點的路徑長度最長的路徑。

14、18. 對 于 AOE 網絡，加速任一關鍵活動就能使整個工程提前完成。19. 對 于 AOE 網絡，任一關鍵活動延遲將導致整個工程延遲完成。20. 在 AOE 網絡中，可能同時存在幾條關鍵路徑，稱所有關鍵路徑都需通過的有向邊為橋。如果加速這樣的橋上的關鍵活動就能使整個工程提前完成。21. 用 鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數有關，而與圖的邊數無關。22. 鄰 接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。23. 鄰 接矩陣只適用于稠密圖 （邊數接近于頂點數的平方） ， 鄰接表適用于稀疏圖 （邊數遠小于頂點數的平 方）24

15、. 存 儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（上）三角部分就可以了。25. 連通分量是無向圖中的極小連通子圖。26. 強連通分量是有向圖中的極大強連通子圖。27. 在AOE網絡中一定只有一條關鍵路徑。參考答案：1.否2.否3.是4.是5.是6.否7.是8.是9.否10.是11.是12.否13.否14.否15.是16.否17.是18.否19.是20.是21.是22.否23.是24.是25.否26.是27.否四、運算題1.設連通圖G如圖所示。試畫出該圖對應的鄰接矩陣表示，并給出對它執(zhí)行從頂點V0開始的廣度優(yōu)先搜索的結果。2.設連通圖G如圖所示。試畫出該圖及其對應的鄰接表表示，并給出

16、對它執(zhí)行從V0開始的深度優(yōu)先搜索的結果。3.設連通圖G如圖所示。試畫出從頂點V0出發(fā)的深度優(yōu)先生成樹,指出圖G中哪幾個頂點是關節(jié)點(即萬一它失效則通信網絡將發(fā)生故障)28. 連通圖G如圖所示，(1)如果有關節(jié)點，請找出所有的關節(jié)點。(2)如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？如何加?29. 于如圖所示的有向圖，試寫出：(1)從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹;(2)從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹2830. 有向圖G如圖所示。試畫出從頂點 V0開始進行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的DFS生成森林和BFS生成森林。7.表示圖的另一種方法是使用關聯矩陣

17、因此，如果邊j依附于頂點i ,則 是關聯矩陣，試說明在什么條件下將有INCINCij=1ADJ = INCO其中，一行對應于一個頂點，一列對應于一條邊。如果ADJ是圖G= (V,E )的鄰接矩陣，INC INCT I ,其中，INCT是矩陣INC的轉置矩陣，I是單位矩陣。兩個 n n的矩陣的乘積 C = A B定義為 n 1Cijaik bkjk 0公式中的 定義為按位加，定義為按位乘。設無向圖G如圖所示。試畫出該圖的鄰接矩陣和關聯矩陣。算法給出在構造最小生成樹過程中順序8.設有一個連通網絡如圖所示。試按如下格式，應用 Kruskal 選出的各條邊。3 5)42權值）（始頂點號，終頂點號，（，

18、）（，）（，）（，）（，）9.設有一個連通網絡如圖所示。試采用prim算法從頂點。開始構造最小生成樹。（寫出加入生成樹頂點 集合S和選擇邊Edge的順序）S頂點號Edge（頂點，頂點，權值）0(,)0(,)0(,)0(,)0(,)010.計算連通網的最小生成樹的Dijkstra算法可簡述如下：將連通網所有的邊以方便的次序逐條加入到初始為空的生成樹的邊集合 T中。每次選擇并加入一條邊時，需要判斷它是否會與先前加入 T中的邊 構成回路。如果構成了回路，則從這個回路中將權值最大的邊退選。如果以鄰接矩陣作為連通網的存儲結構（僅使用矩陣的上三角部分），并在鄰接矩陣的下三角部分記錄最小生成樹的邊信息。試以

19、如下所示的圖G為例，畫出構造出最小生成樹及其鄰接矩陣，并在括號內填入每次選擇的邊和可能去掉的邊。0 160Edge14 215919060 18 110260選擇的邊掉的（頂點, 頂權值）（頂點,頂權值）與 八、,與 八、,(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)11 .有八項活動，每項活動要求的前驅如下活動A0A1A2A3A4A5A6A7前驅無前 驅A0A0A0,A2A1A2,A4A3A5, A6(1) 試畫出相應的AOV網絡，并給出一個拓撲排序序列。(2)試改變某些結點的編號，使得用鄰接矩陣表示該網絡時所有對角

20、線以下的元素全為0。12 .試對下圖所示的AOE網絡(1) 這個工程最早可能在什么時間結束。(2)確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程提前 完成。13.設帶權有向圖如圖所示。試采用Dijkstra算法求從頂點0到其他各頂點的最短路徑和最短路徑長度。14 . 一項工程由六個子工程p1, p2, p6 組成。這些子工程之間有下列關系：p1 p2, p3 p6,p4 p3, p2 p6, p4 p5, p1 p3, p5 p6。符號 表示領先于的關系。例如，p2 p6 表示p2完成后p6才能開始。試給出該工程的三種可能的施工順序。15 .設一有向圖如下所示

21、，請問該有向圖是否為強連通圖，并畫出該有向圖所有的強連通分量。參考答案1.圖G對應的鄰接矩陣為G.Edge0 1 11 0 01 0 01 1 10 1 00 0 10 0 00 0 00 0 01 0 01 1 01 0 10 0 00 0 00 0 01 0 01 0 00 0 00 0 00 0 00 0 01 1 00 0 00 0 00 1 11 0 01 0 0執(zhí)行廣度優(yōu)先搜索的結果為V0V1V3V2V4V7V6V5V8 ,搜索結果不唯一。2 .圖G對應的鄰接表為:012345678執(zhí)行深度優(yōu)先搜索的結果為：V0V1V4V3V6V7V8V2V5 ,搜索結果不唯一。3 .圖G中，從V

22、0出發(fā)的深度優(yōu)先生成樹為:圖G中的關節(jié)點為:。從的子孫結點到的祖先結引一條邊，并將的子孫結點、與4 . (1)關節(jié)點為，(2)至少加四條邊(1, 10), (3, 4), (4, 5), (5, 6)點引一條邊，從的子孫結點到根的另一分支結點連結起來，可使其變?yōu)橹剡B通圖。(解答不唯一)5.以頂點 為根的深度優(yōu)先生成樹（不唯一）6 .深度優(yōu)先生成森林為：廣度優(yōu)先生成森林為：7 .當圖中的頂點個數等于邊 圖G對應的鄰接矩陣為：ADJ（2） qVoV2yQo V1 V4（o-oV 5V6V 7V2/%1V4foo6V5V6V7的條數時，ADJ = INC*INCT-I成立。0123456701100

23、0000100110001100001102010000013010000014001000015001000016000111107以頂點為根的廣度優(yōu)先生成樹:對應的關聯矩陣為:0 12 3110 010 110INC 00010001000100011000100010000000010001023450 10 0 0 100 11118.應用Kruskal算法順序選出最小生成樹的各條邊為:權值）(0,3,1 )(2,5,2 )(1,4,3 )(3,5,4 )(3,4,5 )始頂點號，終頂點號,(9.采用prim算法從頂點0開始構造最小生成樹的過程:10.最小生成樹及其鄰接矩陣如圖所示16

24、0161421160591950660181114026110EdgeS頂點號Edge（頂點，頂點，權值）0(0,1,9 )0, 1(1,3,5 )0, 1,3(1,2,7 )0, 1, 3, 2(2,4,6 )0, 1,3, 2, 4(2,5,7 )0, 1,3, 2, 4, 5選擇的邊去掉的邊（頂點，頂 權值） （頂點，頂 權值）(2 ,1 ,16)(,)(5 ,1 ,14)(,)(6 ,1 ,21)(,)(6 ,2 ,19)(6 ,1 ,21)(6 ,4 ,11)(,)(6 ,5 ,26)(6 ,5 ,26)(5 ,4 ,18)(6 ,2 ,19)(4 ,2 ,9)(5 ,4 ,18)(

25、3 ,2 ,5)(,)(4 ,6)(4 ,2 ,9)3 ,選擇順序不唯一。11.相應的AOV網絡為:一個拓撲排序序列為：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓撲排序結果不唯一。按拓撲有序的次序對所有頂點從新編號：原編號A0A1A4A2A5A3A6A7新編號A0A1A2A3A4A5A6A7相應鄰接矩陣為:Edge0 12 3 40 10 100 0 10 00 0 0 0 1567100000010002010500 1600 07各頂點(事件)的最早可能開始時間Ve(i)和最遲允許開始時間Vl(i)參看下表:頂點123456Ve01915293843Vl0191537384

26、3各邊(活動)的最早可能開始時間Ee(k)和最遲允許開始時間El(k)參看下表：邊Ee00151915192938El170151927273738如果活動k的最早可能開始時間 Ee(k)與最遲允許開始時間El(k)相等，則該活動是關鍵活動。本題的關鍵活動為, , , ,它們組成關鍵路徑。這些關鍵活動中任一個提前完成，整個工程就能提前完成。整個工程最早在43天完成。由關鍵活動組成的AOV網絡如圖所示。13.帶權有向圖如圖所示:應用Dijkstra算法求從頂點V0到其他各頂點的最短路徑Path和最短路徑長度Len的步驟如下:步 驟V0V1V2V3V4動作PatherLIPatheL nPathe

27、iL1PatheL n1V0V14一ooV0V37一oo選 V0V1V0V14V0V1V28V0V37一oo參照V1調 整2V0V14V0V1V28V0V37一oo選 V0V3V0V14V0V1V28V0V37V0V3V412參照V3調 整3V0V14V0V1V28V0V37V0V3V412選 V0V1V2V0V14V0V1V28V0V37V0V1V2V410參照V2調 整4V0V14V0V1V28V0V37V0V1V2V410選V0V1V2V414 .圖G為p2可能的施工順序有：p1, p2, p4, p3, p5, p6p1, p4, p2, p3, p5, p6p4, p5, p1, p

28、3, p2, p615 .該圖的強連通分量分別為:五、算法分析題1 .已知有向圖的鄰接矩陣表示及其一個算法描述如下:01111、001000001111000*00110，A =/圖的鄰接矩陣表示有向圖鄰接距陣/有向圖當前結點數/當前邊數const int MaxVertices = 5;struct Graph int EdgeMaxVerticesMaxVertices; / int CurrentNode;int CurrentEdges;int unknown (int i ) int d = 0;for ( int j = 0; j CurrentNode; j+) if ( Edg

29、e皿!= 0 ) d+;if ( Edgeji != 0 ) d+;return d;(1)若定義圖的一個對象Graph G ,則執(zhí)行操作 G.unknown (3)后的返回值是多少?(2)試說明該算法的功能及時間復雜度。2 .已知有向圖的鄰接矩陣表示及其一個操作算法描述如下:0 10 0A = 0 01 110 01 0 1、0 0 00 1 10 0 00 1 0 )const int MaxVertices = 5;/圖的鄰接矩陣表示有向圖鄰接距陣/有向圖當前結點數/當前邊數struct Graph int EdgeMaxVerticesMaxVertices; /int Current

30、Node;int CurrentEdges; void unknown ( int i ) int d, j;d = 0;for ( j = 0; j CurrentNode; j+ ) if ( Edgeij ) d+; Edge皿=0; if ( Edgeji ) d+; Edge皿=0; CurrentEdges -= d;后該圖的鄰接矩陣，并說明該算若定義圖的一個對象Graph G，試寫出執(zhí)行操作 G.unknown法的功能。3 .已知有向圖的鄰接表類的表示的形式描述如下:4.struct Edge int dest; float cost;Edge * link;template s

31、truct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;int NumVertices;int NumEdges;int DegreeMaxVertices; / 鄰接表中邊結點的定義/ 鄰接的結點/ 邊的權值/ 鄰接表中頂點的定義/ 鄰接表/ 頂點表/ 當前頂點個數/ 當前邊數/ 各個頂點的度的記錄數組/ 下列算法是計算有向圖中各個頂點的度，并保存在數組 Degree 中。請在處/ 填入合適的內容，使其成為一個完整的算法。void FindDegree ( ) int i; Edge * p = NU

32、LL;for ( i = 0; i NumVertices; i+ ) Degreei =(1);for ( i = 0; i link ) (2) ;(3) ; ;已知有向圖的鄰接表類的表示的形式描述如下:struct Edge int dest; float cost;/ 鄰接表中邊結點的定義/ 鄰接的結點/ 邊的權值;Edge * link;template struct Vertex / 鄰接表中頂點的定義Type data;Edge *adj;template struct Graph / 鄰接表Vertex * NodeTable; int NumVertices;int NumE

33、dges;/ 頂點表/ 當前頂點個數/ 當前邊數int DegreeMaxVertices;/ 各個頂點的度的記錄數組/ 下列算法是計算有向圖 G 中一個頂點 vi 的入度。請在/ 使其成為一個完整的算法。void FindDegree ( int i ) int deg, j;Edge * p = NULL;deg = 0;for ( j = 0; j link;if ( p = NULL ) break;if ( p != NULL )(2);return deg;處填入合適的內容，5. 已知有向圖的鄰接表類的表示的形式描述如下：struct Edge int dest; float co

34、st; Edge * link;/ 鄰接表中邊結點的定義/ 鄰接的結點/ 邊的權值;template struct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;int NumVertices;/ 鄰接表中頂點的定義/ 鄰接表/ 頂點表/ 當前頂點個數int NumEdges;/ 當前邊數int DegreeMaxVertices;/ 各個頂點的度的記錄數組/ 下列算法是從有向圖 G 中刪除所有以 vi 為弧頭的有向邊。請在處填入合適/ 的內容，使其成為一個完整的算法。void DeletEdge ( i

35、nt i ) int de = 0, j; Edge *p, *q;if ( i = NumVertices ) cout 錯誤輸入 endl; exit (1); for ( j = 0; j link; if ( p != NULL ) if ( p != NodeTablej.adj ) q-link = p-link;else (2);delete p; de+;NumEdges = NumEdges - de;6.已知帶權圖的鄰接矩陣表示和鄰接表類表示的形式描述分別如下:(1) 鄰接矩陣的定義#define INFINITY INT_MAXconst int MaxVertices

36、= 20;template struct AdjMatrix Type * NodeTable;float arrMaxverticesMaxVertices;int NumVertices;int NumEdges;(2) 鄰接表定義struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct AdjTable Vertex * NodeTable;int NumVertices;/INT_MAX 為最大整數，表示8/ 頂點表定義/ 鄰接矩陣定義/

37、當前頂點個數/ 當前邊數/ 鄰接表中邊結點的定義/ 鄰接的結點/ 邊的權值/ 鄰接表中頂點的定義/ 鄰接表/ 頂點表/ 當前頂點個數/ 當前邊數處填入合適int NumEdges; / 下列算法是根據一個圖的鄰接矩陣建立該圖的鄰接表，請在/ 的內容，使其成為一個完整的算法。AdjTable * convertM ( ) / 將圖的鄰接矩陣(用 this 指針指示)轉換為鄰接表，函數返回鄰接表的地址。AdjTable * A; Edge *e;A-NodeTable = new VertexNumVertices;A-NumEdges = NumEdges;A-NumVertices = Num

38、Vertices;for ( int i = 0; i NodeTablei.data = NodeTablei;A-NodeTablei.adj =(1);for ( int j = 0; j dest = j;e-cost= (2);e-link = A-NodeTablei.adj;(3);return A;7. 已知帶權圖的鄰接矩陣表示和鄰接表類表示的形式描述分別如下：(1) 鄰接矩陣的定義#define INFINITY INT_MAXconst int MaxVertices = 20;template struct AdjMatrix Type * NodeTable;float

39、 arrMaxverticesMaxVertices;int NumVertices;int NumEdges;(2) 鄰接表定義struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct AdjTable Vertex * NodeTable;int NumVertices;int NumEdges;/INT_MAX 為最大整數，表示8/ 頂點表定義/ 鄰接矩陣定義/ 當前頂點個數/ 當前邊數/ 鄰接表中邊結點的定義/ 鄰接的結點/ 邊的權值/ 鄰

40、接表中頂點的定義/ 鄰接表/ 頂點表/ 當前頂點個數/ 當前邊數/ 下列算法是根據一個圖的鄰接表存儲結構建立該圖的鄰接矩陣存儲結構，/ 請在處填入合適的內容，使其成為一個完整的算法AdjMatrix * convertAL( ) / 將圖的鄰接表(用 this 指針指示)轉換為鄰接矩陣，函數返回鄰接矩陣的地址。AdjMatrix * A; int i, j;Edge *p;A-NodeTable = new VertexNumVertices;A-arr = new float MaxverticesMaxVertices;A-NumEdges = NumEdges;A-NumVertices

41、 = NumVertices;for ( i = 0; i NumVertices; i+ ) for ( j = 0; j arrij = INFINITY;A-NodeTablei = (1);for ( i = 0; i arrip-dest = (2);(3);8. 已知圖的鄰接表和逆鄰接表的形式描述如下：struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;Vertex * Oppos

42、itNodeTable;int NumVertices;int NumEdges;/ 結點定義/ 鄰接結點/ 邊的權值/ 頂點定義/ 鄰接表與逆鄰接表定義/ 鄰接表頂點表/ 逆鄰接表頂點表/ 當前頂點個數/ 當前邊數/ 下列算法是根據一個圖的鄰接表存儲結構建立該圖的逆鄰接表存儲結構，請/ 在處填入合適的內容，使其成為一個完整的算法。void convertM ( ) int i; Edge *p, *q;OppositNodeTable = new VertexNumVertices;for ( i = 0; i NumVertices; i+ ) OppositNodeTablei.data

43、 = NodeTablei.data; OppositNodeTablei.adj = NULL;for ( i = 0; i dest = i;q-cost = p-cost;OppositNodeTablep-dest.adj = q;參考答案：1 . (1)執(zhí)行操作后的返回值是5。/2 分(2)算法的功能是計算有向圖中一個頂點的度。/2分算法的時間復雜度是 O(n) , n為圖的頂點個數。/2 分2 .執(zhí)行操作G.unknown (3) 后，圖的鄰接矩陣為：/3分10 110 1、00000000010000000000 J算法的功能是從圖中刪除所有與某個頂點相關的邊。/3分3 .填空結果8.填空結果30 0/2(2) Degreep-dest+(3) Degreei+4 .填空結果(1) p != NULL & p-dest