第7章-圖習(xí)題及參考答案.doc

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