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

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

2013-11-15 15:17:48  來源: 數據結構 

  

  ()樹形選擇排序基本思想首先對n個待排序記錄的關鍵字進行兩兩比較從中選出én/ù個較小者再兩兩比較直到選出關鍵字最小的記錄為止此為一趟排序我們將一趟選出的關鍵字最小的記錄稱為冠軍亞軍是從與冠軍比較失敗的記錄中找出具體做法為輸出冠軍將其葉子結點關鍵字改為最大值然後從該葉子結點開始和其左(或右)兄弟比較修改從葉子結點到根結點路徑上各結點的關鍵字則根結點的關鍵字即為次小關鍵字如此下去可依次選出從小到大的全部關鍵字

  () 樹形選擇排序與直接選擇排序相比較其優點是從求第個元素開始從ni+個元素中不必進行ni次比較只比較ëlognû次比較次數遠小於直接選擇排序其缺點是輔助儲存空間大

  () 堆排序基本思想是堆是n個元素的序列先建堆即先選得一個關鍵字最大或最小的記錄然後與序列中最後一個記錄交換之後將序列中前n記錄重新調整為堆(調堆的過程稱為篩選)再將堆頂記錄和當前堆序列的最後一個記錄交換如此反復直至排序結束優點是在時間性能與樹形選擇排序屬同一量級的同時堆排序只需要一個記錄大小供交換用的輔助空間調堆時子女只和雙親比較避免了過多的輔助存儲空間及和最大值的比較

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


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