數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題(存儲版)
【正文】 Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表示圖時(shí)計(jì)算時(shí)間約為10ms，則在圖的頂點(diǎn)數(shù)為40時(shí)，計(jì)算時(shí)間約為_________ms。8．連通分量是無向圖的極小連通子圖。16．最小生成樹是指邊數(shù)最小的生成樹。24．在AOE網(wǎng)中，減小任一關(guān)鍵活動上的權(quán)值后，整個(gè)工期也就相應(yīng)減小。并在給定的鄰接表基礎(chǔ)上，指出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。表2 某工程各工序關(guān)系表工序代號 A B C D E F G H I J K L M N所需時(shí)間 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驅(qū)工作 A,B B C,D B E G,I E I F,I H,J,K L G完成如下各小題：（1）畫出相應(yīng)的AOE網(wǎng)（2）列出事件的最早發(fā)生時(shí)間，最遲發(fā)生時(shí)間。2．假設(shè)圖G采用鄰接矩陣存儲，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。7．假設(shè)圖采用鄰接表存儲，分別寫出基于DFS和BPS遍歷的算法來判別頂點(diǎn)i和頂點(diǎn)j（i!=j）之間是否有路徑。若有向圖中存在一個(gè)頂點(diǎn)v，從v可以通過路徑達(dá)達(dá)圖中其它所有頂點(diǎn)，則稱v為該有向圖的根。設(shè)v是有向圖G的一個(gè)頂點(diǎn)，把v的偏心度定義為：MAX{從w到v的最短距離|wV(G)}如果v是有向圖G中具有最小偏心度的頂點(diǎn)，則稱頂點(diǎn)v是G的中心點(diǎn)。（1）給出該圖的鄰接表定義（2）定義在算法中使用的全局輔助數(shù)組（3）寫出逆向拓?fù)渑判虻乃惴?。若鄰接表的?shù)據(jù)類型定義為AGraph，則算法的首部為：void dfs_topsort(AGraph *G) 若拓?fù)渑判虺晒?，表示圖中不存在環(huán)；否則表示圖中存在環(huán)。6364255651103452 圖711 城市連通圖16．利用狄克斯特拉算法，設(shè)計(jì)一個(gè)可產(chǎn)生從指定頂點(diǎn)出發(fā)的最小生成樹的算法。（3）給定一組必避點(diǎn){1,6}，即輸出的路徑不能包含這些頂點(diǎn)。5．設(shè)計(jì)一個(gè)算法，求不帶權(quán)無向連通圖G中距離頂點(diǎn)v的最遠(yuǎn)頂點(diǎn)。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。39822 127153426512 12 15131344313204圖77 一個(gè)有向圖 圖78一個(gè)有向圖 12．設(shè)圖78中的頂點(diǎn)表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪個(gè)村莊能使個(gè)村莊總體交通代價(jià)最小。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。22．任何有向無環(huán)圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃┮弧?4．連通圖的生成樹包含了圖中所有頂點(diǎn)。6．如果表示有向圖的鄰接矩陣是對稱矩陣，則該有向圖一定是有向完全圖。16．從源點(diǎn)到匯點(diǎn)長度最長的路徑稱為關(guān)鍵路徑，該路徑上的活動稱為________。8．對于n個(gè)頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是__________。A．在AOE網(wǎng)中，減少任一關(guān)鍵活動的權(quán)值后，整個(gè)工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動的權(quán)值和C．在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必須在關(guān)鍵路徑上D．A和B31．下面說法不正確的是______。C．由n1條權(quán)值之和最小的邊構(gòu)成的連通子圖。A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3 D．v1，v2，v5，v3，v4 234 ∧35 ∧5 ∧4 ∧v1v2v3v4 ∧v5圖71 一個(gè)有向圖的鄰接表19．對圖72所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問序列______。A．入邊
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1