完整版)排序練習(xí)題(答案

1、排序練習(xí)題1.2.3.4.5.6.7.8.9.10.11.12.A. 3, 5, 7, 9, 12, 10, 15, 2B. 3, 5, 9, 7, 12, 10, 15, 1單項(xiàng)選擇題)。假定元素 ri+1 的插入位置為 rj ，若對(duì) n 個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第 i 趟排序時(shí)， 則需要移動(dòng)元素的次數(shù)為(A. j-iB. i-j-1 C. i-jD. i-j+1在對(duì) n 個(gè)元素進(jìn)行直接插入排序的過(guò)程中，共需要進(jìn)行(A. n B. n+1 C. n-1)趟。D. 2n在對(duì) n 個(gè)元素進(jìn)行冒泡排序的過(guò)程中，最好情況下的時(shí)間復(fù)雜度為(2A. O(1)B. O(log 2n)C. O(n 2

2、)D. O(n)。在對(duì) n 個(gè)元素進(jìn)行快速排序的過(guò)程中，若每次劃分得到的左、右兩個(gè)子區(qū)間中元素的個(gè)數(shù)相等 或只差一個(gè)，則排序的時(shí)間復(fù)雜度為(A. O(1)B. O(nlog 2n)。2C. O(n 2)D. O(n)在對(duì) n 個(gè)元素進(jìn)行直接插入排序的過(guò)程中，A. O(1)B. O(log 2n)算法的空間復(fù)雜度為( )。2C. O(n 2)D. O(nlog 2n)設(shè)一組初始記錄關(guān)鍵字序列 (5，2，6， 進(jìn)行比較，則第一趟冒泡排序的結(jié)果為( (A) 2 ，5，3，6， 8(C) 2 ，3，5，6， 83，8)，利用冒泡排序進(jìn)行升序排序，且排序中從后往前 )。(B) 2 ，5，6，3，8(D)

3、 2 ，3，6，5，8對(duì)下列四個(gè)序列進(jìn)行快速排序，各以第一個(gè)元素為基準(zhǔn)進(jìn)行第一次劃分，則在該次劃分過(guò)程中 需要移動(dòng)元素次數(shù)最多的序列為( )。A. 1, 3, 5, 7, 9B. 9, 7, 5, 3, 1C. 5, 1, 3, 7, 9D. 5, 7, 9, 3, 1在對(duì) n 個(gè)元素進(jìn)行堆排序的過(guò)程中，時(shí)間復(fù)雜度為(2A. O(1)B. O(log 2n)C. O(n 2)。D. O(nlog 2n)以下序列不可以構(gòu)成小跟堆的是(A. 12, 9, 7, 5, 3, 1)。B. 1, 3, 5, 9, 7, 12C. 1, 5, 3, 7, 9, 12D. 1, 5, 3, 9, 12, 7

4、設(shè)一組初始記錄關(guān)鍵字序列 (5， 8， 快速排序的結(jié)果為( )。A. 2，3，5，8， 6C. 3， 2，5，6，3，B.8，6D.2)，以第一個(gè)記錄關(guān)鍵字 5 為基準(zhǔn)進(jìn)行一趟從大到小2，3，5，6，83，2， 5， 8， 6假定對(duì)元素序列( 為( )。7, 3, 5, 9, 1, 12)進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆A. 1, 3, 5, 7, 9, 12B. 1, 3, 5, 9, 7, 12C. 1, 5, 3, 7, 9, 12D. 1, 5, 3, 9, 12, 7假定一個(gè)初始堆為(1, 5, 3, 9, 12, 7, 15, 10) ，則進(jìn)行第一趟堆排序后，再

5、重新建堆得到的結(jié)果為)。C. 3, 7, 5, 9, 12, 10, 15, 1D. 3, 5, 7, 12, 9, 10, 15, 113.若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為(A. nB. n-1C. n/214.若要從A.C.1000個(gè)元素中得到10個(gè)最小值元素，最好采用(直接插入排序B.歸并排序堆排序D.快速排序D. log 2 n)方法。15.若要對(duì)A.1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用( 直接插入排序B.歸并排序C.堆排序)方法。D.快速排序填空題1.2.3.對(duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為 快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi)0(nlog 2n).2

6、_0(n )_。假定一組記錄為(46,79,56,38,40,84)，則利用堆排序方法建立的初始小根堆為_(kāi)(38,40,56,79,46,84)n-1_，最少的趟數(shù)為_(kāi)1，在最壞情況下的時(shí)間復(fù)雜度為-4-4.假定一組記錄為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為_(kāi)(40,38,46,56,79,80)_。5. 假定一組記錄為 (46,79,56,38,40,80,46,75,28,46)，對(duì)其進(jìn)行歸并排序的過(guò)程中，供需要4趟完成。6. 在時(shí)間復(fù)雜度為0(nlog 2n)的所有排序方法中，_歸并排序方法是穩(wěn)定的。7. 設(shè)有一無(wú)序序列32，45，41，12,

7、1，9 ，進(jìn)行從小到大的希爾排序，且分組增量d=3，則一趟希爾排序后的序列為 12,1,9,32,45,41。三、判斷題1. 希爾排序算法的平均時(shí)間復(fù)雜度為O(n2)。( 0 )2. 堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。(1 )3. 在對(duì)排序中，若要進(jìn)行升序排序，則需要建立大根堆。(1 )4. 若給出的待排序序列已有序，則使用快速排序的進(jìn)行排序的時(shí)間復(fù)雜度是0(n)。( 0 )5. 若待排序序列已基本有序，則使用冒泡排序會(huì)比快速排序的時(shí)間效率會(huì)更好。(1)6. 堆排序是穩(wěn)定的排序算法。(0 )四、應(yīng)用題1.已知一組記錄為(46,74,53,14,26,38,86,65,27,34)每一趟的排

8、序結(jié)果。2.已知一組記錄為(46,74,53,14,26,38,86,65,27,34) 趟的排序結(jié)果。3.已知一組記錄為(46,74,53,14,26,38,86,65,27,34)趟的排序結(jié)果。4.已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用直接插入排序法進(jìn)行排序時(shí)，給出采用冒泡排序法進(jìn)行排序時(shí)每一，給出采用快速排序法進(jìn)行排序時(shí)每一，給出采用簡(jiǎn)單選擇排序法進(jìn)行排序時(shí)，給出采用堆排序法進(jìn)行排序時(shí)每一趟，給出采用歸并排序法進(jìn)行排序時(shí)每一每一趟的排序結(jié)果。5. 已知一組記錄為 (46,74,53,14,26,38,86,65,27,34) 的排序結(jié)果。6

9、. 已知一組記錄為 (46,74,53,14,26,38,86,65,27,34) 趟的排序結(jié)果。四、應(yīng)用題（參考答案）1.(0)46745314263886652734(1)46745314263886652734(2)46537414263886652734(3)14465374263886652734(4)14264653743886652734(5)14263846537486652734(6)14263846537486652734(7)14263846536574862734(8)14262738465365748634(9)142627343846536574862.(0)467

10、45314263886652734(1)46531426387465273486(2)46142638536527347486(3)14263846532734657486(4)14263846273453657486(5)14263827344653657486(6)14262734384653657486(7)142627343846536574863.(0)46745314263886652734(1)34273814264686655374(2)26271434384674655386(3)14262734384653657486(4)142627343846536574864.(0)

11、46745314263886652734(1)14745346263886652734(2)14265346743886652734(3)14262746743886655334(4)14262734743886655346(5)14262734387486655346(6)14262734384686655374(7)14262734384653658674(8)14262734384653658674-7-(9) 14 26 27 34 38 46 53 65 74 865. 構(gòu)成初始堆(即建堆)的過(guò)程：123456 78910(0)46745314263886652734(1)46745

12、314263886652734(2)46745314263886652734(3)46743814265386652734(4)46143827265386657434(5)14263827345386657446進(jìn)行堆排序的過(guò)程：(0)14263827345386657446(1)26273846345386657414(2)27343846745386652614(3)34463865745386272614(4)38465365748634272614(5)46655386743834272614(6)53657486463834272614(7)65867453463834272614(8)74866553463834272614