Q99.
有關Tree 的敘述，下列何者正確？
電腦軟體設計共同科目 · 乙級 · Q99
難易度分析
3 / 5
本題不僅要求掌握不同樹狀結構的建立方向定義，還需運用 B-tree 的分支度與容量公式進行精確的數值計算，以判斷高度的最小值與最大值，具備概念區分與量化分析雙重要求。
正確答案：④將100000 筆資料存入分支度(Order)為256 之B-tree，其高度至少為3
④ 將100000 筆資料存入分支度(Order)為256 之B-tree，其高度至少為3:分支度 m=256 時，每層最多 256 個子節點。高度為 2 時最多容納 255 + 256×255 = 65,535 筆資料，不足以儲存 100,000 筆，因此高度至少需為 3 才能滿足容量需求。
錯誤選項解析
- ① B-tree 的建立方式是採由上往下(Top-down)做法:B-tree 的經典插入演算法實際上是採由下往上 (Bottom-up) 方式，先將資料插入至葉節點，若節點溢出則向上分裂傳播，而非由上往下。
- ② 二元搜尋樹(Binary Search Tree)的建立方式是採由下往上(Bottom-up)做法:二元搜尋樹 (BST) 的建立與插入是從根節點開始，依據鍵值大小比較後決定往左或往右子樹移動，屬於由上往下 (Top-down) 的遍歷過程。
- ③ 將100000 筆資料存入分支度(Order)為256之B-tree，其高度最高為4:分支度為 256 的 B-tree，在非最壞情況下高度可能為 3 即可容納 100000 筆資料，因此「最高為 4」的敘述過於絕對，未考慮節點填充率的變化範圍。
Learning Tip
"本題核心考點為 B-tree 高度與容量的計算關係。解題關鍵在於掌握公式：高度 h 的 B-tree 最大容量為各層節點數乘以每節點最大鍵數。常見陷阱是混淆 Top-down 與 Bottom-up 的適用情境——B-tree 插入採 Bottom-up 分裂，而 BST 插入採 Top-down 遍歷。實務上，B-tree 因高度低、I/O 次數少，廣泛應用於資料庫索引結構。"
學員答題分佈
①B-tree 的建立方式是採由上往下(Top-down)做法0%
②二元搜尋樹(Binary Search Tree)的建立方式是採由下往上(Bottom-up)做法0%
③將100000 筆資料存入分支度(Order)為256之B-tree，其高度最高為40%
④將100000 筆資料存入分支度(Order)為256 之B-tree，其高度至少為30%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！