圖習題及參考答案

1、A.非零B.非整C.非負D.非正12.設 G1=(V1,E1)和 G2=(V2,E2)13.A.GI是 G2的子圖C.GI是 G2的連通分量有向圖的一個頂點的度為該頂點的（A.入度C.入度與出度之和為兩個圖，如果 V11V2,E11E2,則稱（B. G2是GI的子圖D.G2是GI的連通分量）B.出度D.（入度+出度14. 一個連通圖的生成樹是包含圖中所有頂點的一個（A.極小B.連通C.極小連通）/2）子圖。D.無環(huán)15. n（n1）個頂點的強連通圖中至少含有（A. n-1B. n）條有向邊。n（n-1）/216. 在一個帶權連通圖 G 中，權值最小的邊一定包含在 G 的（A.某個最小B.任何最

2、小C.廣度優(yōu)先D.n（n-1）生成樹中。D.深度優(yōu)先17. 對于具有 e 條邊的無向圖，它的鄰接表中有（A.e-1B.e)個結點。C. 2(e-1)D.2e18. 對于如圖所示的帶權有向圖，從頂點到頂點 5 的最短路徑為（A.1,4,5C.1,4,3,5D. 1,2,4,3,5第7章習題10 .在用 Kruskal 算法求解帶權連通圖的最?。ù鷥r）生成樹時，選擇權值最小的邊的原則是該邊不能在11 .在用 Dijkstra 算法求解帶權有向圖的最短路徑問題時，要求圖中每條邊所帶的權值必須是（A.頂點B.邊C. 權D.權值2.在無向圖中定義頂點 v， i與Vj之間的路徑為從Vi到達 Vj的一個（）

3、。A.頂點序列B.邊序列C.權值總和D.邊的條數3.圖的簡單路徑是指（）不重復的路徑。A.權值B.頂點C.邊D.邊與頂點均4.設無向圖的頂點個數為n,則該圖最多有（）條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n 個頂點的連通圖至少有（）條邊。A.n-1B.nC.n+1D.06.在一個無向圖中，所有頂點的度數之和等于所有邊數的（）倍。A.3B.2C.1D.1/2）的數目。1.7.若采用鄰接矩陣法存儲一個 n 個頂點的無向圖，則該鄰接矩陣是一個（、單項選擇題在無向圖中定義頂點的度為與它相關聯的（8.A.上三角矢 I 陣 B.稀疏矩陣圖的深度優(yōu)先搜索類似于樹的（A.

4、先根B.中根9.圖的廣度優(yōu)先搜索類似于樹的（A.先根B.中根C.對角矩陣）次序遍歷。C.后根）次序遍歷。C.后根D.對稱矩陣D.層次D.層次圖中構成（A.重邊）B.有向環(huán)C.回路D.權值重復的邊B.1,2,3,54953619 .一個有 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 .為了實現圖的廣度優(yōu)先遍歷

5、，BFS 算法使用的一個輔助數據結構是（）。A.棧 B.隊列 C.二叉樹 D.樹二、填空題1 .用鄰接矩陣存儲圖，占用存儲空間數與圖中頂點個數關，與邊數關。2 .n（n0）個頂點的無向圖最多有條邊，最少有條邊。3 .n（n0）個頂點的連通無向圖最少有條邊。0104 .若 3 個頂點的圖 G 的鄰接矩陣為卜00，則圖 G 一定是向圖。，10一5 .n（n0）個頂點的無向圖中頂點的度的最大值為。6 .（n0）個頂點的連通無向圖的生成樹至少有條邊。7 .在使用 Kruskal 算法構造連通網絡的最小生成樹時，只有當一條候選邊的兩個端點不在同一個上，才有可能加入到生成樹中。8 .求解帶權連通圖最小生成

6、樹的 Prim 算法適合于圖的情形，而 Kruskal 算法適合于圖的情形。三、判斷題1 .一個圖的子圖可以是空圖，頂點個數為 0。2 .存儲圖的鄰接矩陣中，矩陣元素個數不但與圖的頂點個數有關，而且與圖的邊數也有關。3 .對一個連通圖進行一次深度優(yōu)先搜索（depthfirstsearch）可以遍訪圖中的所有頂點。4 .有 n（n1）個頂點的無向連通圖最少有 n-1 條邊。5 .如果無向圖中各個頂點的度都大于 2,則該圖中必有回路。6 .如果有向圖中各個頂點的度都大于 2,則該圖中必有回路。7 .圖的廣度優(yōu)先搜索（breadthfirstsearch）算法不是遞歸算法。8 .有 n 個頂點、e

7、條邊的帶權有向圖的最小生成樹一般由 n 個頂點和 n-1 條邊組成。9 .對于一個邊上權值任意的帶權有向圖，使用 Dijkstra 算法可以求一個頂點到其它各個頂點的最短路徑。10 .有回路的有向圖不能完成拓撲排序。11 .對任何用頂點表示活動的網絡（AOV 網）進行拓撲排序的結果都是唯一的。12 .用邊表示活動的網絡（AOE 網）的關鍵路徑是指從源點到終點的路徑長度最長的路徑。13 .對于 AOE 網絡，加速任一關鍵活動就能使整個工程提前完成。14 .對于 AOE 網絡，任一關鍵活動延遲將導致整個工程延遲完成。15 .在 AOE 網絡中，可能同時存在幾條關鍵路徑，稱所有關鍵路徑都需通過的有向

8、邊為橋。如果加速這樣的橋上的關鍵活動就能使整個工程提前完成。16 .用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數有關，而與圖的邊數無關。17 .鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。18 .鄰接矩陣只適用于稠密圖（邊數接近于頂點數的平方），鄰接表適用于稀疏圖（邊數遠小于頂點數的平方）19 .存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（上）三角部分就可以了。20 .連通分量是無向圖中的極小連通子圖。21 .在 AOE 網絡中一定只有一條關鍵路徑。四、運算題1.設連通圖 G 如圖所示。試畫出該圖對應的鄰接矩陣表示

9、，并給出對它執(zhí)行從頂點搜索的結果。3 .對于如圖所示的有向圖，試寫出:(1)從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹;(2)從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹4 .設有向圖 G 如圖所示。試畫出從頂點 V。開始進行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的 DFS 生成森林和 BFS 生成森林。V0開始的廣度優(yōu)先2.設連通圖 G 如圖所示。試畫出該圖及其對應的鄰接表表示，并給出對它執(zhí)行從V0開始的深度優(yōu)先搜索的結果。5.設有一個連通網絡如圖所示。試按如下格式，應用出的各條邊。Kruskal 算法給出在構造最小生成樹過程中順序選(始頂點號，終頂點號，權值)(,)(,)(,)(,)(,

10、)S:頂點號Edge:(頂點,頂點，權值)0(,)0(,)0(,)0(,)0(,)07 .有八項活動，每項活動要求的前驅如下活動A0A1A2A3A4A5A6A7前驅無前驅A0A0A0,A2A1A2,A4A3A5,A6(1)試畫出相應的 AOV 網絡，并給出一個拓撲排序序列。(2)試改變某些結點的編號，使得用鄰接矩陣表示該網絡時所有對角線以下的元素全為 0。8 .試對下圖所示的 AOE 網絡(1)這個工程最早可能在什么時間結束。(2)確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程提前完成。9 .設帶權有向圖如圖所示。試采用 Dijkstra 算法求從頂點6.設有

11、一個連通網絡如圖所示。試采用集合 S 和選擇邊 Edge 的順序)prim 算法從頂點 0 開始構造最小生成樹。(寫出加入生成樹頂點0 到其他各頂點的最短路徑和最短路徑長度。第7章習題參考答案一、單項選擇題參考答案：1.B2.A3.B4.B5.A6.B7.D8.A9.D10.C11.C12.A13.C14.C15.B16.A17.D18.D19.D20.A21.C22.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.

12、否14.是15.是16.是 17.否 18.是 19.是 20.否 21.否四、運算題參考答案：執(zhí)行廣度優(yōu)先搜索的結果為 V0V1V3V2V4V7V6V5V8,搜索結果不唯一。2 .圖 G 對應的鄰接表為：1.圖 G 對應的鄰接矩陣為G.Edge=0111010011000100101001000001100001010000001100000000000001000111001000001000123456執(zhí)行深度優(yōu)先搜索的結果為：V0V1V4V3V6V7V8V2V5,搜索結果不唯一。3 .以頂點為根的深度優(yōu)先生成樹（不唯一）：以頂點為根的廣度優(yōu)先生成樹5.采用 prim 算法從頂點 0 開

13、始構造最小生成樹的過程:S:頂點號Edge:（頂點,頂點，權值）0(0,19)0,1(13,5)0,1,3(12,7)0,1,3,2(2,4,6)0,1,3,2,4(2,5,7)0,1,3,2,4,5(0,3,1)(2,5,2)(1,4,3)(3,5,4)(3,4,5)4.應用 Kruskal 算法順序選出最小生成樹的各條邊為：（始頂點號，終頂點號，權值）6.相應的 AOV 網絡為:一個拓撲排序序列為：A0,A1,A4,A2,A5,A3,A6,A7。注意：拓撲排序結果不唯一。按拓撲有序的次序對所有頂點從新編號：原編號A0A1A4A2A5A3A6A7新編號A0A1A2A3A4A5A6A7相應鄰接

14、矩陣為:3456710100-00000017.針對下圖所示的Edge=0010030014010500160007各頂點(事件)的最早可能開始時間Ve(i)和最遲允許開始時間 Vl(i)參看下表:頂點123456Ve01915293843Vl01915373843各邊(活動)的最早可能開始時間Ee(k)和最遲允許開始時間El(k)參看卜表邊Ee00151915192938El170151927273738如果活動 k 的最早可能開始時間 Ee(k)與最遲允許開始時間日(k)相等，則該活動是關鍵活動。關鍵活動為,它們組成關鍵路徑。這些關鍵活動中任一個提前完成，整個工程就能提前完成。本題的網絡AOE整個工程最早在 43 天完成。由關鍵活動組成的 AOV 網絡如圖所示。V0到其他各頂點的最短路徑 Path 和最短路徑長度 Len 的步驟如下:步驟V0VIV2V3V4動作PathLenPathLenPathLenPathLen1V0V140