習題10排序及其答案

1、習題10、單項選擇題1,若對n個元素進行直接插入排序，在進行第i趟排序時，假定元素ri+1的插入位置為rj,則需要移動元素的次數(shù)為()。A.j-iB.i-j-1C.i-jD.i-j+12,若對n個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為()。一一一一一2一A.O(1)B.O(n)C,O(n)D.O(log2n)3.在n個元素進行直接插入排序的過程中，共需要進行()趟。A.nB.n+1C.n-1D.2n4,對n個元素進行直接插入排序時間復雜度為()。2A.O(1)B.O(n)C.O(n2)D.O(log2n)5 .在n個元素進行冒泡排序的過程中，第一趟排

2、序至多需要進行()對相鄰元素之間的交換。A.nB.n-1C.n+1D.n/26 .在n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為()。A.O(1)B.O(log2n)C.O(n2)D,O(n)7 .在n個元素進行冒泡排序的過程中，至少需要()趟完成。A.1B.nC.n-1D.n/28 .在n個元素進行快速排序的過程中，若每次劃分得到的左、右兩個子區(qū)間中元素的個數(shù)相等或只差一個，則整個排序過程得到的含兩個或兩個元素的區(qū)間個數(shù)大致為()。A.nB.n/2C.log2nD.2n9 .在n個元素進行快速排序的過程中，第一次劃分最多需要移動()次元素，包括開始把支點元素移動到臨時變量的一次在內(nèi)

3、。A.n/2B.n-1C.nD.n+110 .在又n個元素進行快速排序的過程中，最好情況下需要進行()躺。A.nB.n/2C.log2nD.2n11 .在n個元素進行快速排序的過程中，最壞情況下需要進行()躺。A.nB.n-1C.n/2D.log2n12 .在n個元素進行快速排序的過程中，平均情況下的時間復雜度為()。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)13 .在n個元素進行快速排序的過程中，最壞情況下的時間復雜度為()。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)14 .在n個元素進行快速排序的過程中，平均情況下的空間復雜度為()。A.

4、O(1)B.O(log2n)C.O(n2)D.O(nlog2n)15 .在n個元素進行直接插入排序的過程中，算法的空間復雜度為()。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)16 .對下列四個序列進行快速排序，各以第一個元素為基準進行第一次劃分，則在該次劃分過程中需要移動元素次數(shù)最多的序列為()。A.1,3,5,7,9B,9,7,5,3,1C.5,3,1,7,9D.5,7,9,1,317 .假定對元素序列(7,3,5,9,1,12,8,15)進行快速排序，則進行第一次劃分后，得到的左區(qū)間中元素的個數(shù)為()。A.2B.3C.4D.518 .在n個元素進行簡單選擇排序的過

5、程中，需要進行()趟選擇和交換。A.nB.n+1C.n-1D.n/219 .在n個元素進行堆排序的過程中，時間復雜度為()。A.O(1)B.O(logn)C.O(n2)D.O(nlog2n)20 .在n個元素進行堆排序的過程中，空間復雜度為()。A.O(1)B.O(logn)C.O(n2)D.O(nlog?n)21 .假定對元素序列(7,3,5,9,1,12)進行堆排序，并且采用小根堆，則由初始數(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,722 .假定一個初始堆為(1,5,3,9,12,7,15,10),

6、則進行第一趟堆排序后得到的結(jié)果為()。A.3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,123 .若又n個元素進行歸并排序，則進行歸并的趟數(shù)為()。A.nB.n-1C.n/2D.log2nl24 .若一個元素序列基本有序，則選用()方法較快。A.直接插入排序B.簡單選擇排序C.堆排序D.快速排序25 .若要從1000個元素中得到10個最小值元素，最好采用()方法。A.直接插入排序B.簡單選擇排序C.堆排序D.快速排序26 .若要對1000個元素排序，要求既快又穩(wěn)定，則最好采用()方法。A

7、.直接插入排序B.歸并排序C.堆排序D.快速排序27 .若要對1000個元素排序，要求既快又節(jié)省存儲空間，則最好采用()方法。A.直接插入排序B.歸并排序C.堆排序D.快速排序28 .在平均情況下速度最快的排序方法為()。A.簡單選擇排序B.歸并排序C.堆排序D.快速排序二、填空題1 .每次從無序子表中取出一個元素，把它插入到有序子表中的適當位置，此種排序方法叫做排序；每次從無序子表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。2 .每次直接或通過支點元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做排序；每次使兩個相鄰的有序表合并成一個有序表

8、的排序方法叫做排序。3 .在簡單選擇排序中，記錄比較次數(shù)的時間復雜度為，記錄移動次數(shù)的時間復雜度為。4 .對n個記錄進行冒泡排序時，最少的比較次數(shù)為,最少的趟數(shù)為5 .快速排序在平均情況下的時間復雜度為,在最壞情況下的時間復雜度為O6,若對一組記錄(46,79,56,38,40,80,35,50,74)進行直接插入排序，當把第8個記錄插入到前面已排序的有序表時，為尋找插入位置需比較次。7 .假定一組記錄為(46,79,56,38,40,84),則利用堆排序方法建立的初始小根堆為8 .假定一組記錄為(46,79,56,38,40,84),在冒泡排序的過程中進行第一趟排序后的結(jié)果為。9 .假定一組

9、記錄為(46,79,56,64,38,40,84,43),在冒泡排序的過程中進行第一趟排序時，元素79將最終下沉到其后第個元素的位置。10 .假定一組記錄為(46,79,56,38,40,80,對其進行快速排序的過程中，共需要趟排序。11 .假定一組記錄為(46,79,56,38,40,8。，對其進行快速排序的過程中，含有兩個或兩個以上元素的排序區(qū)間的個數(shù)為個。12 .假定一組記錄為(46,79,56,25,76,38,40,80),對其進行快速排序的第一次劃分后，右區(qū)間內(nèi)元素的個數(shù)為。13 .假定一組記錄為(46,79,56,38,40,80),對其進行快速排序的第一次劃分后的結(jié)果為14 .

10、假定一組記錄為(46,79,56,38,40,80,46,75,28,46,對其進行歸并排序的過程中，第二趟歸并后的子表個數(shù)為。15 .假定一組記錄為(46,79,56,38,40,80,46,75,28,46,對其進行歸并排序的過程中，第三趟歸并后的第2個子表為。16 .假定一組記錄為(46,79,56,38,40,80,46,75,28,46,對其進行歸并排序的過程中，供需要趟完成。17 .在時間復雜度為O(nlog2n)的所有排序方法中，排序方法是穩(wěn)定的。18 .在時間復雜度為O(n2)的所有排序方法中，排序方法是不穩(wěn)定的。19 .在所有排序方法中，排序方法采用的是二分法的思想。20 .

11、在所有排序方法中，方法使數(shù)據(jù)的組織采用的是完全二叉樹的結(jié)構(gòu)。21 .在所有排序方法中，方法采用的是兩兩有序表合并的思想。22 .排序方法使鍵值大的記錄逐漸下沉，使鍵值小的記錄逐漸上浮。23 .排序方法能夠每次使無序表中的第一個記錄插入到有序表中。24 .排序方法能夠每次從無序表中順序查找出一個最小值。三、應用題1 .已知一組記錄為時每一趟的排序結(jié)果。2 .已知一組記錄為一趟的排序結(jié)果。3 .已知一組記錄為一趟的排序結(jié)果。4 .已知一組記錄為時每一趟的排序結(jié)果。5 .已知一組記錄為趟的排序結(jié)果。6 .已知一組記錄為一趟的排序結(jié)果。(46,74,53,14,26,38,86,65,27,34),給

12、出采用直接插入排序法進行排序(46,74,53,14,26,38,86,65,27,34),給出采用冒泡排序法進行排序時每(46,74,53,14,26,38,86,65,27,34),給出采用快速排序法進行排序時每(46,74,53,14,26,38,86,65,27,34),給出采用簡單選擇排序法進行排序(46,74,53,14,26,38,86,65,27,34),給出采用堆排序法進行排序時每(46,74,53,14,26,38,86,65,27,34),給出采用歸并排序法進行排序時每四、算法設(shè)計題1 .編寫一個雙向起泡的排序算法，即相鄰兩趟向相反方向起泡。2 .試以單鏈表為存儲結(jié)構(gòu)實現(xiàn)

13、簡單選擇排序的算法。習題10參考答案一、單項選擇題1.D2.B3.C4.C5.B6.D7.A8.B9.D10.C11.B12.D13.C14.D15.A16.D17.B18.C19.D20.A21.B22.A23.D24.A25.B26.B27.C28.D、填空題1.插入，選擇3.O(n2),O(n)5.O(nlog2n),0(n2)7.(38,40,56,79,46,84)9.411.413.40384656798015.284617.歸并19.快速21.歸并排序23.直接插入三、應用題2.快速，歸并4.n-1,16.48.(46,56,38,40,79,84)10. 312. 414. 3

14、16. 418.直接選擇20.堆排序22.冒泡24.直接選擇1.(0)46745314263886652734(1)46745314263886652734(2)46537414263886652734(3)14465374263886652734(4)14264653743886652734(5)14263846537486652734(6)14263846537486652734(7)14263846536574862734(8)14262738465365748634(9)142627343846536574862.(0)46745314263886652734(1)4653142638

15、7465273486(2)46142638536527347486(3)14263846532734657486(4)14263846273453657486(5)14263827344653657486(6)14142626272734343838464653536565747486863.(0)46745314263886652734(1)34273814264686655374(2)26271434384674655386(3)14262734384653657486(4)142627343846536574864.(0)46745314263886652734(1)1474534626

16、3886652734(2)14265346743886652734(3)14262746743886655334(4)14262734743886655346(5)14262734387486655346(6)1426273438468665537414262734384653658674(8)14262734384653658674(9)142627343846536574865.構(gòu)成初始堆（即建堆）的過程：12345678910(0)46745314263886652734(1)46745314263886652734(2)46745314263886652734(3)4674381426

17、5386652734(4)46143827265386657434(5)14263827345386657446進行堆排序的過程：(0)14263827345386657446(1)26273846345386657414(2)27343846745386652614(3)34463865745386272614(4)38465365748634272614(5)46655386743834272614(6)5365748646383427261465867453463834272614(8)74866553463834272614(9)867465534638342726146.(0)467

18、45314263886652734(1)46741453263865862734(2)14465374263865862734(3)14263846536574862734(3)14262734384653657486四、算法設(shè)計題1.voidBubble_Sort2(inta,intn)相鄰兩趟是反方向起泡的冒泡排序算法low=0;high=n-1;冒泡的上下界change=1;while(low<high&&change)change=0;for(i=low;i<high;i+)/從上向下起泡if(ai>ai+1)ai<->ai+1;change=1;high-;/修改上界for(i=high;i>low;i-)/從下向上起泡if(ai<ai-1)ai<->ai-1;change=1;low+;修改下界/while/Bubble_Sort22.voidLinkList_Select_Sort(LinkList&L)/單鏈表上的簡單選擇排序算法for(p=L;p->next->next;p=p->next)q=p->next;x=q->