地特三等申論題
109年
[資訊處理] 資料結構
第 一 題
📝 此題為申論題，共 2 小題
小題 (一)
請描述 order 為 m 的 B-tree 之特性。（6分）
思路引導 VIP
看到 B-tree 特性題，應立即聯想其為「平衡的多路搜尋樹（Balanced Multi-way Search Tree）」。解題關鍵在於精確列出定義的五大要素：節點最大分支度、內部節點最小分支度（⌈m/2⌉）、根節點限制、鍵值與指標數量的關係，以及葉節點齊平（同層）的絕對平衡特性。
小題 (二)
請問 order 為 m 高度為 h 的 B-tree：⑴最多有幾個節點？最多有幾個Key？（6分）⑵最少有幾個節點？最少有幾個 Key？（8分）
思路引導 VIP
遇到 B-tree 最大/最小節點與鍵值推導題，先確認 B-tree 的定義：Order m 代表每個節點最多 m 個子節點、m-1 個鍵值；除根節點外，內部節點最少有 ⌈m/2⌉ 個子節點、⌈m/2⌉-1 個鍵值。接著確立高度 h 的定義（通常假設根節點為第 1 層，樹葉為第 h 層），利用等比級數公式逐層累加，即可嚴謹求得答案。