高考申論題
107年
[資訊處理] 資料結構
第 一 題
📖 題組：
四、對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）是一種優先佇列（priority queue），請回答下列與 SMMH 相關的問題：
四、對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）是一種優先佇列（priority queue），請回答下列與 SMMH 相關的問題：
📝 此題為申論題，共 3 小題
小題 (一)
請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積（heap）建構之優先佇列功能有何不同？並從一個空的 SMMH 開始，依序插入 30,20,50,5,4,9,70,2,80。請畫出最後 SMMH 的樹狀結構圖。（10 分）
思路引導 VIP
SMMH 是進階的 Heap 變體。1. 特性分析：SMMH 根節點不放資料，其左子樹與右子樹的對應關係代表了 Min 與 Max 的雙向限制。2. 功能對比：一般 Heap 只能快速找 Min 或 Max 其中之一；SMMH 則是雙端優先佇列（Double-Ended Priority Queue），可同時高效處理找最小值與最大值。3. 插入模擬：記住 SMMH 節點性質：若節點有左兄弟，左兄弟 $\le$ 自己；若有祖父，則祖父的左子 $\le$ 自己 $\le$ 祖父的右子。
小題 (二)
請畫出第(一)小題建構的 SMMH，刪除數字 2 後 SMMH 的樹狀結構圖。（5 分）
思路引導 VIP
刪除操作通常是：1. 移除目標節點。2. 用最後一個節點（最後一層最右邊的節點）填補空位。3. 重新調整樹結構以符合 SMMH 性質。在此例中，刪除 2 是刪除葉子，相對單純，但仍須檢查其父節點與祖父節點的性質是否維持。
小題 (三)
請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0，請列出由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第(一)小題建構完成的 SMMH 的結果。（15 分）
思路引導 VIP
SMMH 在陣列中的表現與一般二元樹類似，但要注意根節點（Index 0 或 1）的處理。題目要求起始索引為 0，且 SMMH 的根（Index 0）通常不存值。公式推導需基於「完滿二元樹」的索引邏輯：
- 父節點：$p = \lfloor (x-1)/2 \rfloor$