第八章試題56079

1、書據(jù)結(jié)構(gòu)課程（本科）第八章試題一、單項(xiàng)選擇題1. 在無向圖中定義頂點(diǎn)的度為與它相關(guān)聯(lián)的（ ）的數(shù)目。A. 頂點(diǎn)B. 邊C. 權(quán)D. 權(quán)值2. 在無向圖中定義頂點(diǎn) vi與vj之間的路徑為從vi到達(dá)vj的一個(gè)（ ）。A. 頂點(diǎn)序列B. 邊序列C. 權(quán)值總和D. 邊的條數(shù)3. 圖的簡單路徑是指（ ）不重復(fù)的路徑。A. 權(quán)值B. 頂點(diǎn)C. 邊D. 邊與頂點(diǎn)均4. 設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1) 5. n個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。A. n-1 B. nC. n+1D. 06. 在一個(gè)無向圖中，所有頂點(diǎn)的

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

3、算法求解帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹時(shí)，選擇權(quán)值最小的邊的原則是該邊不能在圖中構(gòu)成（ ）。A. 重邊B. 有向環(huán)C. 回路D. 權(quán)值重復(fù)的邊12. 在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時(shí)，要求圖中每條邊所帶的權(quán)值必須是（ ）。A. 非零B. 非整C. 非負(fù)D. 非正13. 在一個(gè)連通圖中進(jìn)行深度優(yōu)先搜索得到一棵深度優(yōu)先生成樹，樹根結(jié)點(diǎn)是關(guān)節(jié)點(diǎn)的充要條件是它至少有（ ）子女。A. 1B. 2C. 3D. 014. 設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2

4、)15. 設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接矩陣作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2)16. 設(shè)G1 = (V1, E1) 和G2 = (V2, E2) 為兩個(gè)圖，如果V1 Í V2，E1 Í E2，則稱（ ）。 A. G1是G2的子圖 B. G2是G1的子圖 C. G1是G2的連通分量 D. G2是G1的連通分量17. 有向圖的一個(gè)頂點(diǎn)的度為該頂點(diǎn)的（ ）。 A. 入度 B. 出度C. 入度與出度之和 D. (入度出度)218. 一個(gè)連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)（ ）子

5、圖。 A. 極小B. 連通C. 極小連通D. 無環(huán)19. n (n1) 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有（ ）條有向邊。 A. n-1 B. nn(n-1)/2D. n(n-1)20. 在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的（ ）生成樹中。 A. 某個(gè)最小B. 任何最小C. 廣度優(yōu)先D.深度優(yōu)先21. 對(duì)于具有e條邊的無向圖，它的鄰接表中有（ ）個(gè)邊結(jié)點(diǎn)。 A. e-1B. e C. 2(e-1) D. 2e22. 對(duì)于如圖所示的帶權(quán)有向圖，從頂點(diǎn)1到頂點(diǎn)5的最短路徑為（ ）。 A.1, 4, 5B. 1, 2, 3, 5C. 1, 4, 3, 5D. 1, 2, 4, 3, 512613

6、81955412323. 具有n個(gè)頂點(diǎn)的有向無環(huán)圖最多可包含（ ）條有向邊。 A. n-1B. n C. n(n-1)/2 D.n(n-1)24. 一個(gè)有n個(gè)頂點(diǎn)和n條邊的無向圖一定是（ ）。 A. 連通的 B. 不連通的 C. 無環(huán)的 D. 有環(huán)的25. 在n個(gè)頂點(diǎn)的有向無環(huán)圖的鄰接矩陣中至少有（ ）個(gè)零元素。 A. nB. n(n-1)/2 C. n(n+1)/2D. n(n-1)26. 對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于（ ）。 A. 求一個(gè)頂點(diǎn)的度 B. 求一個(gè)頂點(diǎn)的鄰接點(diǎn) C. 進(jìn)行圖的深度優(yōu)先遍歷 D. 進(jìn)行圖的廣度優(yōu)先遍歷27. 在一個(gè)有向圖的鄰接矩陣表示中，刪除一條邊

7、<vi, vj>需要耗費(fèi)的時(shí)間是（ ）。 A. O(1) B. O(i) C. O(j) D. O(i+j)28. 與鄰接矩陣相比，鄰接表更適合于存儲(chǔ)（ ）圖。 A. 無向B.連通C.稀疏 D. 稠密圖29. 設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條邊的有向圖采用鄰接矩陣表示，要計(jì)算某個(gè)頂點(diǎn)的出度所耗費(fèi)的時(shí)間是（ ）。 A. O(n) B. O(e) C. O(n+e) D. O(n2)30. 為了實(shí)現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)是（ ）。 A. 棧 B. 隊(duì)列C. 二叉樹 D. 樹參考答案：1. B2. A3. B4. B5. A 6. B7. D8. A9. D10. C1

8、1.C12. C13. B14. B15. D16. A17. C18. C 19. B 20. A21. D 22. D 23. C24. D 25. C26. A 27. A 28. C 29. A 30. B 二、填空題1. 圖的定義包含一個(gè)頂點(diǎn)集合和一個(gè)邊集合。其中，頂點(diǎn)集合是一個(gè)有窮_集合。2. 用鄰接矩陣存儲(chǔ)圖，占用存儲(chǔ)空間數(shù)與圖中頂點(diǎn)個(gè)數(shù)_關(guān)，與邊數(shù)_關(guān)。3. n (n0) 個(gè)頂點(diǎn)的無向圖最多有_條邊，最少有_條邊。4. n (n0) 個(gè)頂點(diǎn)的連通無向圖最少有_條邊。5. 若3個(gè)頂點(diǎn)的圖G的鄰接矩陣為，則圖G一定是_向圖。6. n (n0) 個(gè)頂點(diǎn)的連通無向圖各頂點(diǎn)的度之和最少為

9、_。7. 設(shè)圖G = (V, E)，V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1, V3)，則從頂點(diǎn)V0開始的圖G的不同深度優(yōu)先序列有_種，例如_。8. 設(shè)圖G = (V, E)，V = P, Q, R, S, T, E = <P, Q>, <P, R>, <Q, S>, <R, T>，從頂點(diǎn)P出發(fā)，對(duì)圖G進(jìn)行廣度優(yōu)先搜索所得的所有序列為_和_。9. n (n0) 個(gè)頂點(diǎn)的無向圖中頂點(diǎn)的度的最大值為_。10. 在重連通圖中每個(gè)頂點(diǎn)的度至少為_。11. 在非重連通圖中進(jìn)行深度優(yōu)先

10、搜索，則深度優(yōu)先生成樹的根為關(guān)節(jié)點(diǎn)的充要條件是它至少有_個(gè)子女。12. (n0) 個(gè)頂點(diǎn)的連通無向圖的生成樹至少有_條邊。13. 101個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N有100條邊，其中權(quán)值為1, 2, 3, 4, 5, 6, 7, 8, 9, 10的邊各10條，則網(wǎng)絡(luò)N的最小生成樹各邊的權(quán)值之和為_。14. 在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時(shí)，只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè)_上，才有可能加入到生成樹中。15. 深度優(yōu)先生成樹的高度比廣度優(yōu)先生成樹的高度_。16. 求解帶權(quán)連通圖最小生成樹的Prim算法適合于_圖的情形，而Kruskal算法適合于_圖的情形。17. 求解最短路徑的Dij

11、kstra算法適用于各邊上的權(quán)值_的情形。若設(shè)圖的頂點(diǎn)數(shù)為n，則該算法的時(shí)間復(fù)雜度為_。18. 若對(duì)一個(gè)有向無環(huán)圖進(jìn)行拓?fù)渑判?，再?duì)排在拓?fù)溆行蛐蛄兄械乃许旤c(diǎn)按其先后次序重新編號(hào)，則在相應(yīng)的鄰接矩陣中所有_元素將集中到對(duì)角線以上。參考答案：1. 非空2. 有, 無3. n(n-1)/2, 04. n-15. 有 6. 2(n-1)7. 4，V0V1V3V2（或V0V2V1V3, V0V2V3V1, V0V3V1V2）8. PQRST和PRQTS9. n-110. 211. 212. n-1 13. 55014. 連通分量15. 高16. 稠密，稀疏17. 非負(fù)，O(n2)18. 非零（或值為

12、1的）三、判斷題1. 一個(gè)圖的子圖可以是空圖，頂點(diǎn)個(gè)數(shù)為0。2. 存儲(chǔ)圖的鄰接矩陣中，矩陣元素個(gè)數(shù)不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。3. 一個(gè)有1000個(gè)頂點(diǎn)和1000條邊的有向圖的鄰接矩陣是一個(gè)稀疏矩陣。4. 對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索（depth first search）可以遍訪圖中的所有頂點(diǎn)。5. 有n (n1) 個(gè)頂點(diǎn)的無向連通圖最少有n-1條邊。6. 有n (n1) 個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有n條邊。7. 圖中各個(gè)頂點(diǎn)的編號(hào)是人為的，不是它本身固有的，因此可以因?yàn)槟撤N需要改變頂點(diǎn)的編號(hào)。8. 如果無向圖中各個(gè)頂點(diǎn)的度都大于2，則該圖中必有回路。9. 如果有向圖中各

13、個(gè)頂點(diǎn)的度都大于2，則該圖中必有回路。10. 圖的深度優(yōu)先搜索（depth first search）是一種典型的回溯搜索的例子，可以通過遞歸算法求解。11. 圖的廣度優(yōu)先搜索（breadth first search）算法不是遞歸算法。12. 有n個(gè)頂點(diǎn)、e條邊的帶權(quán)有向圖的最小生成樹一般由n個(gè)頂點(diǎn)和n-1條邊組成。13. 對(duì)于一個(gè)邊上權(quán)值任意的帶權(quán)有向圖，使用Dijkstra算法可以求一個(gè)頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短路徑。14. 對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判颍╰opological sorting），一定可以將圖的所有頂點(diǎn)按其關(guān)鍵碼大小排列到一個(gè)拓?fù)溆行虻男蛄兄小?5. 有回路的有向圖不能完成拓?fù)?/p>

14、排序。16. 對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。17. 用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）的關(guān)鍵路徑是指從源點(diǎn)到終點(diǎn)的路徑長度最長的路徑。18. 對(duì)于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。19. 對(duì)于AOE網(wǎng)絡(luò)，任一關(guān)鍵活動(dòng)延遲將導(dǎo)致整個(gè)工程延遲完成。20. 在AOE網(wǎng)絡(luò)中，可能同時(shí)存在幾條關(guān)鍵路徑，稱所有關(guān)鍵路徑都需通過的有向邊為橋。如果加速這樣的橋上的關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。21. 用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。22. 鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)

15、于有向圖和無向圖的存儲(chǔ)都適用。23. 鄰接矩陣只適用于稠密圖（邊數(shù)接近于頂點(diǎn)數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方）24. 存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，因此只要存儲(chǔ)鄰接矩陣的下（上）三角部分就可以了。25. 連通分量是無向圖中的極小連通子圖。26. 強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。27. 在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。參考答案：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.

16、是27. 否四、運(yùn)算題V0V1V2V5V4V3V6V7V81. 設(shè)連通圖G如圖所示。試畫出該圖對(duì)應(yīng)的鄰接矩陣表示，并給出對(duì)它執(zhí)行從頂點(diǎn)V0開始的廣度優(yōu)先搜索的結(jié)果。V0V1V2V5V4V3V6V7V82. 設(shè)連通圖G如圖所示。試畫出該圖及其對(duì)應(yīng)的鄰接表表示，并給出對(duì)它執(zhí)行從V0開始的深度優(yōu)先搜索的結(jié)果。V0V1V2V5V4V3V6V7V83. 設(shè)連通圖G如圖所示。試畫出從頂點(diǎn)V0出發(fā)的深度優(yōu)先生成樹，指出圖G中哪幾個(gè)頂點(diǎn)是關(guān)節(jié)點(diǎn)（即萬一它失效則通信網(wǎng)絡(luò)將發(fā)生故障）。4. 設(shè)連通圖G如圖所示， (1) 如果有關(guān)節(jié)點(diǎn)，請找出所有的關(guān)節(jié)點(diǎn)。(2) 如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？如

17、何加？5. 對(duì)于如圖所示的有向圖，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹V1V2V3V4V7V6V0V56. 設(shè)有向圖G如圖所示。試畫出從頂點(diǎn)V0開始進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的DFS生成森林和BFS生成森林。7. 表示圖的另一種方法是使用關(guān)聯(lián)矩陣INC 。其中，一行對(duì)應(yīng)于一個(gè)頂點(diǎn)，一列對(duì)應(yīng)于一條邊。因此，如果邊j依附于頂點(diǎn)i，則INCij=1。如果ADJ是圖G =（V, E）的鄰接矩陣，INC是關(guān)聯(lián)矩陣，試說明在什么條件下將有ADJ = INC´INCT-I，其中，INCT是矩陣INC的轉(zhuǎn)置

18、矩陣，I是單位矩陣。兩個(gè)n´n的矩陣的乘積C = A´B定義為公式中的 定義為按位加， 定義為按位乘。設(shè)無向圖G如圖所示。試畫出該圖的鄰接矩陣和關(guān)聯(lián)矩陣。01234567e0e1e2e3e4e5e7e6e8e98. 設(shè)有一個(gè)連通網(wǎng)絡(luò)如圖所示。試按如下格式，應(yīng)用Kruskal算法給出在構(gòu)造最小生成樹過程中順序選出的各條邊。0123456618753426 ( 始頂點(diǎn)號(hào)，終頂點(diǎn)號(hào)， 權(quán)值 )( , , )( , , )( , , )( , , )( , , )9. 設(shè)有一個(gè)連通網(wǎng)絡(luò)如圖所示。試采用prim算法從頂點(diǎn)0開始構(gòu)造最小生成樹。（寫出加入生成樹頂點(diǎn)集合S和選擇邊Edge

19、的順序）1234650910751187S:頂點(diǎn)號(hào)Edge:(頂點(diǎn)，頂點(diǎn)，權(quán)值)0( ， ， )0( ， ， )0 ( ， ， )0( ， ， )0( ， ， )0 10. 計(jì)算連通網(wǎng)的最小生成樹的Dijkstra算法可簡述如下：將連通網(wǎng)所有的邊以方便的次序逐條加入到初始為空的生成樹的邊集合T中。每次選擇并加入一條邊時(shí)，需要判斷它是否會(huì)與先前加入T中的邊構(gòu)成回路。如果構(gòu)成了回路，則從這個(gè)回路中將權(quán)值最大的邊退選。如果以鄰接矩陣作為連通網(wǎng)的存儲(chǔ)結(jié)構(gòu)（僅使用矩陣的上三角部分），并在鄰接矩陣的下三角部分記錄最小生成樹的邊信息。試以如下所示的圖G為例，畫出構(gòu)造出最小生成樹及其鄰接矩陣，并在括號(hào)內(nèi)填入每

20、次選擇的邊和可能去掉的邊。26211118141619956選 擇 的 邊去 掉 的 邊（頂點(diǎn),頂點(diǎn),權(quán)值）（頂點(diǎn),頂點(diǎn),權(quán)值）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）11. 有八項(xiàng)活動(dòng), 每項(xiàng)活動(dòng)要求的前驅(qū)如下:活動(dòng)A0A1A2A3A4A5A6A7前驅(qū)無前驅(qū)A0A0A0, A2A1A2, A4A3A5, A6 (1) 試畫出相應(yīng)的AOV網(wǎng)絡(luò), 并給出一個(gè)拓

21、撲排序序列。(2) 試改變某些結(jié)點(diǎn)的編號(hào), 使得用鄰接矩陣表示該網(wǎng)絡(luò)時(shí)所有對(duì)角線以下的元素全為0。12. 試對(duì)下圖所示的AOE網(wǎng)絡(luò)(1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。 (2) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。11115191022344556613. 設(shè)帶權(quán)有向圖如圖所示。試采用Dijkstra算法求從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑和最短路徑長度。 718244591234014. 一項(xiàng)工程由六個(gè)子工程p1, p2, ¼, p6組成。這些子工程之間有下列關(guān)系：p1 < p2, p3 < p6, p4 < p

22、3, p2 < p6, p4 < p5, p1 < p3, p5 < p6。符號(hào)“<”表示“領(lǐng)先于”的關(guān)系。例如，p2 < p6表示p2完成后p6才能開始。試給出該工程的三種可能的施工順序。15. 設(shè)一有向圖如下所示，請問該有向圖是否為強(qiáng)連通圖，并畫出該有向圖所有的強(qiáng)連通分量。gfecabd 參考答案：1. 圖G對(duì)應(yīng)的鄰接矩陣為執(zhí)行廣度優(yōu)先搜索的結(jié)果為V0V1V3V2V4V7V6V5V8，搜索結(jié)果不唯一。2. 圖G對(duì)應(yīng)的鄰接表為：31320310350126766213780 V01 V12 V23 V34 V45 V56 V67 V78 V8執(zhí)行深度優(yōu)先搜

23、索的結(jié)果為：V0V1V4V3V6V7V8V2V5，搜索結(jié)果不唯一。3. 圖GV0V1V2V5V4V3V6V7V8中，從V0出發(fā)的深度優(yōu)先生成樹為：圖G中的關(guān)節(jié)點(diǎn)為：V1, V2, V3, V6。4. (1) 關(guān)節(jié)點(diǎn)為 , , , , (2) 至少加四條邊 (1, 10), (3, 4), (4, 5), (5, 6)。從 的子孫結(jié)點(diǎn)到的祖先結(jié)點(diǎn)引一條邊，從 的子孫結(jié)點(diǎn) 到根 的另一分支 引一條邊，并將 的子孫結(jié)點(diǎn) 、 與結(jié)點(diǎn) 連結(jié)起來，可使其變?yōu)橹剡B通圖。（解答不唯一）5. 以頂點(diǎn) 為根的深度優(yōu)先生成樹（不唯一）：以頂點(diǎn) 為根的廣度優(yōu)先生成樹：V1V2V3V4V7V6V0V56. 深度優(yōu)先生成

24、森林為：V1V2V3V4V7V6V0V5廣度優(yōu)先生成森林為：7. 當(dāng)圖中的頂點(diǎn)個(gè)數(shù)等于邊的條數(shù)時(shí)，ADJ = INC*INCT-I成立。圖G對(duì)應(yīng)的鄰接矩陣為：對(duì)應(yīng)的關(guān)聯(lián)矩陣為：8. 應(yīng)用Kruskal算法順序選出最小生成樹的各條邊為：01234515342 ( 始頂點(diǎn)號(hào)，終頂點(diǎn)號(hào)， 權(quán)值 ) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )9. 采用prim算法從頂點(diǎn)0開始構(gòu)造最小生成樹的過程：S:頂點(diǎn)號(hào)Edge:(頂點(diǎn)，頂點(diǎn)，權(quán)值)0( 0， 1， 9 )0, 1( 1， 3， 5 )0, 1, 3 ( 1， 2， 7 )

25、0, 1, 3, 2( 2， 4， 6 )0, 1, 3, 2, 4( 2， 5， 7 )0, 1, 3, 2, 4, 5 1234650975710. 最小生成樹及其鄰接矩陣如圖所示14165611選 擇 的 邊去 掉 的 邊（頂點(diǎn),頂點(diǎn),權(quán)值）（頂點(diǎn),頂點(diǎn),權(quán)值）（ 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

26、 ）（ 4 , 2 , 9 ）（ 5 , 4 , 18 ）（ 3 , 2 , 5 ）（ , , ）（ 4 , 3 , 6 ）（ 4 , 2 , 9 ）選擇順序不唯一。11. 相應(yīng)的AOV網(wǎng)絡(luò)為：A0A1A2A3A4A5A6A7一個(gè)拓?fù)渑判蛐蛄袨椋篈0,A1,A4,A2,A5,A3,A6,A7。 注意：拓?fù)渑判蚪Y(jié)果不唯一。按拓?fù)溆行虻拇涡驅(qū)λ许旤c(diǎn)從新編號(hào)：原編號(hào)A0A1A4A2A5A3A6A7新編號(hào)A0A1A2A3A4A5A6A7A0A1A3A5A2A4A6A7相應(yīng)鄰接矩陣為：12. 針對(duì)下圖所示的AOE網(wǎng)絡(luò)111151910223445566各頂點(diǎn)（事件）的最早可能開始時(shí)間Ve(i)和最遲允

27、許開始時(shí)間Vl(i)參看下表：頂點(diǎn)123456Ve01915293843Vl01915373843各邊（活動(dòng)）的最早可能開始時(shí)間Ee(k)和最遲允許開始時(shí)間El(k)參看下表：邊<1,2><1,3><3,2><2,5><3,5><2,4><4,6><5,6>Ee00151915192938El170151927273738如果活動(dòng)k的最早可能開始時(shí)間Ee(k) 與最遲允許開始時(shí)間El(k)相等，則該活動(dòng)是關(guān)鍵活動(dòng)。本題的關(guān)鍵活動(dòng)為<1,3>, <3,2>, <2,5&g

28、t;, <5,6>，它們組成關(guān)鍵路徑。這些關(guān)鍵活動(dòng)中任一個(gè)提前完成，整個(gè)工程就能提前完成。整個(gè)工程最早在43天完成。由關(guān)鍵活動(dòng)組成的AOV網(wǎng)絡(luò)如圖所示。111151910223445566718244591234013. 帶權(quán)有向圖如圖所示： 應(yīng)用Dijkstra算法求從頂點(diǎn)V0到其他各頂點(diǎn)的最短路徑Path和最短路徑長度Len的步驟如下：步驟V0V1V2V3V4動(dòng)作PathLenPathLenPathLenPathLen1V0V14V0V37選V0V1V0V14V0V1V28V0V37參照V1調(diào)整2V0V14V0V1V28V0V37選V0V3V0V14V0V1V28V0V37V0

29、V3V412參照V3調(diào)整3V0V14V0V1V28V0V37V0V3V412選V0V1V2V0V14V0V1V28V0V37V0V1V2V410參照V2調(diào)整4V0V14V0V1V28V0V37V0V1V2V410選V0V1V2V4p1p2p6p4p5p314. 圖G為可能的施工順序有：p1, p2, p4, p3, p5, p6p1, p4, p2, p3, p5, p6p4, p5, p1, p3, p2, p615. 該圖的強(qiáng)連通分量分別為： ecabgfd五、算法分析題1. 已知有向圖的鄰接矩陣表示及其一個(gè)算法描述如下：A =0 1 1 1 10 0 1 0 00 0 0 1 11 1

30、0 0 00 0 1 1 0const int MaxVertices = 5;struct Graph /圖的鄰接矩陣表示int EdgeMaxVerticesMaxVertices; /有向圖鄰接距陣int CurrentNode; /有向圖當(dāng)前結(jié)點(diǎn)數(shù)int CurrentEdges; /當(dāng)前邊數(shù)int unknown ( int i ) int d = 0;for ( int j = 0; j < CurrentNode; j+) if ( Edgeij != 0 ) d+;if ( Edgeji != 0 ) d+;return d;(1) 若定義圖的一個(gè)對(duì)象Graph G，則執(zhí)

31、行操作G.unknown (3) 后的返回值是多少？(2) 試說明該算法的功能及時(shí)間復(fù)雜度。2. 已知有向圖的鄰接矩陣表示及其一個(gè)操作算法描述如下：A =0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0const int MaxVertices = 5;struct Graph /圖的鄰接矩陣表示int EdgeMaxVerticesMaxVertices; /有向圖鄰接距陣int CurrentNode; /有向圖當(dāng)前結(jié)點(diǎn)數(shù)int CurrentEdges; /當(dāng)前邊數(shù)void unknown ( int i ) int d, j;d = 0;for

32、 ( j = 0; j < CurrentNode; j+ ) if ( Edgeij ) d+; Edgeij = 0; if ( Edgeji ) d+; Edgeji = 0; CurrentEdges -= d;若定義圖的一個(gè)對(duì)象Graph G，試寫出執(zhí)行操作G.unknown (3) 后該圖的鄰接矩陣，并說明該算法的功能。3. 已知有向圖的鄰接表類的表示的形式描述如下：struct Edge /鄰接表中邊結(jié)點(diǎn)的定義int dest; /鄰接的結(jié)點(diǎn)float cost; /邊的權(quán)值Edge * link;template <class Type> struct Ver

33、tex /鄰接表中頂點(diǎn)的定義Type data;Edge *adj;template <class Type>struct Graph /鄰接表Vertex<Type> * NodeTable; /頂點(diǎn)表int NumVertices; /當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges; /當(dāng)前邊數(shù)int DegreeMaxVertices; /各個(gè)頂點(diǎn)的度的記錄數(shù)組/下列算法是計(jì)算有向圖中各個(gè)頂點(diǎn)的度，并保存在數(shù)組Degree 中。請?jiān)?處/填入合適的內(nèi)容，使其成為一個(gè)完整的算法。void FindDegree ( ) int i; Edge * p = NULL;for (

34、 i = 0; i < NumVertices; i+ ) Degreei = (1) ; for ( i = 0; i < NumVertices; i+) for ( p = NodeTablei.adj; p != NULL; p = p->link ) (2) ; (3) ; ;4. 已知有向圖的鄰接表類的表示的形式描述如下：struct Edge /鄰接表中邊結(jié)點(diǎn)的定義int dest; /鄰接的結(jié)點(diǎn)float cost; /邊的權(quán)值Edge * link;template <class Type> struct Vertex /鄰接表中頂點(diǎn)的定義Typ

35、e data;Edge *adj;template <class Type>struct Graph /鄰接表Vertex<Type> * NodeTable; /頂點(diǎn)表int NumVertices; /當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges; /當(dāng)前邊數(shù)int DegreeMaxVertices; /各個(gè)頂點(diǎn)的度的記錄數(shù)組/下列算法是計(jì)算有向圖G中一個(gè)頂點(diǎn)vi的入度。請?jiān)?處填入合適的內(nèi)容，/使其成為一個(gè)完整的算法。 void FindDegree ( int i ) int deg, j; Edge * p = NULL;deg = 0; for ( j = 0;

36、 j < NumVertices; j+ ) p = NodeTablej.adj; while ( (1) ) p = p->link;if ( p = NULL ) break; if ( p != NULL ) (2) ; return deg;5. 已知有向圖的鄰接表類的表示的形式描述如下：struct Edge /鄰接表中邊結(jié)點(diǎn)的定義int dest; /鄰接的結(jié)點(diǎn)float cost; /邊的權(quán)值Edge * link;template <class Type> struct Vertex /鄰接表中頂點(diǎn)的定義Type data;Edge *adj;temp

37、late <class Type>struct Graph /鄰接表Vertex<Type> * NodeTable; /頂點(diǎn)表int NumVertices; /當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges; /當(dāng)前邊數(shù)int DegreeMaxVertices; /各個(gè)頂點(diǎn)的度的記錄數(shù)組/下列算法是從有向圖G中刪除所有以vi為弧頭的有向邊。請?jiān)?處填入合適/的內(nèi)容，使其成為一個(gè)完整的算法。void DeletEdge ( int i ) int de = 0, j; Edge *p, *q; if ( i >= NumVertices ) cout <<

38、 "錯(cuò)誤輸入" << endl; exit (1); for ( j = 0; j < NumVertices; j+ ) p = NodeTablej.adj; while ( (1) ) q = p; p = p->link; if ( p != NULL ) if ( p != NodeTablej.adj ) q->link = p->link; else (2) ;delete p; de+; NumEdges = NumEdges - de;6. 已知帶權(quán)圖的鄰接矩陣表示和鄰接表類表示的形式描述分別如下：(1) 鄰接矩陣的定義

39、#define INFINITY INT_MAX/INT_MAX為最大整數(shù)，表示const int MaxVertices = 20;template <class Type> struct AdjMatrix Type * NodeTable;/頂點(diǎn)表定義float arrMaxverticesMaxVertices;/鄰接矩陣定義 int NumVertices; /當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges; /當(dāng)前邊數(shù);(2) 鄰接表定義struct Edge /鄰接表中邊結(jié)點(diǎn)的定義int dest; /鄰接的結(jié)點(diǎn)float cost; /邊的權(quán)值Edge * link;tem

40、plate <class Type> struct Vertex /鄰接表中頂點(diǎn)的定義Type data;Edge *adj;template <class Type>struct AdjTable /鄰接表Vertex<Type> * NodeTable; /頂點(diǎn)表int NumVertices; /當(dāng)前頂點(diǎn)個(gè)數(shù) int NumEdges; /當(dāng)前邊數(shù)/下列算法是根據(jù)一個(gè)圖的鄰接矩陣建立該圖的鄰接表，請?jiān)?處填入合適/的內(nèi)容，使其成為一個(gè)完整的算法。AdjTable<Type> * convertM ( ) /將圖的鄰接矩陣（用this指針指示

41、）轉(zhuǎn)換為鄰接表，函數(shù)返回鄰接表的地址。AdjTable<Type> * A; Edge *e;A->NodeTable = new Vertex<Type>NumVertices;A->NumEdges = NumEdges;A->NumVertices = NumVertices;for ( int i = 0; i < NumVertices; i+ ) A->NodeTablei.data = NodeTablei;A->NodeTablei.adj = (1) ;for ( int j = 0; j < NumVertices; j+ ) if ( arrij != INFINITY && arrij != 0 ) e = new Edge; e->dest = j; e->cost= (2) ;e->link = A->N