民國110年 第2梯次 電腦軟體設計(C++)乙級 學科
第64題
關於分支度(Order)為m 的B-tree ,下列那些正確?
題目
關於分支度(Order)為m 的B-tree ,下列那些正確?
- (1) 樹根儲存的資料數量為(m-1)/2 至m-1
- (2) 所有的葉節點都是同一階層
- (3) 新增一筆新資料時,目前的樹根可能會分割成兩個節點,並建立一個新樹根
- (4) 樹根以外的樹節點儲存之資料數量為(m-1)/2 至m-1
官方答案
(2) 所有的葉節點都是同一階層、(3) 新增一筆新資料時,目前的樹根可能會分割成兩個節點,並建立一個新樹根、(4) 樹根以外的樹節點儲存之資料數量為(m-1)/2 至m-1
解析
B-tree（分支度/Order 為 m）具備下列特性：所有葉節點位於同一階層（高度相同），故②正確。插入資料時若造成樹根節點鍵值超過上限 m-1，樹根會分裂為兩個子節點，並於上層建立新樹根，樹高因而增加，故③正確。對於樹根以外的內部與葉節點，其鍵值數量介於 ⌈m/2⌉-1 與 m-1 之間；當 m 為奇數時 ⌈m/2⌉-1=(m-1)/2，故④之範圍正確。而樹根最少只需 1 個鍵值（非空時），並不適用 (m-1)/2 之下限，故①錯誤。綜上，正確為 2、3、4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。