103年 - 103年地方三等-三等資料結構#42936

科目：公職◆資料結構 | 年份：103年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

(一)請用 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 分）

(一)請畫出該二元樹 T。（10 分）

(二)請寫出該二元樹之前序巡行（preorder traversal）結果。（10 分）

(一)請依序寫出過程中逐一加入已被選擇的頂點（vertex），起始頂點為 S。（10 分）

(二)請問以此演算法所找出的 S 到 T 最短路徑長度為何？（5 分）

(一)若要新增加一筆資料於此循環佇列，front 及 back 變數該如何改變？（5 分）

(二)若要從循環佇列中取出並刪除一筆資料，front 及 back 變數該如何改變？（5 分）

(三)此循環佇列最多可以儲存幾筆資料？（5 分）

(四)若此循環佇列已經全滿，在未刪除任何資料前已不能再儲存新資料，請問此時 front 及 back 的關連為何？（5 分）

(一)請依序寫出泡沫排序法前五回合的排序結果。（10 分）

(二)請依序寫出快速排序法前五回合的排序結果，每一回合用一個樞紐（pivot），並把每一回合所用的樞紐圈起來。（10 分）