高考申論題
105年
[資訊處理] 資料結構
第 一 題
📖 題組：
四、(一)依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分） (二)從上面(一)小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
四、(一)依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分） (二)從上面(一)小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
思路引導 VIP
本題測驗 Min Heap（最小堆積）的建構。解題關鍵在於把握兩大原則：(1) 完全二元樹特性：新元素一律先插入至樹的最底層最右側（即陣列末端）；(2) 最小堆積特性：插入後與父節點比較，若比父節點小則進行向上交換（Heapify-up），直到滿足父節點均小於等於子節點為止。
小題 (二)
從上面(一)小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
思路引導 VIP
Min Heap 的刪除操作固定為「移除根節點（即最小值）」，接著將「樹的最後一個葉節點」移至根節點，並執行向下調整（Down-Heap），每次與值較小的子節點交換，直到重新滿足父節點小於等於子節點的特性。本題需從第(一)題的結果出發，連續執行兩次刪除操作並繪圖。