阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 103年 - 103年地方三等-三等資料結構#42936
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 分)