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

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

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

  拓撲排序是有向圖的頂點依照弧的走向找出一個全序集的過程主要是根據與頂點連接的弧來確定頂點序列冒泡排序是借助交換思想通過比較相鄰結點關鍵字大小進行排序的算法

    直接插入排序的基本思想是基於插入開始假定第一個記錄有序然後從第二個記錄開始依次插入到前面有序的子文件中即將記錄R[i](<=i<=n)插入到有序子序列R[i]中使記錄的有序序列從R[i]變為R[i] 最終使整個文件有序共進行n趟插入最壞時間復雜度是(n)平均時間復雜度是(n)空間復雜度是O()是穩定排序

  簡單選擇排序的基本思想是基於選擇開始有序序列長度為零第i(<=i<n)趟簡單選擇排序是從無序序列R[in]的ni+記錄中選出關鍵字最小的記錄和第i個記錄交換使有序序列逐步擴大最後整個文件有序共進行n趟選擇最壞時間復雜度是(n)平均時間復雜度是(n)空間復雜度是O()是不穩定排序

  二路並歸排序的基本思想是基於歸並開始將具有n個待排序記錄的序列看成是n個長度為的有序序列然後進行兩兩歸並得到én/ù個長度為的有序序列再進行兩兩歸並得到én/ù個長度為的有序序列如此重復經過élognù趟歸並最終得到一個長度為n的有序序列最壞時間復雜度和平均時間復雜度都是(nlogn)空間復雜度是O(n)是穩定排序

   錯誤快速排序堆排序和希爾排序是時間性能較好的排序方法但都是不穩定的排序方法

   等概率(後插)插入位置n則平均移動個數為n/

  若不等概率則平均移動個數為

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


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