數據結構第五章圖習題

第第頁數據結構第五章圖習題

05圖

【單選題】

1.設無向圖G中有五個頂點，各頂點的度分別為2、4、3、1、2，則G中邊數為（C）。Ａ、4條Ｂ、5條Ｃ、6條Ｄ、無法確定

2.含n個頂點的無向完全圖有（D）條邊；含n個頂點的有向圖最多有（C）條?。缓琻個頂點的有向強連通圖最多有（C）條??；含n個頂點的有向強連通圖最少有（Ｆ）條弧；設無向圖中有n個頂點，則要接通全部頂點至少需（G）條邊。

A、n2B、n(n+1)C、n(n-1)D、n(n-1)/2E、n+1F、nG、n-1

3.對下圖從頂點a出發(fā)進行深度優(yōu)先遍歷，則（A）是可能得到的遍歷序列。A、acfgdebB、abcdefgC、acdgbefD、abefgcd

對下圖從頂點a出發(fā)進行廣度優(yōu)先遍歷，則（D）是不可能得到的遍歷序列。A、abcdefgB、acdbfgeC、abdcegfD、adcbgef

?010???4.設圖G的鄰接矩陣A=101，則G中共有（C）個頂點；若G為有向圖，則G中共有（D）????010??條弧；若G為無向圖，則G中共有（B）條邊。

A、1B、2C、3D、4E、5F、9G、以上答案都不對

5.含n個頂點的圖，最少有（B）個連通分量，最多有（D）個連通分量。A、0B、1C、n-1D、n

6.用鄰接表存儲圖所用的空間大小（A）。

A、與圖的頂點數和邊數都有關B、只與圖的邊數有關C、只與圖的頂點數有關D、與邊數的平方有關

7.n個頂點的無向圖的鄰接表最多有（B）個表結點。A、n2B、n(n-1)C、n(n+1)D、n(n-1)/2

8.無向圖G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（D）。

A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b

9.圖的BFS生成樹的樹高比DFS生成樹的樹高（A）。A、小或相等B、小C、大或相等D、大

10.下列不正確的是（C）。

(1)求從指定源點到其余各頂點的迪杰斯特拉（Dijkstra）最短路徑算法中弧上權不能為負的原因是在實際應用中無意義；

(2)利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3)；（圖用鄰接矩陣表示）(3)Floyd求每對不同頂點對的算法中允許弧上的權為負，但不能有權和為負的回路。A、(1),(2),(3)B、(1)C、(1),(3)D、(2),(3)

11.當各邊上的權值（A）時，BFS算法可用來解決單源最短路徑問題。A、均相等B、均互不相等C、不一定相等

12.若一個有向圖具有拓撲排序序列，那么它的鄰接矩陣必定為（C）。A、對稱矩陣B、稀疏矩陣C、三角矩陣D、一般矩陣

13.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（D）。A、G中有弧B、G中有一條從Vi到Vj的路徑C、G中沒有弧D、G中有一條從Vj到Vi的路徑

14.關鍵路徑是AOE網中（B）。

A、從始點到終點的最短路徑B、從始點到終點的最長路徑

C、人始點到終點的邊數最多的路徑D、從始點到終點的邊數最少的路徑

15.下面關于求關鍵路徑的說法不正確的是（C）。A、求關鍵路徑是以拓撲排序為基礎的

B、一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同

C、一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D、關鍵活動一定位于關鍵路徑上

【填空題】

1.設無向連通圖G含n個頂點e條邊，則G的生成樹含個頂點條邊。2.連通分量是無向圖的子圖，生成樹是無向連通圖的子圖。3.對稀疏圖而言，在鄰接矩陣和鄰接表這兩種存儲結構中選擇更為適宜。4.設無向圖G含n個頂點e條邊，則G的鄰接表表示中含個邊表結點。5.設有向圖G含n個頂點e條弧，則G的鄰接表表示中含個邊表結點。

【計算題】

1.設無向圖如下，寫出對該圖從頂點a出發(fā)進行廣度優(yōu)先遍歷可能得到的所有遍歷序列。

解：abcdefg、abdcegf、acbdfeg、acdbfge、adbcgef、adcbgfe。

2.設有向圖如下，寫出對該圖從頂點a出發(fā)進行深度優(yōu)先遍歷可能得到的所有遍歷序列。

解：abedc、acbed、acdbe。

3.設無向網如下，(1)寫出其鄰接矩陣；(2)基于該鄰接矩陣求深度優(yōu)先生成樹和廣度優(yōu)先生成樹；(3)基于該鄰接矩陣按普里姆算法求最小生成樹；(4)寫出其鄰接表；(5)基于該鄰接表按克魯斯卡爾算法求最小生成樹。

解：???4??3(1)??????????????4?559???35?5???5?55?7654?9?7?3?????63?2????5?2?6?????5??4??????6?????(2)深度優(yōu)先生成樹：；廣度優(yōu)先生成樹：

(3)最小生成樹：；求解過程：

(4)鄰接表：

(5)最小生成樹：

4.設AOV圖如下，寫出對該圖進行拓撲排序可能得到的所有拓撲序列。

解：abcdefg、abcdfeg、abcfdeg

5.設AOE網如下，試求關鍵路徑。

解：關鍵路徑１：v1→v2→v5→v7關鍵路徑２：v1→v3→v6→v7。

6.設有向網如下，試