Wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Graph

Total questions: 30

Worksheet time: 15mins

Name
Class
Date
1.

下列哪一個是尤拉循環成立的必要且充分條件？（圖中頂點度數均可觀察）

a)

所有頂點度數皆為偶數

b)

恰有兩個頂點度數為奇數

c)

至少一個頂點度數為奇數

d)

所有頂點度數皆為奇數

2.

尤拉鏈可以存在於何種度數情況？

a)

所有頂點度數皆為偶數

b)

恰有兩個頂點度數為奇數

c)

恰有一個頂點度數為奇數

d)

至少三個頂點度數為奇數

3.

若有一座城市橋梁問題，要求走遍每座橋且只走一次並回到出發點，應使用哪種路徑概念？

a)

最短路徑

b)

尤拉鏈

c)

哈密頓路徑

d)

尤拉循環

4.

在無向圖中，頂點的度數代表什麼？

a)

該頂點的入邊數量

b)

該頂點的出邊數量

c)

到其他頂點的最短距離

d)

與其相鄰的邊數量

5.

在無向圖中，若有 n 個頂點且恰好有 n(n−1)/2 個邊，該圖稱為什麼？

a)

強連通圖，任意方向皆可達

b)

多重圖，允許重邊與自迴路

c)

完全圖，所有頂點兩兩相連

d)

子圖，只包含部分頂點邊

6.

簡單路徑的正確敘述是什麼？

a)

所有頂點必須互為相鄰

b)

除端點外所有頂點皆不重複

c)

除終點外不可有任何邊

d)

除起點外可重複頂點與邊

7.

在有向圖中，若任意一對頂點 u、v 皆存在從 u 到 v 與從 v 到 u 的有向路徑，則該圖具備何性質？

a)

最大連通子圖，唯一存在

b)

外分支度為零的圖

c)

強連通，雙向皆可到達

d)

連通圖，僅無向情境成立

8.

下列哪一項正確描述連通分量？

a)

所有頂點的度數總和

b)

圖中最大的連通子圖

c)

所有簡單路徑的集合

d)

所有強連通分量之並

9.

在有向圖中，若使用相鄰矩陣表示，行代表頂點、列代表頂點，則矩陣元素vij的意義是什麼？

a)

表示vi與vj在同一連通分量

b)

表示vi與vj的度數相等

c)

表示從vj到vi有邊連接

d)

表示從vi到vj有邊連接

10.

相鄰串列表示法中，頂點的內分支度數與外分支度數如何取得？

a)

內分支度數看堆疊大小，外分支度數看佇列大小

b)

內分支度數數相鄰串列長度，外分支度數看矩陣對角

c)

內分支度數計入度，外分支度數計出度

d)

內分支度數看列首，外分支度數看列尾

11.

在深度優先搜尋過程中，若從起點走到某頂點w，發現w的所有相鄰頂點皆已被拜訪，應採取什麼動作？

a)

改用廣度優先搜尋繼續

b)

清空堆疊並重新開始

c)

停止搜尋並輸出結果

d)

回溯到最近未拜訪的頂點

12.

使用相鄰矩陣表示稀疏圖時，空間複雜度約為多少？

a)

n2n^2

b)

n

c)

n log n

d)

m

13.

在深度優先搜尋(DFS)的堆疊實作中，當某頂點被輸出後，下一步正確的動作是什麼？

a)

將所有訪問過的頂點重新標記

b)

將佇列中的第一個頂點入列一次

c)

將其父節點從堆疊彈出並輸出

d)

將其所有相鄰頂點依序推入堆疊

14.

依照圖中所示的BFS流程，若起始頂點為 V1，且依序入列其未拜訪的相鄰頂點，早期拜訪順序的前三個頂點應為哪一組？

a)

V1、V5、V7

b)

V1、V2、V3

c)

V1、V4、V6

d)

V1、V8、V10

15.

下列敘述何者最能區分DFS與BFS的遍歷特性？

a)

DFS偏向沿一條路徑深入，BFS偏向逐層展開

b)

DFS逐層展開，BFS沿單一路徑深入

c)

DFS與BFS皆以遞歸為唯一實作

d)

DFS與BFS皆以佇列為主結構

16.

依據圖中最後總結的BFS拜訪順序，若起始於 V1，正確的完整順序是哪一個？

a)

V1、V4、V5、V6、V2、V3、V7、V8、V9、V10

b)

V1、V2、V3、V4、V5、V6、V7、V8、V9、V10

c)

V1、V2、V3、V5、V4、V6、V8、V7、V9、V10

d)

V1、V3、V2、V4、V6、V5、V7、V8、V10、V9

17.

在無向連通圖中，擴展樹的基本性質是什麼？

a)

不連通且無迴圈

b)

含迴圈但連通

c)

可能有向且連通

d)

不含迴圈且連通

18.

Prim 演算法在選擇下一條邊時的核心準則是什麼？

a)

選擇任意尚未加入的邊

b)

選擇形成最長路徑的邊

c)

選擇目前樹中成本最大的邊

d)

選擇跨越 U 與 V−U 的最小成本邊

19.

Kruskal 演算法在加入邊時必須檢查哪件事以避免？

a)

避免形成迴圈

b)

避免增加頂點數

c)

避免邊跨越兩集合

d)

避免選擇相同成本

20.

對同一張加權連通圖，使用 Prim 或 Kruskal 求得的最小成本擴展樹將如何？

a)

成本不同且結構不同

b)

成本相同但結構可能不同

c)

成本相同且結構必相同

d)

成本不同但結構相同

21.

下列哪一項最正確描述單一來源最短路徑問題的目標？請參考圖例中以城市為頂點、邊權為距離的情境。

a)

在圖中選出不相鄰邊使總成本最小

b)

找出所有頂點之間的所有路徑總數

c)

自指定起點到所有頂點的最小路徑成本

d)

自所有頂點到指定終點的最大路徑成本

22.

在Dijkstra演算法的初始化步驟中，集合S與陣列D的典型設定為何？請依圖中文本說明作答。

a)

S含相鄰頂點；D為其邊權值

b)

S為空集合；D皆為∞含起點

c)

S僅含起點；D起點為0他點為∞

d)

S含所有頂點；D皆為零

23.

依照步驟2的規則，從V−S中選擇下一個加入S的頂點時，主要依據是什麼？

a)

選與S相鄰頂點中編號最小者

b)

選與起點邊權最小之頂點

c)

選目前D值最小之頂點

d)

選度數最大之頂點

24.

在更新公式D[I] = min(D[I], D[t] + A[t, I])中，符號A[t, I]表示什麼量？

a)

集合S的大小減一

b)

頂點t到頂點I的邊權距離

c)

圖中所有邊權的總和

d)

頂點I的目前最小路徑成本

25.

圖1顯示以陣列Y記錄最短路徑的前一頂點。若Uj=最短距離，dj為從i到j的距離，更新規則應如何表示？

a)

Uj=min(dj−Ui)，並記錄前一頂點j

b)

Uj=max(Ui+dj)，並刪除前一頂點i

c)

Uj=min(Ui+dj)，並記錄前一頂點i

d)

Uj=max(dj−Ui)，並加入所有鄰接點

26.

在AOV-network中，每個頂點代表哪一種元素？

a)

代表路徑或邊(edge path)

b)

代表時間或日程(schedule time)

c)

代表資源或成本(cost resource)

d)

代表活動或工作(task, activity)

27.

若在AOV網路中存在拓樸排序，以下哪一敘述正確？

a)

所有頂點必須形成一個環路

b)

每條邊由前驅vi指向後繼vj

c)

刪除後繼頂點以維持排序正確

d)

每條邊由後繼vj指向前驅vi

28.

在 AOV-network 中，「立即前行者」與「前行者」的主要差異是什麼？

a)

立即前行者允許多條路徑

b)

前行者只出現在無向圖

c)

前行者必定是臨界活動

d)

立即前行者只靠一條邊相連

29.

拓樸排序的基本兩步驟是哪兩個？

a)

找無前行者並輸出

b)

先找臨界路徑再輸出

c)

隨機挑一頂點刪除

d)

刪除其出邊並更新入度

30.

在臨界路徑法中，若某活動 earliest(i)=latest(i)，該活動的性質是？

a)

非臨界可延三天

b)

假活動無工期

c)

臨界活動不可延遲

d)

邊上事件不可改

Similar Resources on Wayground

資訊科技-4

28 questions

資訊科技-4

quiz

Worksheet

•

University

doc 7-2019

31 questions

doc 7-2019

quiz

Worksheet

•

University