申論題 - 阿摩線上測驗

申論題資訊

試卷：109年 - 109 身心特考_三等_資訊處理：資料結構#86485
科目：公職◆資料結構
年份：109年
排序：0

題組內容

四、假設有個矩陣 A[1:n]儲存 n 個整數。本題將設計 heap 排序演算法（heap sort）之重要部分，將矩陣 A[1:n]變成一個 max-heap。

申論題內容

(二)設計一個副程式 sift(A, r, n)其輸入參數 A 是一個矩陣，n 是矩陣 A 的大小，1≦r≦n 是一個指標。副程式 sift(A, r, n)的功能是將 A[r]為樹根的子樹變成 heap。（在呼叫 sift(A, r, n)之前， A[i]的所有子樹必須已經是 heap）並分析其計算時間確實是 O(h(r))，其中 h(r)是以A[r]為樹根的子樹的高度。（10 分）