數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題-文庫吧
2025-03-10 03:01 本頁面
【正文】 v1，v2，v5，v3，v4 234 ∧35 ∧5 ∧4 ∧v1v2v3v4 ∧v5圖71 一個有向圖的鄰接表19．對圖72所示的無向圖，從頂點1開始進行深度優(yōu)先遍歷，可得到頂點訪問序列______。A．1，2，4，3，5，7，6 B．1，2，4，3，5，6，7C．1，2，4，5，6，3，7 D．1，2，3，4，5，7，61654327 圖72 一個無向圖20．對圖72所示的無向圖，從頂點1開始進行廣度優(yōu)先遍歷，可得到頂點訪問序列______。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．一個無向連通圖的生成樹是含有該連通圖的全部頂點的______。A．極小連通子圖 B．極小子圖C．極大連通子圖 D．極大子圖22．設(shè)無向圖 G=(V, E) 和G’= (V’, E’)，如果 G’為G的生成樹，則下列說法中不正確的是______。A．G’為G的連通分量 B．G’為G的無環(huán)子圖C．G’為G的子圖 D．G’為G的極小連通子圖且V’＝V。A．只有一棵 B．有一棵或多棵C．一定有多棵 D．可能不存在24．對于含有n個頂點的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個________。A．由n1條權(quán)值最小的邊構(gòu)成的子圖。 B．由n1條權(quán)值之和最小的邊構(gòu)成的子圖。C．由n1條權(quán)值之和最小的邊構(gòu)成的連通子圖。D．由n個頂點構(gòu)成的邊的權(quán)值之和最小的生成樹。25．若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有向圖_______。A．是個有根有向圖 B．是個強連通圖C．含有多個入度為0的頂點 D．含有頂點數(shù)目大于1的強連通分量26．判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用____。A．求關(guān)鍵路徑的方法 B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法 D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時間復(fù)雜度為______。A．O(n) B．O(n+e)C．O(n2) D．O(ne)28．求最短路徑的Floyd算法的時間復(fù)雜度為______。A．O(n) B．O(ne)C．O(n2) D．O(n3) 29．關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中______。A．從源點到匯點的最長路徑 B．從源點到匯點的最短路徑C．最長的回路 D．最短的回路30．下面說法不正確的是______。A．在AOE網(wǎng)中，減少任一關(guān)鍵活動的權(quán)值后，整個工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動的權(quán)值和C．在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必須在關(guān)鍵路徑上D．A和B31．下面說法不正確的是______。A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間B．任何一個關(guān)鍵活動提前完成，將使整個工程提前完成C．所有關(guān)鍵活動都提前完成，則整個工程提前完成D．某些關(guān)鍵活動若提前完成，將使整個工程提前完成二、填空題1．對于具有n個頂點的無向圖G最多有_________條邊。2．對于具有n個頂點的強連通有向圖G至少有_________條邊。3．對于具有n個頂點的有向圖，每個頂點的度最大可達___________。4．若無向圖G的頂點度數(shù)最小值大于___________時，G至少有一條回路。5．對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1