民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第41題
將右列堆積( H e a p ) [ 15 , 13 , 9 , 5 , 12 , 8 , 7 , 4 , 0 , 1 , 2 , 6 ] 的最大元素刪除後,所…
題目
將右列堆積( H e a p ) [ 15 , 13 , 9 , 5 , 12 , 8 , 7 , 4 , 0 , 1 , 2 , 6 ] 的最大元素刪除後,所形成的堆積何者正 確?
- (1) 13 , 12 , 9 , 5 , 6 , 8 , 7 , 4 , 0 , 1 , 2
- (2) 13 , 9 , 5 , 12 , 8 , 7 , 4 , 0 , 6 , 2 , 1
- (3) 13 , 12 , 9 , 5 , 2 , 8 , 7 , 4 , 0 , 1 , 6
- (4) 13 , 12 , 9 , 8 , 7 , 6 , 5 , 4 , 2 , 1 , 0
官方答案
(1) 13 , 12 , 9 , 5 , 6 , 8 , 7 , 4 , 0 , 1 , 2
解析
最大堆積刪除最大值即刪除根節點 15，作法是將最後一個元素 6 移到根，再從根向下調整（heapify）：根的兩子為 13、9，與較大的 13 交換，得 [13,6,9,5,12,8,7,4,0,1,2]；此時索引 1 的子節點為 5 與 12，再與 12 交換，得 [13,12,9,5,6,8,7,4,0,1,2]；6 的兩子 1、2 皆小於 6，調整結束，故選 1。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。