阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
103年 - 103年地方三等-三等資料結構#42936
> 申論題
題組內容
四、給定一個陣列(array) A[0], A[1],…, A[99] 用以表示一個循環佇列(circular queue)。 另外再以兩個整數變數 front 及 back 記錄該循環佇列之前端(front of the queue) 及尾端(back of the queue)。一個尚未有任何資料的循環佇列之 front = back = -1:
(三)此循環佇列最多可以儲存幾筆資料?(5 分)
相關申論題
(一)請用 Kruskal 演算法找出最小生成樹 MST(G) (minimum spanning tree)。請依序寫 出加入此最小生成樹的每一個邊。(5 分)
#136775
(二)請用 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
(二)請寫出該二元樹之前序巡行(preorder traversal)結果。(10 分)
#136780
(一)請依序寫出過程中逐一加入已被選擇的頂點(vertex),起始頂點為 S。(10 分)
#136781
(二)請問以此演算法所找出的 S 到 T 最短路徑長度為何?(5 分)
#136782
(一)若要新增加一筆資料於此循環佇列,front 及 back 變數該如何改變?(5 分)
#136783
(二)若要從循環佇列中取出並刪除一筆資料,front 及 back 變數該如何改變?(5 分)
#136784
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327