課程課件作業(yè)空chapter7

1復(fù)習(xí)題所謂簡單路徑是指_____。

A.任何一條邊在這條路徑上不重復(fù)出現(xiàn)

B.任何一個頂點在這條路徑上不重復(fù)出現(xiàn)

C.這條路徑由一個頂點序列構(gòu)成，不包含邊

D.這條路徑由一個邊的序列構(gòu)成，不包含頂點帶權(quán)有向圖G用鄰接矩陣A存儲，則vi的入度等于A中__。

A.第i行非∞的元素之和 B.第i列非∞的元素之和

C.第i行非∞和非0的元素個數(shù)

D.第i列非∞和非0的元素個數(shù)2復(fù)習(xí)題在一個無向圖中，所有頂點的度之和等于邊數(shù)的_____倍。

A.? B.1 C.2 D.4具有6個頂點的無向圖至少應(yīng)有____條邊才能確保是一個連通圖。

A.5 B.6 C.7 D.8如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是_____。

A.完全圖 B.連通圖 C.有回路 D.一棵樹3任何一個無向連通圖_____最小生成樹。

A.只有一個 B.有1或多棵 C.一定有多棵D.可能不存在一個有向圖G的鄰接表存儲如下圖所示，現(xiàn)按深度優(yōu)先搜索遍歷，從v1出發(fā)，所得到的頂點序列是____。

A.12345 B.12354 C.12453 D.12534復(fù)習(xí)題12345v1v2v3v4v523435544關(guān)鍵路徑是AOE網(wǎng)中_____。

A.從源點到匯點的最長路徑

B.從源點到匯點的最短路徑

C.最長的回路 D.最短的回路設(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復(fù)習(xí)題5判斷以下敘述的正確性。

1)n個頂點的無向圖最多有n(n-1)條邊。

2)在有向圖中，各頂點的入度之和等于各頂點的出度之和。

3)如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖。

4)如果表示有向圖的鄰接矩陣是對稱矩陣，則該有向圖一定是完全有向圖。

5)從n個頂點的連通圖中選取n-1條權(quán)值最小的邊，即可構(gòu)成最小生成樹。

6)強連通圖不能進行拓撲排序。復(fù)習(xí)題(錯)(對)(錯)()()()6

7)只要無向網(wǎng)中沒有權(quán)值相同的邊，其最小生成樹就是唯一的。

8)只要無向網(wǎng)中有權(quán)值相同的邊，其最小生成樹就不可能是唯一的。

9)如果表示某個圖的鄰接矩陣是對稱矩陣，則該圖一定不是無向圖。

10)最短路徑一定是簡單路徑。

11)在一個有向圖的拓撲序列中若頂點a在頂點b之前，則圖中必有一條弧<a,b>。

復(fù)習(xí)題()()()()()7

12)無環(huán)有向圖才能進行拓撲排序。

13)拓撲排序算法僅能適用于有向無環(huán)圖。14)在表示某工程的AOE網(wǎng)中，加速其關(guān)鍵路徑上的任意關(guān)鍵活動均可以縮短整個工程的完成時間。15)在AOE網(wǎng)中，關(guān)鍵路徑上活動的時間延長多少，整個工程的時間也就隨