選擇題

1-1
無向連通圖所有頂點的度之和為偶數。
T

1-2
無向連通圖邊數一定大于頂點個數減1
F

1-3
無向連通圖至少有一個頂點的度為1。
F

1-4
用鄰接表法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關.
F

1-5
用鄰接矩陣法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關。
T

1-6
在一個有向圖中，所有頂點的入度與出度之和等于所有邊之和的2倍。
T

1-7
在任一有向圖中，所有頂點的入度之和等于所有頂點的出度之和。
T

1-8
如果無向圖G必須進行兩次廣度優(yōu)先搜索才能訪問其所有頂點，則G中一定有回路.
F

1-9
如果無向圖G必須進行兩次廣度優(yōu)先搜索才能訪問其所有頂點，則G一定有2個連通分量。
T

1-10
在一個有權無向圖中，若b到a的最短路徑距離是12，且c到b之間存在一條權為2的邊，則c到a的最短路徑距離一定不小于10。
T

1-11
Kruskal 算法是維護一個森林，每一步把兩棵樹合并成一棵。
T

1-12
Kruskal 算法是通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹。
F

1-13
Prim 算法是通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹。
T

1-14
若圖G有環(huán)，則G不存在拓撲排序序列。
T

1-15
若圖G為連通圖且不存在拓撲排序序列，則圖G必有環(huán)。
T

1-16
P 是頂點 S 到 T 的最短路徑，如果該圖中的所有路徑的權值都加 1，P 仍然是 S 到 T 的最短路徑。
F

1-17
如果從有向圖 G 的每一點均能通過深度優(yōu)先搜索遍歷到所有其它頂點，那么該圖一定不存在拓撲序列。
T

1-18
如果 e 是有權無向圖 G 唯一的一條最短邊，那么邊 e 一定會在該圖的最小生成樹上。
T

選擇題

2-1
下列關于無向連通圖特征的敘述中，正確的是：（所有頂點的度之和為偶數）

2-2
若無向圖G =（V，E）中含7個頂點，要保證圖G在任何情況下都是連通的，則需要的邊數最少是：（16）

2-3
具有5個頂點的有向完全圖有（20）條弧

2-4
在N個頂點的無向圖中，所有頂點的度之和不會超過頂點數的多（N-1）倍

2-5
對于有向圖，其鄰接矩陣表示比鄰接表表示更易于：（求一個頂點的入度）

2-6
若一個有向圖用鄰接矩陣表示，則第i個結點的入度就是：（第i列的非零元素個數）

2-7
下面關于圖的存儲的敘述中，（用相鄰矩陣法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關）是正確的

2-8
關于圖的鄰接矩陣，（有向圖的鄰接矩陣可以是對稱的，也可以是不對稱的）是正確的

2-9
在一個無向圖中，所有頂點的度數之和等于所有邊數的（2）倍

2-10
在任一有向圖中，所有頂點的入度之和與所有頂點的出度之和的關系是：（相等）

2-11
設無向圖的頂點個數為N，則該圖最多有（N(N?1)/2）條邊

2-12
圖的深度優(yōu)先遍歷類似于二叉樹的：（先序遍歷）

2-13
在用鄰接表表示有N個結點E條邊的圖時，深度優(yōu)先遍歷算法的時間復雜度為：（O(N+E)）

2-14
已知一個圖的鄰接矩陣如下，則從頂點V1出發(fā)按深度優(yōu)先搜索法進行遍歷，可能得到的一種頂點序列為：（V1,V2,V4,V5,V6,V3）

2-15
我們用一個有向圖來表示航空公司所有航班的航線。（Dijkstra算法）最適合解決找給定兩城市間最經濟的飛行路線問題？

2-16
數據結構中Dijkstra算法用來解決（最短路徑）問題？

2-17
給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：（14）

2-18
在AOE網中，（從第一個事件到最后一個事件的最長路徑）是關鍵路徑

2-19
下面給出的有向圖中，各個頂點的入度和出度分別是：（入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1）

2-20
若要檢查有向圖中有無回路，除了可以利用拓撲排序算法外，（深度優(yōu)先搜索）也可以用

2-21
給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：（8）

2-22
如果G是一個有15條邊的非連通無向圖，那么該圖頂點個數最少為（ 7 ）

2-23
圖的廣度優(yōu)先遍歷類似于二叉樹的（層次遍歷）

2-24
給定一個有向圖的鄰接表如下圖，則該圖有（ 3 {{2}, {4}, {0, 1, 3, 5}} ）個強連通分量。

2-25
給定有權無向圖的鄰接矩陣如下，其最小生成樹的總權重是：（23）

2-26
給定有向圖的鄰接矩陣如下：

頂點2（編號從0開始）的出度和入度分別是：（0,2）

2-27
給定有權無向圖如下。關于其最小生成樹，（最小生成樹不唯一，其總權重為23）是對的

2-28
已知無向圖G含有16條邊，其中度為4的頂點個數為3，度為3的頂點個數為4，其他頂點的度均小于3。圖G所含的頂點個數至少是：（11）

2-29
下列選項中，不是如下有向圖的拓撲序列的是：（5, 2, 1, 6, 3, 4）

2-30
具有 100 個頂點和 12 條邊的無向圖至多有（95）個連通分量

2-31
具有 50 個頂點和 17 條邊的無向圖至多有（44）個連通分量

2-32
使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標頂點是：（2, 4, 3, 6, 5, 7）

2-33
使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標頂點是：（6, 7, 5, 3, 2, 4）

2-34
下圖所示的 AOE 網表示一項包含 8 個活動的工程。活動 d 的最早開始時間和最遲開始時間分別是：（12 和 14）

2-35
設無向圖為 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。則每個頂點的度依次為：（3, 2, 3, 2）

2-36
設無向圖為 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。則相應的鄰接矩陣為：

2-37
對于給定的有向圖如下，其鄰接表為：


2-38
對于給定的有向圖如下，其逆鄰接表為：

2-39
對于給定的有向圖如下，其強連通分量為：（{1}, {2, 3, 4, 6}, {5}）

2-40
已知一個無向圖的頂點集為 {V0,V1,?,V7}，其鄰接矩陣如下所示：

以下哪項不可能是從 V0 出發(fā)的深度優(yōu)先遍歷序？
V0,V1,V4,V3,V6,V7,V2,V5

2-41
已知一個無向圖的頂點集為 {V0,V1,?,V7}，其鄰接矩陣如下所示：

以下哪項不可能是從 V0 出發(fā)的廣度優(yōu)先遍歷序？
V0,V3,V1,V4,V2,V6,V5,V7

2-42
以下哪個是給定無向帶權圖的鄰接矩陣？

到自身和其他到不了的頂點的距離都是無窮大

2-43
以下哪個不是給定無向帶權圖的最小生成樹？

2-44
給定無向帶權圖如下，（abcdefgh）是從頂點 a 出發(fā)深度優(yōu)先搜索遍歷該圖的頂點序列（多個頂點可以選擇時按字母序）

2-45
給定一個圖的鄰接矩陣如下，則從V1出發(fā)的深度優(yōu)先遍歷序列（DFS，有多種選擇時小標號優(yōu)先）是：（V1, V2, V4, V6, V8, V10, V9, V7, V5, V3）

2-46
給定一個圖的鄰接矩陣如下，則從V1出發(fā)的寬度優(yōu)先遍歷序列（BFS，有多種選擇時小標號優(yōu)先）是：V1, V2, V3, V4, V5, V6, V7, V9, V8, V10

2-48
試利用 Dijkstra 算法求下圖中從頂點 A 到其他頂點的最短距離及對應的路徑。下列那個序列給出了可能的頂點收集順序？ACFEDBG

2-49
給出如下圖所示的具有 7 個結點的網 G，哪個選項對應其正確的鄰接矩陣？


2-50
給出如下圖所示的具有 7 個結點的網 G，采用Prim算法，從4號結點開始，給出該網的最小生成樹。下列哪個選項給出了正確的樹結點收集順序？4563201

2-51
給定有向圖如下。（abdfce）不是對應的拓撲序列？

2-52
一個工程項目由下列 A-L 共12個活動構成，各活動的持續(xù)時間和前驅活動如下圖。則完成該項目的所需時間和關鍵活動是：110；ABCDEGHL(最長的)

2-53
對下圖從頂點C出發(fā)進行廣度優(yōu)先搜索，哪個是正確的搜索序列？CBDAEHFG

2-54
已知無向圖 G 如下所示，使用克魯斯卡爾（Kruskal）算法求圖 G 的最小生成樹，加入到最小生成樹中的邊依次是：(b,f), (b,d), (a,e), (c,e), (b,e)

2-55
若使用 AOE 網估算工程進度，則下列敘述中正確的是：關鍵路徑是從源點到匯點路徑長度最長的路徑

2-56
給定如下有向圖，該圖的拓撲有序序列的個數是：1

2-57
使用 Dijkstra 算法求下圖中從頂點 1 到其余各頂點的最短路徑，將當前找到的從頂點 1 到頂點 2、3、4、5 的最短路徑長度保存在數組 dist 中，求出第二條最短路徑后，dist 中的內容更新為：21、3、14、6

2-58
圖的遍歷(廣度優(yōu)先)
對下圖進行廣度優(yōu)先遍歷，得到的序列不可能為 ▁CDFBAE▁▁ 。
文章來源地址http://www.zghlxwxcb.cn/news/detail-440329.html

到了這里，關于《數據結構》_PTA_數據結構作業(yè)6：圖的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！