《數(shù)據(jù)結(jié)構(gòu)》習(xí)題匯編07-第七章-圖-試題

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

2、點(diǎn)的度數(shù)之和等于所有邊數(shù)的 （）A. 3B. 2C. 1倍。D. 1/27. 若采用鄰接矩陣法存儲一個(gè)n 個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè)（）A. 上三角矩陣B. 稀疏矩陣8. 圖的深度優(yōu)先搜索類似于樹的（A. 先根B. 中根9. 圖的廣度優(yōu)先搜索類似于樹的（A. 先根B. 中根C. 對角矩陣D. 對稱矩陣）次序遍歷。C. 后根D. 層次）次序遍歷。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、在圖中構(gòu)成（A. 重邊12. 在 用 Dijkstra()。A. 非零算法求解帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹時(shí)，選擇權(quán)值最小的邊的原則是該邊不能）。B. 有向環(huán)C. 回路D. 權(quán)值重復(fù)的邊算法求解帶權(quán)有向圖的最短路徑問題時(shí)，要求圖中每條邊所帶的權(quán)值必須是C. 非整C. 非負(fù) D. 非正13. 在 一個(gè)連通圖中進(jìn)行深度優(yōu)先搜索得到一棵深度優(yōu)先生成樹，樹根結(jié)點(diǎn)是關(guān)節(jié)點(diǎn)的充要條件是它至少有（ ）子女。A. 1B. 2C. 3D. 015.設(shè)有向圖有n個(gè)頂點(diǎn)和( )。A. O(nlog 2e)16.設(shè) G1=(V1,E1) 和 G2 = (V2,E2)A. G1 是G2的子圖C. G1 是G2的連通分

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

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

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

7、. 設(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(n 2)30. 為 了實(shí)現(xiàn)圖的廣度優(yōu)先遍歷， BFS 算法使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)是( ) 。A.棧B. 隊(duì)列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、義包含一個(gè)頂點(diǎn)集合和一個(gè)邊集合。其中，頂點(diǎn)集合是一個(gè)有窮 集合。2. 用鄰接矩陣存儲圖，占用存儲空間數(shù)與圖中頂點(diǎn)個(gè)數(shù) 關(guān)，與邊數(shù) 關(guān)。3. n (n 0)個(gè)頂點(diǎn)的無向圖最多有 條邊，最少有 條邊。4. n (n 0)個(gè)頂點(diǎn)的連通無向圖最少有 條邊。0101005. 若3個(gè)頂點(diǎn)的圖G的鄰接矩陣為 01 0 ,則圖G一定是 向圖。6. n (n 0)個(gè)頂點(diǎn)的連通無向圖各頂點(diǎn)的度之和最少為 。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)先序

9、列有 種，例如 8. 設(shè)圖 G = (V, E) ， V = P, Q, R, S, T, E = , , , 從頂點(diǎn) P 出發(fā)，對圖 G 進(jìn)行廣度優(yōu)先搜索所得的所有序列為 和9. n (n 0)個(gè)頂點(diǎn)的無向圖中頂點(diǎn)的度的最大值為 。10. 在 重連通圖中每個(gè)頂點(diǎn)的度至少為 。11. 在 非重連通圖中進(jìn)行深度優(yōu)先搜索，則深度優(yōu)先生成樹的根為關(guān)節(jié)點(diǎn)的充要條件是它至少有 個(gè)子女。12. (n0)個(gè)頂點(diǎn)的連通無向圖的生成樹至少有 條邊。13. 1 01 個(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 的最小生成樹

10、各邊的權(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. 求解最短路徑的 Dijkstra 算法適用于各邊上的權(quán)值 的情形。若設(shè)圖的頂點(diǎn)數(shù)為 n ，則該算法的時(shí)間復(fù)雜度為 。18. 若 對一個(gè)有向無環(huán)圖進(jìn)行拓?fù)渑判颍賹ε旁谕負(fù)溆行蛐蛄兄械乃许旤c(diǎn)按其先后次序重新編號，則在相應(yīng)的鄰接矩陣中所有 元素將集中到對角線以上。參考答案： 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. 非負(fù)， O(n2)9. n-110. 212. n-113. 55015. 高16. 稠密，稀疏18. 非零(或值為 1 的)三、判斷題1. 一個(gè)圖的子圖可以是空圖，頂點(diǎn)個(gè)數(shù)為 0 。2. 存儲圖的鄰接矩陣中，矩陣元素個(gè)數(shù)不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。3. 一個(gè)有 1000 個(gè)頂點(diǎn)和 1000 條邊的有向圖的鄰接矩陣是一個(gè)稀疏矩陣

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

13、eadth first searchn 個(gè)頂點(diǎn)和 n-1 條邊組成。算法可以求一個(gè)頂點(diǎn)到其它各個(gè)頂點(diǎn)的最短路） ，一定可以將圖的所有頂點(diǎn)按其關(guān)鍵碼大小12. 有 n 個(gè)頂點(diǎn)、 e 條邊的帶權(quán)有向圖的最小生成樹一般由13. 對 于一個(gè)邊上權(quán)值任意的帶權(quán)有向圖，使用 Dijkstra徑。14. 對 一個(gè)有向圖進(jìn)行拓?fù)渑判颍╰opological sorting排列到一個(gè)拓?fù)溆行虻男蛄兄小?5. 有 回路的有向圖不能完成拓?fù)渑判颉?6. 對任何用頂點(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)的路徑長度最長的路徑。

14、18. 對 于 AOE 網(wǎng)絡(luò)，加速任一關(guān)鍵活動(dòng)就能使整個(gè)工程提前完成。19. 對 于 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. 用 鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。22. 鄰 接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。23. 鄰 接矩陣只適用于稠密圖 （邊數(shù)接近于頂點(diǎn)數(shù)的平方） ， 鄰接表適用于稀疏圖 （邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平 方）24

15、. 存 儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（上）三角部分就可以了。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.是27.否四、運(yùn)算題1.設(shè)連通圖G如圖所示。試畫出該圖對應(yīng)的鄰接矩陣表示，并給出對它執(zhí)行從頂點(diǎn)V0開始的廣度優(yōu)先搜索的結(jié)果。2.設(shè)連通圖G如圖所示。試畫出該圖及其對應(yīng)的鄰接表表示，并給出

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

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

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

19、如下所示的圖G為例，畫出構(gòu)造出最小生成樹及其鄰接矩陣，并在括號內(nèi)填入每次選擇的邊和可能去掉的邊。0 160Edge14 215919060 18 110260選擇的邊掉的（頂點(diǎn), 頂權(quá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è)拓?fù)渑判蛐蛄小?2)試改變某些結(jié)點(diǎn)的編號，使得用鄰接矩陣表示該網(wǎng)絡(luò)時(shí)所有對角

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

21、，請問該有向圖是否為強(qiáng)連通圖，并畫出該有向圖所有的強(qiáng)連通分量。參考答案1.圖G對應(yīng)的鄰接矩陣為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)先搜索的結(jié)果為V0V1V3V2V4V7V6V5V8 ,搜索結(jié)果不唯一。2 .圖G對應(yīng)的鄰接表為:012345678執(zhí)行深度優(yōu)先搜索的結(jié)果為：V0V1V4V3V6V7V8V2V5 ,搜索結(jié)果不唯一。3 .圖G中，從V

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

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

24、0161421160591950660181114026110EdgeS頂點(diǎn)號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選擇的邊去掉的邊（頂點(diǎn)，頂 權(quá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)(4 ,2 ,9)(5 ,4 ,18)(

25、3 ,2 ,5)(,)(4 ,6)(4 ,2 ,9)3 ,選擇順序不唯一。11.相應(yīng)的AOV網(wǎng)絡(luò)為:一個(gè)拓?fù)渑判蛐蛄袨椋篈0,A1,A4,A2,A5,A3,A6,A7。 注意：拓?fù)渑判蚪Y(jié)果不唯一。按拓?fù)溆行虻拇涡驅(qū)λ许旤c(diǎn)從新編號：原編號A0A1A4A2A5A3A6A7新編號A0A1A2A3A4A5A6A7相應(yīng)鄰接矩陣為:Edge0 12 3 40 10 100 0 10 00 0 0 0 1567100000010002010500 1600 07各頂點(diǎn)(事件)的最早可能開始時(shí)間Ve(i)和最遲允許開始時(shí)間Vl(i)參看下表:頂點(diǎn)123456Ve01915293843Vl0191537384

26、3各邊(活動(dòng))的最早可能開始時(shí)間Ee(k)和最遲允許開始時(shí)間El(k)參看下表：邊Ee00151915192938El170151927273738如果活動(dòng)k的最早可能開始時(shí)間 Ee(k)與最遲允許開始時(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ò)如圖所示。13.帶權(quán)有向圖如圖所示:應(yīng)用Dijkstra算法求從頂點(diǎn)V0到其他各頂點(diǎn)的最短路徑Path和最短路徑長度Len的步驟如下:步 驟V0V1V2V3V4動(dòng)作PatherLIPatheL nPathe

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

28、3, p2, p615 .該圖的強(qiáng)連通分量分別為:五、算法分析題1 .已知有向圖的鄰接矩陣表示及其一個(gè)算法描述如下:01111、001000001111000*00110，A =/圖的鄰接矩陣表示有向圖鄰接距陣/有向圖當(dāng)前結(jié)點(diǎn)數(shù)/當(dāng)前邊數(shù)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)若定義圖的一個(gè)對象Graph G ,則執(zhí)行操作 G.unknown (3)后的返回值是多少?(2)試說明該算法的功能及時(shí)間復(fù)雜度。2 .已知有向圖的鄰接矩陣表示及其一個(gè)操作算法描述如下:0 10 0A = 0 01 110 01 0 1、0 0 00 1 10 0 00 1 0 )const int MaxVertices = 5;/圖的鄰接矩陣表示有向圖鄰接距陣/有向圖當(dāng)前結(jié)點(diǎn)數(shù)/當(dāng)前邊數(shù)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;后該圖的鄰接矩陣，并說明該算若定義圖的一個(gè)對象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; / 鄰接表中邊結(jié)點(diǎn)的定義/ 鄰接的結(jié)點(diǎn)/ 邊的權(quán)值/ 鄰接表中頂點(diǎn)的定義/ 鄰接表/ 頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)/ 各個(gè)頂點(diǎn)的度的記錄數(shù)組/ 下列算法是計(jì)算有向圖中各個(gè)頂點(diǎn)的度，并保存在數(shù)組 Degree 中。請?jiān)谔? 填入合適的內(nèi)容，使其成為一個(gè)完整的算法。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;/ 鄰接表中邊結(jié)點(diǎn)的定義/ 鄰接的結(jié)點(diǎn)/ 邊的權(quán)值;Edge * link;template struct Vertex / 鄰接表中頂點(diǎn)的定義Type data;Edge *adj;template struct Graph / 鄰接表Vertex * NodeTable; int NumVertices;int NumE

33、dges;/ 頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)int DegreeMaxVertices;/ 各個(gè)頂點(diǎn)的度的記錄數(shù)組/ 下列算法是計(jì)算有向圖 G 中一個(gè)頂點(diǎn) vi 的入度。請?jiān)? 使其成為一個(gè)完整的算法。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;處填入合適的內(nèi)容，5. 已知有向圖的鄰接表類的表示的形式描述如下：struct Edge int dest; float co

34、st; Edge * link;/ 鄰接表中邊結(jié)點(diǎn)的定義/ 鄰接的結(jié)點(diǎn)/ 邊的權(quán)值;template struct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;int NumVertices;/ 鄰接表中頂點(diǎn)的定義/ 鄰接表/ 頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)int NumEdges;/ 當(dāng)前邊數(shù)int DegreeMaxVertices;/ 各個(gè)頂點(diǎn)的度的記錄數(shù)組/ 下列算法是從有向圖 G 中刪除所有以 vi 為弧頭的有向邊。請?jiān)谔幪钊牒线m/ 的內(nèi)容，使其成為一個(gè)完整的算法。void DeletEdge ( i

35、nt i ) int de = 0, j; Edge *p, *q;if ( i = NumVertices ) cout 錯(cuò)誤輸入 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.已知帶權(quán)圖的鄰接矩陣表示和鄰接表類表示的形式描述分別如下:(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 為最大整數(shù)，表示8/ 頂點(diǎn)表定義/ 鄰接矩陣定義/

37、當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)/ 鄰接表中邊結(jié)點(diǎn)的定義/ 鄰接的結(jié)點(diǎn)/ 邊的權(quán)值/ 鄰接表中頂點(diǎn)的定義/ 鄰接表/ 頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)處填入合適int NumEdges; / 下列算法是根據(jù)一個(gè)圖的鄰接矩陣建立該圖的鄰接表，請?jiān)? 的內(nèi)容，使其成為一個(gè)完整的算法。AdjTable * convertM ( ) / 將圖的鄰接矩陣(用 this 指針指示)轉(zhuǎn)換為鄰接表，函數(shù)返回鄰接表的地址。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. 已知帶權(quán)圖的鄰接矩陣表示和鄰接表類表示的形式描述分別如下：(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 為最大整數(shù)，表示8/ 頂點(diǎn)表定義/ 鄰接矩陣定義/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)/ 鄰接表中邊結(jié)點(diǎn)的定義/ 鄰接的結(jié)點(diǎn)/ 邊的權(quán)值/ 鄰

40、接表中頂點(diǎn)的定義/ 鄰接表/ 頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)/ 下列算法是根據(jù)一個(gè)圖的鄰接表存儲結(jié)構(gòu)建立該圖的鄰接矩陣存儲結(jié)構(gòu)，/ 請?jiān)谔幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法AdjMatrix * convertAL( ) / 將圖的鄰接表(用 this 指針指示)轉(zhuǎn)換為鄰接矩陣，函數(shù)返回鄰接矩陣的地址。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;/ 結(jié)點(diǎn)定義/ 鄰接結(jié)點(diǎn)/ 邊的權(quán)值/ 頂點(diǎn)定義/ 鄰接表與逆鄰接表定義/ 鄰接表頂點(diǎn)表/ 逆鄰接表頂點(diǎn)表/ 當(dāng)前頂點(diǎn)個(gè)數(shù)/ 當(dāng)前邊數(shù)/ 下列算法是根據(jù)一個(gè)圖的鄰接表存儲結(jié)構(gòu)建立該圖的逆鄰接表存儲結(jié)構(gòu)，請/ 在處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。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)算法的功能是計(jì)算有向圖中一個(gè)頂點(diǎn)的度。/2分算法的時(shí)間復(fù)雜度是 O(n) , n為圖的頂點(diǎn)個(gè)數(shù)。/2 分2 .執(zhí)行操作G.unknown (3) 后，圖的鄰接矩陣為：/3分10 110 1、00000000010000000000 J算法的功能是從圖中刪除所有與某個(gè)頂點(diǎn)相關(guān)的邊。/3分3 .填空結(jié)果8.填空結(jié)果30 0/2(2) Degreep-dest+(3) Degreei+4 .填空結(jié)果(1) p != NULL & p-dest