103年特種考試地方政府公務人員考試三等_資料結構
首頁
>
線上測驗
>
公職考試>地方特考/三等>資訊處理
> 103年特種考試地方政府公務人員考試三等_資料結構
年度
年度
105
104
103
100
99
98
1.
給定一個權重圖(weighted graph)G(V, E) 如下圖所示。
(一)請用Kruskal 演算法找出最小生成樹 MST(G) (minimum spanning tree)。請依序寫出加入此最小生成樹的每一個邊。
(二)請用Prim 演算法找出最小生成樹 MST(G)。若以A 為起始點,請依序寫出加入此最小生成樹的每一個邊。
(三)假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊
vi
-
vj
且其權重為
w
。請設計一個O(V) 的演算法,從已知的MST(G) 中快速找出新圖的最小生成樹。請以文字敘述說明。
(四)請說明上一小題的演算法為 O(V)。
題型:問答題
難易度:尚未記錄
2.
給定一個二元樹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。
(二)請寫出該二元樹之前序巡行(preorder traversal)結果。
題型:問答題
難易度:尚未記錄
3.
請用 Dijkstra 演算法找出下圖中從S 到T 的最短路徑長度:
(一)請依序寫出過程中逐一加入已被選擇的頂點(vertex),起始頂點為S。
(二)請問以此演算法所找出的S 到T 最短路徑長度為何?
題型:問答題
難易度:尚未記錄
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
變數該如何改變?
(二)若要從循環佇列中取出並刪除一筆資料,
front
及
back
變數該如何改變?
(三)此循環佇列最多可以儲存幾筆資料?
(四)若此循環佇列已經全滿,在未刪除任何資料前已不能再儲存新資料,請問此時
front
及
back
的關連為何?
題型:問答題
難易度:尚未記錄
5.
給定下列尚未排序之數列:80, 24, 11, 47, 19, 91, 2, 32, 85, 7, 16, 36, 99, 52, 41,請以泡沫排序法(bubble sort)及快速排序法
(quick sort)分別將該數列由小到大排序:
(一)請依序寫出泡沫排序法前五回合的排序結果。
(二)請依序寫出快速排序法前五回合的排序結果,每一回合用一個樞紐(pivot),並把每一回合所用的樞紐圈起來。
題型:問答題
難易度:尚未記錄
購買題庫後,可使用那些功能?
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)