民國110年 第2梯次 電腦軟體設計(C++)乙級 學科
第71題
依序讀入1,2,3,4,5,6,7,8,並建造一棵2-3 樹,下列那些正確?
題目
依序讀入1,2,3,4,5,6,7,8,並建造一棵2-3 樹,下列那些正確?
- (1) 2 與6 儲存於同一節點內
- (2) 4 儲存於樹根內
- (3) 3 與8 在同一階層
- (4) 7 與8 儲存於同一節點內
官方答案
(2) 4 儲存於樹根內、(3) 3 與8 在同一階層、(4) 7 與8 儲存於同一節點內
解析
依序插入 1~8 建立 2-3 樹（每節點 1~2 鍵值、葉同層）。插入過程：1,2 形成 [1,2]；插 3 溢位分裂出根 [2] 與葉 [1]、[3]；續插 4,5 得根 [2,4]，葉 [1]、[3]、[5]；插 6,7 使右葉 [5,6,7] 溢位，上推 6 使根 [2,4,6] 再溢位，最終分裂為根 [4]，左右子節點 [2]、[6]，葉為 [1]、[3]、[5]、[7,8]。由此：4 位於樹根（選項 2 正確）；3 與 8 皆為葉節點、同階層（選項 3 正確）；7 與 8 同存於最右葉節點（選項 4 正確）。2 與 6 分處不同內部節點，故選項 1 錯誤。答案為 2、3、4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。