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

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

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

   初始序列[]   移動[]
  移動[]     移動[]
  移動[]     移動[]

  類似本題的另外敘述題的解答

  ()快速排序思想首先將待排序記錄序列中的所有記錄作為當前待排序區域以第一個記錄的關鍵字作為樞軸(或支點)(pivot)凡其關鍵字不大於樞軸的記錄均移動至該記錄之前凡關鍵字不小於樞軸的記錄均移動至該記錄之後致使一趟排序之後記錄的無序序列R[st]將分割成兩部分R[si]和R[i+t]且R[j]key≤R[i]key≤R[k]key(s≤j<ii<k≤t)然後再遞歸地將R[si]和R[i+t]進行快速排序快速排序在記錄有序時蛻變為冒泡排序可用三者取中法改善其性能避免最壞情況的出現具體排序實例不再解答

  .()不可以若m+到n之間關鍵字都大於m的關鍵字時<=k可將j定位到m上若為<k則j將定位到m將出界線會造成錯誤

  ()不穩定例如´(m=n=)對´排序完成會變成´

  ()各次調用qsort的結果如下

  一次調用m=n=       j=

  二次調用m=n=       j= (右部)

  三次調用m=n= 不變返回   m=n= j=

  四次調用m=n= 不變返回 m=n= 返回 m=n= j=(左部)

  五次調用m=n=   j=

  六次調用m=n= 不變返回 m=n=  返回m=n= j=

  七次調用m=n= 不變返回     (注一次劃分後右兩部分調用算兩次)

  ()最大棧空間用量為O(logn)

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


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