第7章-圖習(xí)題及參考答案

1、1第7章習(xí)題一、單項選擇題1.在無向圖中定義頂點的度為與它相關(guān)聯(lián)的（）的數(shù)目。A.頂點B.邊C.權(quán)D.權(quán)值2.在無向圖中定義頂點vi與vj之間的路徑為從vi到達(dá)vj的一個（）。A.頂點序列B.邊序列C.權(quán)值總和D.邊的條數(shù)3.圖的簡單路徑是指（）不重復(fù)的路徑。A.權(quán)值B.頂點C.邊D.邊與頂點均4.設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A.n1B.n(n1)2C.n(n1)2D.n(n1)5.n個頂點的連通圖至少有（）條邊。A.

2、n1B.nC.n1D.06.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的()倍。A.3B.2C.1D.127.若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個()。A.上三角矩陣B.稀疏矩陣C.對角矩陣D.對稱矩陣8.圖的深度優(yōu)先搜索類似于樹的（）次序遍歷。A.先根B.中根C.后根D.層次9.圖的廣度優(yōu)先搜索類似于樹的（）次序遍歷。A.先根B.中根C.后根D.層次10.在用Kruskal算法求解帶權(quán)連通圖的最小（代價）生

3、成樹時，選擇權(quán)值最小的邊的原則是該邊不能在圖中構(gòu)成（）。A.重邊B.有向環(huán)C.回路D.權(quán)值重復(fù)的邊11.在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時，要求圖中每條邊所帶的權(quán)值必須是（）。A.非零B.非整C.非負(fù)D.非正12.設(shè)G1=(V1E1)和G2=(V2E2)為兩個圖，如果V1?V2，E1?E2，則稱（）。A.G1是G2的子圖B.G2是G1的子圖C.G1是G2的連通分量D.G2是G1的連通分量13.有向圖的一個頂點的度為該

4、頂點的（）。A.入度B.出度C.入度與出度之和D.(入度﹢出度))／214.一個連通圖的生成樹是包含圖中所有頂點的一個（）子圖。A.極小B.連通C.極小連通D.無環(huán)15.n(n＞1)個頂點的強(qiáng)連通圖中至少含有（）條有向邊。A.n1B.nn(n1)2D.n(n1)16.在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的（）生成樹中。A.某個最小B.任何最小C.廣度優(yōu)先D.深度優(yōu)先17.對于具有e條邊的無向圖，它的鄰接表中有（）個結(jié)點。A.e

5、1B.eC.2(e1)D.2e18.對于如圖所示的帶權(quán)有向圖，從頂點1到頂點5的最短路徑為（）。A.145B.1235C.1435D.1243512613819554123319.存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（上）三角部分就可以了。20.連通分量是無向圖中的極小連通子圖。21.在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。四、運(yùn)算題1.設(shè)連通圖G如圖所示。試畫出該圖對應(yīng)的鄰接矩陣表示，并給出對它執(zhí)行從頂點V0開始的廣度優(yōu)

6、先搜索的結(jié)果。2.設(shè)連通圖G如圖所示。試畫出該圖及其對應(yīng)的鄰接表表示，并給出對它執(zhí)行從V0開始的深度優(yōu)先搜索的結(jié)果。3.對于如圖所示的有向圖，試寫出：(1)從頂點①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹4.設(shè)有向圖G如圖所示。試畫出從頂點V0開始進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的DFS生成森林和BFS生成森林。5.設(shè)有一個連通網(wǎng)絡(luò)如圖所示。試按如下格式，應(yīng)用Kruskal算