排序練習(xí)題答案

1、排序練習(xí)題一、單項(xiàng)選擇題1. 若對(duì) n 個(gè)元素進(jìn)行直接插入排序， 在進(jìn)行第 i 趟排序時(shí)， 假定元素 ri+1 的插入位置為rj ，則需要移動(dòng)元素的次數(shù)為( ) 。a. j-i b. i-j-1 c. i-jd. i-j+12. 在對(duì) n 個(gè)元素進(jìn)行直接插入排序的過程中，共需要進(jìn)行( )趟。a. n b. n+1c. n-1 d. 2n3. 在對(duì) n 個(gè)元素進(jìn)行冒泡排序的過程中，最好情況下的時(shí)間復(fù)雜度為( ) 。2 d. o(n) n) c. o(n)a. o(1) b. o(log24. 在對(duì) n 個(gè)元素進(jìn)行快速排序的過程中，若每次劃分得到的左、右兩個(gè)子區(qū)間中元素的個(gè)數(shù)相等。 )或只差一個(gè)，

2、則排序的時(shí)間復(fù)雜度為( 2d. o(n) )n) c. o(n a. o(1)b. o(nlog 25. 在對(duì) n 個(gè)元素進(jìn)行直接插入排序的過程中，算法的空間復(fù)雜度為( ) 。2a. o(1) b. o(logd. o(nlogn)n) c. o(n)226. 設(shè)一組初始記錄關(guān)鍵字序列 (5， 2， 6， 3， 8)，利用冒泡排序進(jìn)行升序排序，且排序中從后往前 。進(jìn)行比較，則第一趟冒泡排序的結(jié)果為( ) (b) 2 ， 6， 8， 5，6， 3 ， 8， (a) 25 ， 3(d) 2 ， 3， (c) 2 ， 3， 56， 8 6 ， 5， 87. 對(duì)下列四個(gè)序列進(jìn)行快速排序，各以第一個(gè)元素

3、為基準(zhǔn)進(jìn)行第一次劃分，則在該次劃分過程中 ) 。 需要移動(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)行堆排序的過程中，時(shí)間復(fù)雜度為(8.2d. o(nlogn c. o(n a. o(1) b.o(logn) )22 。 以下序列不可以構(gòu)成小跟堆的是( 9.) b. 1, 3, 5, 9, 7, 12a. 12, 9,7, 5, 3, 1d. 1, 5, 3, 9, 12, 7c. 1, 5, 3, 7, 9, 1210. 設(shè)一組初始記錄關(guān)鍵字序列 (5， 8， 6，

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

5、, 10) 假定一個(gè)初始堆為 12.。) b. 3, 5, 9, 7, 12, 10, 15, 1a. 3, 5, 7, 9, 12, 10, 15, 1d. 3, 5, 7, 12, 9, 10, 15, 1c. 3, 7, 5, 9, 12, 10, 15, 113.若又t n個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為()。a. n b. n-1 c. n/2d. ?logn ? 214.若要從 1000 個(gè)元素中得到10個(gè)最小值元素，最好采用()方法。a.直接插入排序b.歸并排序d.快速排序c.堆排序15.若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用()方法。歸并排序b.快速排序d.

6、 a.直接插入排序堆排序c.二、填空題 1_。n1.對(duì)個(gè)記錄進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為_n-1,最少的趟數(shù)為_，在最壞情況下的時(shí)間復(fù)雜度為_o(nlogn)2.快速排序在平均情況下的時(shí)間復(fù)雜度為22 _o(n)0為根堆小立序排方法建的初始為一3.假定組記錄(46,79,56,38,40,84),則利用堆_ o _(38,40,56,79,46,84)為的結(jié)果劃的快，對(duì)其進(jìn)行速排序第一次分后錄定4.假一組記為(46,79,56,38,40,80) 。(40,38,46,56,79,80),對(duì)其進(jìn)行歸并排序的過程中，供需要(46,79,56,38,40,80,46,75,28,46)5.假定

7、一組記錄為 4 趟完成。排序方法是穩(wěn)定的。_的所有排序方法中，o(nlogn)歸并在時(shí)間復(fù)雜度為6. 2,則一 9 ,進(jìn)行從小到大的希爾排序，且分組增量d=3, 7.設(shè)有一無序序列3245, 4112, 1。趟希爾排序后的序列為12,1,9,32,45,41 一三、判斷題2 ) ( o 0) . 1希爾排序算法的平均時(shí)間復(fù)雜度為o(n堆是完全二叉樹，完全二叉樹不一定是堆。.(1)2)在對(duì)排序中，若要進(jìn)行升序排序，則需要建立大根堆。.3 (1 .40 )若給出的待排序序列已有序，則使用快速排序的進(jìn)行排序的時(shí)間復(fù)雜度是o(n)。(1 ()若待排序序列已基本有序，則使用冒泡排序會(huì)比快速排序的時(shí)間效率

8、會(huì)更好。. 56.堆排序是穩(wěn)定的排序算法。)(0四、應(yīng)用題，給出采用直接插入排序法進(jìn)行排序時(shí)(46,74,53,14,26,38,86,65,27,34) 1.已知一組記錄為每一趟的排序結(jié)果。，給出采用冒泡排序法進(jìn)行排序時(shí)每一2. 已知一組記錄為(46,74,53,14,26,38,86,65,27,34)趟的排序結(jié)果。，給出采用快速排序法進(jìn)行排序時(shí)每一已知一組記錄為3.(46,74,53,14,26,38,86,65,27,34)趟的排序結(jié)果。，給出采用簡(jiǎn)單選擇排序法進(jìn)行排序時(shí)(46,74,53,14,26,38,86,65,27,34)已知一組記錄為4.每一趟的排序結(jié)果。5.已知一組記錄為

9、(46,74,53,14,26,38,86,65,27,34)，給出采用堆排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。6.已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采用歸并排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。.四、應(yīng)用題(參考答案)1.(1) 46 74 53 14 26 38 86 65 27 34(2) 46745314263886652734(3) 46537414263886652734(4) 14465374263886652734(5) 14264653743886652734(6) 14263846537486 652734(7) 1426384653

10、7486 652734(8) 14263846536574 862734(9) 14262738465365 748634(10) 14 26 27 34 38 46 53 65 74 86 2.(11) 4674531426388665 2734(12) 4653142638746527 3486(13) 4614263853652734 7486(14) 1426384653273465 7486(15) 14263846273453657486(16) 14263827344653657486(17) 14262734384653657486(18) 142627343846536574

11、863.(0) 46 74 53 14 26 38 86 65 27 34(1) 34 27 38 14 26 46 86 65 53 74(2) 26 27 14 34 38 46 74 65 53 86(3) 1426 27 3438 46 5365 74 86(4) 1426 27 3438 46 5365 74 864.(1) 4674 53 1426 38 8665 27 34(2) 1474 53 4626 38 8665 27 34(3) 14265346743886652734(4) 14262746743886655334(5) 14262734743886655346(6)

12、 14262734387486655346(7) 1426273438468665 5374(8) 1426273438465365 8674(9) 1426273438465365 8674(10) 1426273438465365 74865. 構(gòu)成初始堆(即建堆)的過程：1 2 3 4 5 6 7 8 9 10(1) 46745314263886652734(2) 46745314263886652734(3) 46745314263886652734(4) 46743814265386652734(5) 461438272653866574 34(6) 142638273453866574 46進(jìn)行堆排序的過程：(7) 142638273453866574 46(8) 262738463453866574 14(9) 273438467453866526 14(10) 344638657453862726 14(11) 3846536574 8634272614(12) 4665538674 3834272614(13) 74 86 65 53 46 38 34 27 26 14(14) 86 74 65 53 46 38 34 27 26 146.(0) 46 74 53 14 26 3