高考申論題
105年
[資訊處理] 資料結構
第 一 題
📖 題組：
二、(一)請將下列值 2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫出結果。作答時，請標示節點如下：例如節點 2B 表示其值為 2 的黑（Black）節點，又如節點 5R 表示其值為 5 的紅（Red）節點。（10 分） (二)請畫出與上面(一)小題相對應的 2-3-4 樹（2-3-4 tree）。（10 分）
二、(一)請將下列值 2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫出結果。作答時，請標示節點如下：例如節點 2B 表示其值為 2 的黑（Black）節點，又如節點 5R 表示其值為 5 的紅（Red）節點。（10 分） (二)請畫出與上面(一)小題相對應的 2-3-4 樹（2-3-4 tree）。（10 分）
📝 此題為申論題，共 3 小題
小題 (一)
請將下列值 2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫出結果。作答時，請標示節點如下：例如節點 2B 表示其值為 2 的黑（Black）節點，又如節點 5R 表示其值為 5 的紅（Red）節點。（10 分）
思路引導 VIP
看到此題，首先應掌握紅黑樹的插入規則：新節點預設為紅色，若發生連續紅節點衝突，需依據「叔叔節點的顏色」決定使用「重新著色（Recolor）」或「旋轉（Rotation，含LL、RR、LR、RL）」。對於 2-3-4 樹，則可運用其與紅黑樹的等價映射關係，將紅黑樹中的紅色節點與其黑色的父節點直接合併，即可快速得出答案。
小題 (二)
請畫出與上面(一)小題相對應的 2-3-4 樹（2-3-4 tree）。（10 分）
思路引導 VIP
看到此題應立刻聯想到「紅黑樹與 2-3-4 樹的等價關係（Isomorphism）」。解題技巧在於：將紅黑樹中的「紅節點」與其「黑色的父節點」進行合併，即可無痛還原出對應的 2-3-4 樹結構。轉換後可再透過節點數值大小的排序（左小右大）進行驗算，確保分支區間正確。
小題 (三)
求出三者乘積之最有效的方式為何？
思路引導 VIP
看到多個矩陣連乘求最佳效率，應立即想到「矩陣連乘積問題（Matrix Chain Multiplication）」，並使用「動態規劃（Dynamic Programming）」求解。藉由建立最小乘法次數陣列，由小區間（2個矩陣）逐步推導至大區間（4個矩陣），最後回溯找出最佳結合順序。