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