第7章-圖習題及參考答案.doc

第7章習題一、單項選擇題1. 在無向圖中定義頂點的度為與它相關(guān)聯(lián)的（ ）的數(shù)目。A. 頂點B. 邊C. 權(quán)D. 權(quán)值2. 在無向圖中定義頂點 vi與vj之間的路徑為從vi到達vj的一個（ ）。A. 頂點序列B. 邊序列C. 權(quán)值總和D. 邊的條數(shù)3. 圖的簡單路徑是指（ ）不重復的路徑。A. 權(quán)值B. 頂點C. 邊D. 邊與頂點均4. 設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)5. n個頂點的連通圖至少有（ ）條邊。A. n-1 B. nC. n+1D. 06. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。A. 3B. 2C. 1D. 1/27. 若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個 ( )。A. 上三角矩陣B. 稀疏矩陣C. 對角矩陣D. 對稱矩陣8. 圖的深度優(yōu)先搜索類似于樹的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次9. 圖的廣度優(yōu)先搜索類似于樹的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次10. 在用Kruskal算法求解帶權(quán)連通圖的最?。ù鷥r）生成樹時，選擇權(quán)值最小的邊的原則是該邊不能在圖中構(gòu)成（ ）。A. 重邊B. 有向環(huán)C. 回路D. 權(quán)值重復的邊11. 在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時，要求圖中每條邊所帶的權(quán)值必須是（ ）。A. 非零B. 非整C. 非負D. 非正12. 設(shè)G1 = (V1, E1) 和G2 = (V2, E2) 為兩個圖，如果V1 V2，E1 E2，則稱（ ）。 A. G1是G2的子圖 B. G2是G1的子圖 C. G1是G2的連通分量 D. G2是G1的連通分量13. 有向圖的一個頂點的度為該頂點的（ ）。 A. 入度 B. 出度C. 入度與出度之和 D. (入度出度)214. 一個連通圖的生成樹是包含圖中所有頂點的一個（ ）子圖。 A. 極小B. 連通C. 極小連通D. 無環(huán)15. n (n1) 個頂點的強連通圖中至少含有（ ）條有向邊。 A. n-1 B. nn(n-1)/2D. n(n-1)16. 在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的（ ）生成樹中。 A. 某個最小B. 任何最小C. 廣度優(yōu)先D.深度優(yōu)先17. 對于具有e條邊的無向圖，它的鄰接表中有（ ）個結(jié)點。 A. e-1B. e C. 2(e-1) D. 2e18. 對于如圖所示的帶權(quán)有向圖，從頂點1到頂點5的最短路徑為（ ）。 A.1, 4, 5B. 1, 2, 3, 5C. 1, 4, 3, 5D. 1, 2, 4, 3, 51261381955412319. 一個有n個頂點和n條邊的無向圖一定是（ ）。 A. 連通的 B. 不連通的 C. 無環(huán)的 D. 有環(huán)的20. 對于有向圖，其鄰接矩陣表示比鄰接表表示更易于（ ）。 A. 求一個頂點的度 B. 求一個頂點的鄰接點 C. 進行圖的深度優(yōu)先遍歷 D. 進行圖的廣度優(yōu)先遍歷21. 與鄰接矩陣相比，鄰接表更適合于存儲（ ）圖。 A. 無向B.連通C.稀疏 D. 稠密圖22. 為了實現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個輔助數(shù)據(jù)結(jié)構(gòu)是（ ）。 A. 棧 B. 隊列C. 二叉樹 D. 樹 二、填空題1. 用鄰接矩陣存儲圖，占用存儲空間數(shù)與圖中頂點個數(shù)_關(guān)，與邊數(shù)_關(guān)。2. n (n0) 個頂點的無向圖最多有_條邊，最少有_條邊。3. n (n0) 個頂點的連通無向圖最少有_條邊。4. 若3個頂點的圖G的鄰接矩陣為，則圖G一定是_向圖。5. n (n0) 個頂點的無向圖中頂點的度的最大值為_。6. (n0) 個頂點的連通無向圖的生成樹至少有_條邊。7. 在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時，只有當一條候選邊的兩個端點不在同一個_上，才有可能加入到生成樹中。8. 求解帶權(quán)連通圖最小生成樹的Prim算法適合于_圖的情形，而Kruskal算法適合于_圖的情形。三、判斷題1. 一個圖的子圖可以是空圖，頂點個數(shù)為0。2. 存儲圖的鄰接矩陣中，矩陣元素個數(shù)不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。3. 對一個連通圖進行一次深度優(yōu)先搜索（depth first search）可以遍訪圖中的所有頂點。4. 有n (n1) 個頂點的無向連通圖最少有n-1條邊。5. 如果無向圖中各個頂點的度都大于2，則該圖中必有回路。6. 如果有向圖中各個頂點的度都大于2，則該圖中必有回路。7. 圖的廣度優(yōu)先搜索（breadth first search）算法不是遞歸算法。8. 有n個頂點、e條邊的帶權(quán)有向圖的最小生成樹一般由n個頂點和n-1條邊組成。9. 對于一個邊上權(quán)值任意的帶權(quán)有向圖，使用Dijkstra算法可以求一個頂點到其它各個頂點的最短路徑。10. 有回路的有向圖不能完成拓撲排序。11. 對任何用頂點表示活動的網(wǎng)絡(luò)（AOV網(wǎng)）進行拓撲排序的結(jié)果都是唯一的。12. 用邊表示活動的網(wǎng)絡(luò)（AOE網(wǎng)）的關(guān)鍵路徑是指從源點到終點的路徑長度最長的路徑。13. 對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動就能使整個工程提前完成。14. 對于AOE網(wǎng)絡(luò)，任一關(guān)鍵活動延遲將導致整個工程延遲完成。15. 在AOE網(wǎng)絡(luò)中，可能同時存在幾條關(guān)鍵路徑，稱所有關(guān)鍵路徑都需通過的有向邊為橋。如果加速這樣的橋上的關(guān)鍵活動就能使整個工程提前完成。16. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。17. 鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。18. 鄰接矩陣只適用于稠密圖（邊數(shù)接近于頂點數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠小于頂點數(shù)的平方）19. 存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（上）三角部分就可以了。20. 連通分量是無向圖中的極小連通子圖。21. 在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。四、運算題V0V1V2V5V4V3V6V7V81. 設(shè)連通圖G如圖所示。試畫出該圖對應(yīng)的鄰接矩陣表示，并給出對它執(zhí)行從頂點V0開始的廣度優(yōu)先搜索的結(jié)果。V0V1V2V5V4V3V6V7V82. 設(shè)連通圖G如圖所示。試畫出該圖及其對應(yīng)的鄰接表表示，并給出對它執(zhí)行從V0開始的深度優(yōu)先搜索的結(jié)果。3. 對于如圖所示的有向圖，試寫出：(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹V1V2V3V4V7V6V0V54. 設(shè)有向圖G如圖所示。試畫出從頂點V0開始進行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的DFS生成森林和BFS生成森林。5. 設(shè)有一個連通網(wǎng)絡(luò)如圖所示。試按如下格式，應(yīng)用Kruskal算法給出在構(gòu)造最小生成樹過程中順序選出的各條邊。0123456618753426 ( 始頂點號，終頂點號， 權(quán)值 )( , , )( , , )( , , )( , , )( , , )6. 設(shè)有一個連通網(wǎng)絡(luò)如圖所示。試采用prim算法從頂點0開始構(gòu)造最小生成樹。（寫出加入生成樹頂點集合S和選擇邊Edge的順序）1234650910751187S:頂點號Edge:(頂點，頂點，權(quán)值)0( ， ， )0( ， ， )0 ( ， ， )0( ， ， )0( ， ， )0 7. 有八項活動, 每項活動要求的前驅(qū)如下:活動A0A1A2A3A4A5A6A7前驅(qū)無前驅(qū)A0A0A0, A2A1A2, A4A3A5, A6 (1) 試畫出相應(yīng)的AOV網(wǎng)絡(luò), 并給出一個拓撲排序序列。(2) 試改變某些結(jié)點的編號, 使得用鄰接矩陣表示該網(wǎng)絡(luò)時所有對角線以下的元素全為0。8. 試對下圖所示的AOE網(wǎng)絡(luò)(1) 這個工程最早可能在什么時間結(jié)束。 111151910223445566(2) 確定哪些活動是關(guān)鍵活動。畫出由所有關(guān)鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。9. 設(shè)帶權(quán)有向圖如圖所示。試采用Dijkstra算法求從頂點0到其他各頂點的最短路徑和最短路徑長度。 7182445912340第7章習題參考答案一、單項選擇題參考答案：1. B2.A3.B4.B5. A 6. B7. D8.A9.D10.C11. C12.A 13.C 14.C 15. B16. A17.D 18. D19.D 20.A21. C 22. B 二、填空題參考答案：1. 有, 無2. n(n-1)/2, 03. n-14. 有5. (n-1)6. n-17. 連通分量 8. 稠密，稀疏三、判斷題參考答案：1. 否2. 否3. 是4. 是5. 是6. 否7. 是8. 否9. 否10. 是11.否 12.是 13.否 14. 是15. 是16.是17.否18.是19.是20. 否 21.否四、運算題參考答案：1. 圖G對應(yīng)的鄰接矩陣為執(zhí)行廣度優(yōu)先搜索的結(jié)果為V0V1V3V2V4V7V6V5V8，搜索結(jié)果不唯一。2. 圖G對應(yīng)的鄰接表為：31320310350126766213780 V01 V12 V23 V34 V45 V56 V67 V78 V8執(zhí)行深度優(yōu)先搜索的結(jié)果為：V0V1V4V3V6V7V8V2V5，搜索結(jié)果不唯一。3. 以頂點 為根的深度優(yōu)先生成樹（不唯一）：以頂點 為根的廣度優(yōu)先生成樹：V1V2V3V4V7V6V0V5V1V2V3V4V7V6V0V54. 深度優(yōu)先生成森林為： 廣度優(yōu)先生成森林為：01234515342應(yīng)用Kruskal算法順序選出最小生成樹的各條邊為： ( 始頂點號，終頂點號， 權(quán)值 ) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )5. 采用prim算法從頂點0開始構(gòu)造最小生成樹的過程：S:頂點號Edge:(頂點，頂點，權(quán)值)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 12346509757A0A1A3A5A2A4A6A76. 相應(yīng)的AOV網(wǎng)絡(luò)為：一個拓撲排序序列為：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓撲排序結(jié)果不唯一。按拓撲有序的次序?qū)λ许旤c從新編號：原編號A0A1A4A2A5A3A6A7新編號A0A1A2A3A4A5A6A7相應(yīng)鄰接矩陣為：7. 針對下圖所示的AOE網(wǎng)絡(luò)111151910223445566各頂點（事件）的最早可能開始時間Ve(i)和最遲允許開始時間Vl(i)參看下表：頂點123456Ve01915293843Vl01915373843各邊（活動）的最早可能開始時間Ee(k)和最遲允許開始時間El(k)參看下表：邊Ee00151915192938El170151927273738如果活動k的最早可能開始時間Ee(k) 與最遲允許開始時間El(k)相等，則該活動是關(guān)鍵活動。本題的關(guān)鍵活動為, , , ，它們組成關(guān)鍵路徑。這些關(guān)鍵活動中任一個提前完成，整個工程就能提前完成。整個工程最早在43天完成。由關(guān)鍵活動組成的AOV網(wǎng)絡(luò)如圖所示。11115191022344556671824459123408. 帶權(quán)有向圖如圖所示： 應(yīng)用Dijkstra算法求從頂點V0到其他各頂點的最短路徑Path和最短路徑