民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第52題
一個只包含根節點的B - t r e e 其高度為1。一個分支度( o r d e r ) 為3 的B - t r e e ,若其高度為 4 ,最多可儲多少筆資…
題目
一個只包含根節點的B - t r e e 其高度為1。一個分支度( o r d e r ) 為3 的B - t r e e ,若其高度為 4 ,最多可儲多少筆資料?
- (1) 120
- (2) 39
- (3) 80
- (4) 26
官方答案
(3) 80
解析
B-tree 節點鍵值數範圍為 [⌈m/2⌉-1, m-1]。題目給分支度 order = 3，即 m = 3，葉節點最多鍵值 = 2。高度 h = 4 表示路徑上有 4 個節點（根層級 1、葉層級 4）。根層級 1 個節點；第 2 層最多 3 個節點；第 3 層最多 3×3=9 個節點；第 4 層最多 3×9=27 個葉節點。最多鍵值總數 = 27 × 2 = 54？不正確：B-tree 內部節點也存鍵值。一般教科書定義 B-tree 所有節點都存鍵值，內部節點最多 m-1=2 個鍵。節點總數 = 1 + 3 + 9 + 27 = 40，最多鍵值 = 40 × 2 = 80。選項 3 為 80，故選 3。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。