熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第十章 答案[18]

2013-11-15 15:18:42  來源: 數據結構 

   建立堆結構:    ()

  ()            ()

   ()是大堆 ()是大堆()是小堆

  ()不是堆調成大堆 

  類似敘述():不是堆 調成大頂堆 

  ()①是堆  ②不是堆 調成堆

  ()①是堆  ②不是堆 調成大堆(圖略)  ():略

   在內部排序方法中一趟排序後只有簡單選擇排序和冒泡排序可以選出一個最大(或最小)元素並加入到已有的有序子序列中但要比較n選次大元素要再比較n其時間復雜度是O(n)個元素中選個元素不能使用這種方法而快速排序插入排序歸並排序基數排序等時間性能好的排序都要等到最後才能確定各元素位置只有堆排序在未結束全部排序前可以有部分排序結果建立堆後堆頂元素就是最大(或最小視大堆或小堆而定)元素然後調堆又選出次大(小)元素凡要求在n個元素中選出k(k<<nk>)個最大(或最小)元素一般均使用堆排序因為堆排序建堆比較次數至多不超過n對深度為k的堆在調堆算法中進行的關鍵字的比較次數至多為(k)次且輔助空間為O()

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23201.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.