阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
103年 - 103年地方三等-三等資料結構#42936
>
題組內容
二、給定一個二元樹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:
(二)請寫出該二元樹之前序巡行(preorder traversal)結果。(10 分)
其他申論題
(二)請用 Prim 演算法找出最小生成樹 MST(G)。若以 A 為起始點,請依序寫出加入 此最小生成樹的每一個邊。(5 分)
#136776
(三)假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊 vi - vj 且 其權重為 w。請設計一個 O(V) 的演算法,從已知的 MST(G) 中快速找出新圖的 最小生成樹。請以文字敘述說明。(10 分)
#136777
(四)請說明上一小題(三) 的演算法為 O(V)。(5 分)
#136778
(一)請畫出該二元樹 T。(10 分)
#136779
(一)請依序寫出過程中逐一加入已被選擇的頂點(vertex),起始頂點為 S。(10 分)
#136781
(二)請問以此演算法所找出的 S 到 T 最短路徑長度為何?(5 分)
#136782
(一)若要新增加一筆資料於此循環佇列,front 及 back 變數該如何改變?(5 分)
#136783
(二)若要從循環佇列中取出並刪除一筆資料,front 及 back 變數該如何改變?(5 分)
#136784
(三)此循環佇列最多可以儲存幾筆資料?(5 分)
#136785
(四)若此循環佇列已經全滿,在未刪除任何資料前已不能再儲存新資料,請問此時 front 及 back 的關連為何?(5 分)
#136786