民國108年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第34題
50 個元素儲存於二元樹,依由上而下,由左而右之順序。若以一個一維陣列B 儲存,下列何者是 正確的?(假設陣列第一個元素其位置編號從1 開始)
題目
50 個元素儲存於二元樹,依由上而下,由左而右之順序。若以一個一維陣列B 儲存,下列何者是 正確的?(假設陣列第一個元素其位置編號從1 開始)
- (1) B[20 ]之左邊及右邊節點分別為B[41]及B[42]
- (2) 這棵樹的leaf node 共有26 個,non-leaf node 共有24 個
- (3) 第一個leaf node 儲存在陣列的第24 個位置
- (4) 第5 層之節點共16 個
官方答案
(4) 第5 層之節點共16 個
解析
以陣列從1開始編號儲存完全二元樹時，編號 i 的節點，其左、右子節點分別是 2i 與 2i+1。前4層節點數為 1+2+4+8=15，所以第5層從編號16開始，編號16到31正好有16個節點；節點總數50大於31，表示第5層這16個位置全部存在，選項4正確。B[20]的子節點應為B[40]、B[41]，不是41、42；50個節點的樹，葉節點為編號26到50共25個，非葉節點也是25個；第一個葉節點在編號26，不是24。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。