數(shù)據(jù)結(jié)構(gòu)第7章圖習題-文庫吧資料
2025-03-31 03:01本頁面
【正文】 1 182 223 163 22 23 44 10 ∧1.2.34.5圖76 連通圖的鄰接表10．已知世界6大城市為：北京（B）紐約（N）巴黎（P）倫敦（L）東京（T）墨西哥城（M）試用由表1給出的交通網(wǎng)確定最小生成樹，并說明所使用的方法及其時間復雜度。 （2）鄰接表 （3）強連通分量（4）對照鄰接表，給出從頂點1出發(fā)的深度優(yōu)先遍歷序列。并在給定的鄰接表基礎(chǔ)上，指出從頂點1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。28．所有關(guān)鍵活動都提前完成，則整個工程將提前完成。26．在關(guān)鍵路徑的活動都是關(guān)鍵活動，而關(guān)鍵活動未必在關(guān)鍵路徑上。24．在AOE網(wǎng)中，減小任一關(guān)鍵活動上的權(quán)值后，整個工期也就相應減小。22．任何有向無環(huán)圖的結(jié)點都可以排成拓撲排序，而且拓撲序列不惟一。20．有環(huán)圖也能進行拓撲排序。18．只要無向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是惟一的。16．最小生成樹是指邊數(shù)最小的生成樹。14．連通圖的生成樹包含了圖中所有頂點。12．圖的深度優(yōu)先搜索中一般要采用棧來暫時剛訪問過的頂點。10．對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個頂點，則該圖一定是完全圖。8．連通分量是無向圖的極小連通子圖。6．如果表示有向圖的鄰接矩陣是對稱矩陣，則該有向圖一定是有向完全圖。4．對同一個有向圖，只保存出邊的鄰接表中結(jié)點的數(shù)目總是和只保存入邊的鄰接表中結(jié)點的數(shù)目一樣多。2．有向圖中各頂點的入度之和等于各頂點的出度之和。18．求從某源點到其余各項點的Dijkstra算法在圖的頂點數(shù)為10，用鄰接矩陣表示圖時計算時間約為10ms，則在圖的頂點數(shù)為40時，計算時間約為_________ms。16．從源點到匯點長度最長的路徑稱為關(guān)鍵路徑，該路徑上的活動稱為________。 14．在AOV圖中，頂點表示________,有向邊表示________。12．一個連通圖的___________是一個極小連通子圖。 10．已知圖G的鄰接表如圖73所示，從頂點v1出發(fā)的深度優(yōu)先搜索序列為________，從頂點1出發(fā)的廣度優(yōu)先搜索序列為_____________。8．對于n個頂點的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_________，判斷任意兩個頂點i和j是否有邊相連的方法是__________，求任意一個頂點的度的方法是__________。6．已知一個有向圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的弧的方法是____________。4．若無向圖G的頂點度數(shù)最小值大于___________時，G至少有一條回路。2．對于具有n個頂點的強連通有向圖G至少有_________條邊。A．在AOE網(wǎng)中，減少任一關(guān)鍵活動的權(quán)值后，整個工期也就相應減少B．AOE網(wǎng)工程工期為關(guān)鍵活動的權(quán)值和C．在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必須在關(guān)鍵路徑上D．A和B31．下面說法不正確的是______。A．O(n) B．O(ne)C．O(n2) D．O(n3) 29．關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中______。A．求關(guān)鍵路徑的方法 B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法 D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時間復雜度為______。25．若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有向圖_______。C．由n1條權(quán)值之和最小的邊構(gòu)成的連通子圖。A．由n1條權(quán)值最小的邊構(gòu)成的子圖。A．G’為G的連通分量 B．G’為G的無環(huán)子圖C．G’為G的子圖 D．G’為G的極小連通子圖且V’＝V。A．1，3，2，4，5，6，7 B．1，2，4，3，5，6，7C．1，2，3，4，5，7，6 D．2，5，1，4，7，3，621．一個無向連通圖的生成樹是含有該連通圖的全部頂點
教學教案相關(guān)推薦
鄂ICP備17016276號-1