圖習(xí)題及參考答案

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

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

3、。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-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n 個(gè)頂點(diǎn)的連通圖至少有（）條邊。A.n-1B.nC.n+1D.06.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A.3B.2C.1D.1/2）的數(shù)目。1.7.若采用鄰接矩陣法存儲(chǔ)一個(gè) n 個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)（、單項(xiàng)選擇題在無(wú)向圖中定義頂點(diǎn)的度為與它相關(guān)聯(lián)的（8.A.上三角矢 I 陣 B.稀疏矩陣圖的深度優(yōu)先搜索類似于樹(shù)的（A.

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

5、，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ú)向圖最少有條邊。0104 .若 3 個(gè)頂點(diǎn)的圖 G 的鄰接矩陣為卜00，則圖 G 一定是向圖。，10一5 .n（n0）個(gè)頂點(diǎn)的無(wú)向圖中頂點(diǎn)的度的最大值為。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)連通圖最小生成

6、樹(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)先搜索（depthfirstsearch）可以遍訪圖中的所有頂點(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)先搜索（breadthfirstsearch）算法不是遞歸算法。8 .有 n 個(gè)頂點(diǎn)、e

7、條邊的帶權(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ò)的有向

8、邊為橋。如果加速這樣的橋上的關(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)算題1.設(shè)連通圖 G 如圖所示。試畫出該圖對(duì)應(yīng)的鄰接矩陣表示

9、，并給出對(duì)它執(zhí)行從頂點(diǎn)搜索的結(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ù)4 .設(shè)有向圖 G 如圖所示。試畫出從頂點(diǎn) V。開(kāi)始進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的 DFS 生成森林和 BFS 生成森林。V0開(kāi)始的廣度優(yōu)先2.設(shè)連通圖 G 如圖所示。試畫出該圖及其對(duì)應(yīng)的鄰接表表示，并給出對(duì)它執(zhí)行從V0開(kāi)始的深度優(yōu)先搜索的結(jié)果。5.設(shè)有一個(gè)連通網(wǎng)絡(luò)如圖所示。試按如下格式，應(yīng)用出的各條邊。Kruskal 算法給出在構(gòu)造最小生成樹(shù)過(guò)程中順序選(始頂點(diǎn)號(hào)，終頂點(diǎn)號(hào)，權(quán)值)(,)(,)(,)(,)(,

10、)S:頂點(diǎn)號(hào)Edge:(頂點(diǎn),頂點(diǎn)，權(quán)值)0(,)0(,)0(,)0(,)0(,)07 .有八項(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é)束。(2)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。9 .設(shè)帶權(quán)有向圖如圖所示。試采用 Dijkstra 算法求從頂點(diǎn)6.設(shè)有

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

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

13、始構(gòu)造最小生成樹(shù)的過(guò)程:S:頂點(diǎn)號(hào)Edge:（頂點(diǎn),頂點(diǎn)，權(quán)值）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.應(yīng)用 Kruskal 算法順序選出最小生成樹(shù)的各條邊為：（始頂點(diǎn)號(hào)，終頂點(diǎn)號(hào)，權(quán)值）6.相應(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)鄰接

14、矩陣為:3456710100-00000017.針對(duì)下圖所示的Edge=0010030014010500160007各頂點(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í)間日(k)相等，則該活動(dòng)是關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)為,它們組成關(guān)鍵路徑。這些關(guān)鍵活動(dòng)中任一個(gè)提前完成，整個(gè)工程就能提前完成。本題的網(wǎng)絡(luò)AOE整個(gè)工程最早在 43 天完成。由關(guān)鍵活動(dòng)組成的 AOV 網(wǎng)絡(luò)如圖所示。V0到其他各頂點(diǎn)的最短路徑 Path 和最短路徑長(zhǎng)度 Len 的步驟如下:步驟V0VIV2V3V4動(dòng)作PathLenPathLenPathLenPathLen1V0V140