加載中. ..
PDF
103年特種考試地方政府公務人員考試試題
代號：
34480
全一張
（正面）
等 別：
三等考試
類 科：
資訊處理
科 目：
資料結構
考試時間：2小時
座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、給定一個權重圖（weighted graph）G(V, E) 如下圖所示。
請用 Kruskal 演算法找出最小生成樹 MST(G) (minimum spanning tree)。請依序寫
出加入此最小生成樹的每一個邊。（5分）
請用 Prim 演算法找出最小生成樹 MST(G)。若以 A為起始點，請依序寫出加入
此最小生成樹的每一個邊。（5分）
假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊 vi - vj 且
其權重為 w。請設計一個 O(V) 的演算法，從已知的 MST(G) 中快速找出新圖的
最小生成樹。請以文字敘述說明。（10 分）
請說明上一小題 的演算法為 O(V)。（5分）
B
H
E
D
I
C F
A
32
35
225
64
40
19
30
21
14
20
24
16
23
15
26
二、給定一個二元樹T。若T之後序巡行（postorder traversal）結果是P D J M O A I H K G L N E B C，
而中序巡行（inorder traversal）結果是 J D P I A M O C K H G B E L N：
請畫出該二元樹 T。（10 分）
請寫出該二元樹之前序巡行（preorder traversal）結果。（10 分）
103年特種考試地方政府公務人員考試試題
代號：
34480
全一張
（背面）
等 別：
三等考試
類 科：
資訊處理
科 目：
資料結構
三、請用 Dijkstra 演算法找出下圖中從 S到T的最短路徑長度：
請依序寫出過程中逐一加入已被選擇的頂點（vertex），起始頂點為 S。（10 分）
請問以此演算法所找出的 S到T最短路徑長度為何？（5分）
B
G
E
K
T
C
A
H
F
D
S
L
M
5
2
1
3
5
1
7
6
5
6
5
1
3
5
3
2
6
3
3
1
4
4
4
四、給定一個陣列（array） A[0], A[1],…, A[99] 用以表示一個循環佇列（circular queue）。
另外再以兩個整數變數 front 及back 記錄該循環佇列之前端（front of the queue）
及尾端（back of the queue）。一個尚未有任何資料的循環佇列之 front = back = -1：
若要新增加一筆資料於此循環佇列，front 及back 變數該如何改變？（5分）
若要從循環佇列中取出並刪除一筆資料，front 及back 變數該如何改變？（5分）
此循環佇列最多可以儲存幾筆資料？（5分）
若此循環佇列已經全滿，在未刪除任何資料前已不能再儲存新資料，請問此時
front 及back 的關連為何？（5分）
五、給定下列尚未排序之數列：80, 24, 11, 47, 19, 91, 2, 32, 85, 7, 16, 36, 99, 52, 41，請以
泡沫排序法（bubble sort）及快速排序法（quick sort）分別將該數列由小到大排序：
請依序寫出泡沫排序法前五回合的排序結果。（10 分）
請依序寫出快速排序法前五回合的排序結果，每一回合用一個樞紐（pivot），並
把每一回合所用的樞紐圈起來。（10 分）