地特三等申論題
111年
[資訊處理] 資料結構
第 一 題
📖 題組：
回顧二元樹結構，其為 m 路樹（m-ary Trees，亦稱多元樹、m 元樹）的一個特例，請回答下列相關問題：
回顧二元樹結構，其為 m 路樹（m-ary Trees，亦稱多元樹、m 元樹）的一個特例，請回答下列相關問題：
📝 此題為申論題，共 3 小題
小題 (一)
給出 m 路樹的定義。（5 分）
思路引導 VIP
看到 m 路樹的定義，應直接聯想二元樹（m=2）的推廣。作答時需採用嚴謹的遞迴定義，點出「空集合」或「根節點加最多 m 棵互不相交且具次序性的子樹」這兩大條件，並指明節點最大分支度（Degree）為 m。
小題 (二)
若用陣列來表示一個 m 路樹，請說明如何利用陣列的索引值來表示節點間的親子連結關係（意即，假設陣列索引起始值為 0，若節點 v 在陣列的第 i 個位置，節點 v 的第 c 個子節點的位置為何？另一方面，節點 v 的 parent 位置為何？）？（10 分）
思路引導 VIP
看到陣列表示法的題目，應立刻聯想熟悉的二元樹（m=2）索引公式（子節點 2i+1 與 2i+2，父節點 ⌊(i-1)/2⌋），再將其等差與層次遍歷的規律推廣至 m 路樹。作答時必須嚴謹定義「第 c 個子節點」的起始值（通常設 c 從 1 起算），並列出簡單的推導步驟以確保邏輯嚴密。
小題 (三)
基於此 m 路樹結構及二元搜尋樹（Binary Search Tree）的概念，我們可以定義出一個多元搜尋樹。當 m=4 的時候，可以稱此搜尋樹為四元搜尋樹。請給出(2,4)-樹((2,4)-tree)的定義並比較與四元搜尋樹的差異。（10 分）
思路引導 VIP
作答本題時，首先需精確寫出 (2,4)-樹（即 2-3-4 樹）的三大核心性質：節點度數限制（2,3,4）、搜尋樹鍵值排列規則，以及最重要的「完美平衡」（所有葉節點同高）。接著在比較差異時，應以普通的「四元搜尋樹」為基準，從『是否具備自平衡機制』、『節點度數下限限制』與『時間複雜度（最佳/最差情況）』三個維度進行對比分析，即可完整取分。