民國114年 第2梯次 延期考區 電腦軟體設計(JAVA)乙級 學科
第22題
假設有一分支度(Order)為17 之B-tree,下列敘述何者是正確?
題目
假設有一分支度(Order)為17 之B-tree,下列敘述何者是正確?
- (1) 若此B-tree 之高度為3(共3 層),則鍵值總數最少的情形為108 個
- (2) 樹根節點至少有8 個鍵值(Key)
- (3) 樹根節點至少有9 個子節點
- (4) 若此B-tree 之高度為4(共4 層),則第4 層之鍵值總數最少的情形為1296 個
官方答案
(4) 若此B-tree 之高度為4(共4 層),則第4 層之鍵值總數最少的情形為1296 個
解析
分支度(Order)為 17 的 B-tree，每個節點最多 17 個子節點、16 個鍵值；非根節點最少要有 ⌈17/2⌉=9 個子節點，即最少 9-1=8 個鍵值。高度 4 時，第 2 層最少 2 個節點，第 3 層最少 2×9=18 個節點，第 4 層最少 18×9=162 個節點，每個節點最少 8 個鍵值，故 162×8=1296 個鍵值，選項 4 正確。樹根最少只需 1 個鍵值、2 個子節點，故選項 2、3 皆誤；高度 3 的最少鍵值為 1+2×8+18×8=161，並非 108，選項 1 也錯。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。