民國106年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第12題
假設n 代表資料數量,下列之描述何者是錯誤?
題目
假設n 代表資料數量,下列之描述何者是錯誤?
- (1) 在A V L T r e e 新增、刪除、搜尋一個節點,所需之時間複雜度均為O ( l o g n )
- (2) 在H e a p 新增一個值,所需之時間複雜度O ( l o g n )
- (3) 刪除M i n i m u m H e a p 之最小值,所需之時間複雜度
- (4) 將二元樹以P r e o r d e r 順序排列,所需之計算複雜度為O ( n )
官方答案
(3) 刪除M i n i m u m H e a p 之最小值,所需之時間複雜度
解析
n 為資料量時：AVL Tree 為平衡二元搜尋樹，其新增、刪除、搜尋皆維持 O(log n)（選項1正確）；Heap 新增元素需向上調整，複雜度 O(log n)（選項2正確）；二元樹前序(Preorder)走訪須拜訪每個節點一次，為 O(n)（選項4正確）。刪除 Min Heap 的最小值（位於根）後，需將末節點移至根並向下調整(heapify-down)，同樣為 O(log n)；若該選項聲稱其他複雜度即為錯誤敘述，故選3。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。