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

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