地特三等申論題
108年
[資訊處理] 資料結構
第 一 題
📖 題組：
有下列資料元素（data elements），其數值越小則優先權（priority）越高，請分別依序將各元素加入（add）優先佇列（priority queue）中，且分別以下列三種資料結構實作之。 90, 10, 80, 20, 70, 50, 40, 30
有下列資料元素（data elements），其數值越小則優先權（priority）越高，請分別依序將各元素加入（add）優先佇列（priority queue）中，且分別以下列三種資料結構實作之。 90, 10, 80, 20, 70, 50, 40, 30
📝 此題為申論題，共 3 小題
小題 (一)
用雙向鏈接串列（doubly-linked list）來實作此優先佇列，請畫出其資料結構圖。（6 分）
思路引導 VIP
看到使用雙向鏈結串列實作「優先佇列」，且數值越小優先權越高，應想到為了能有效率地取得最高優先權元素（O(1) 取出），在依序插入時應維持串列呈「已排序（數值由小到大）」狀態。繪圖時務必清晰呈現雙向箭頭（prev 與 next 指標）、資料值，並標示出 Head 與 Tail。
小題 (二)
用紅黑樹（red-black tree）來實作此優先佇列，請畫出其資料結構圖。注意: 紅節點請標示 R，例如 20R 表示其值為 20 的紅（Red）節點；黑節點則請標示 B，例如 50B 表示其值為 50 的黑（Black）節點。（7 分）
思路引導 VIP
本題考查紅黑樹（Red-Black Tree）的節點新增與平衡操作。解題關鍵在於依序將元素加入，每次加入預設為紅節點，並檢查是否違反紅黑樹規則（不可有連續紅節點）。若違反，則依據叔叔節點的顏色，進行重新著色（Recolor）或旋轉（Rotation）以維持樹的平衡。
小題 (三)
用最小堆積（min heap）來實作此優先佇列，請畫出其資料儲存的陣列（array）圖。注意: 陣列索引（array index）由左向右遞增。（7 分）
思路引導 VIP
遇到最小堆積（Min Heap）的資料插入題，優先思考「依序插入完全二元樹的最後一個節點（即陣列最尾端）」。接著必須執行向上調整（Up-Heapify），若新插入的元素小於其父節點，則兩者交換，直到滿足「父節點數值不大於子節點」的最小堆積性質。