民國110年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第80題
關於分支度(Order)為m 的B-tree ,下列那些正確?
題目
關於分支度(Order)為m 的B-tree ,下列那些正確?
- (1) 所有的葉節點都是同一階層
- (2) 樹根以外的樹節點儲存之資料數量為(m-1)/2 至m-1
- (3) 新增一筆新資料時,目前的樹根可能會分割成兩個節點, 並建立一個新樹根
- (4) 樹根儲存的資料數量為(m-1)/2 至m-1
官方答案
(1) 所有的葉節點都是同一階層、(2) 樹根以外的樹節點儲存之資料數量為(m-1)/2 至m-1、(3) 新增一筆新資料時,目前的樹根可能會分割成兩個節點, 並建立一個新樹根
解析
B-tree 的定義要求所有葉節點位於同一階層，樹高保持平衡，選項1正確。就分支度 m 而言，除樹根與葉節點外，每個節點儲存的鍵值數介於 ⌈m/2⌉−1 與 m−1 之間（題目以 (m−1)/2 表示其下限），選項2正確。新增資料使節點鍵值超過 m−1 時會分裂，若溢滿的是樹根，樹根分裂為兩個節點並產生新的樹根，樹高增加一層，選項3正確。樹根只需至少 1 個鍵值、最多 m−1 個，並不受下限 (m−1)/2 限制，故選項4錯誤。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。