數(shù)據(jù)結(jié)構(gòu)?？戚o導(dǎo)八11

1、1、敏而好學(xué)，不恥下問(wèn)孔子 數(shù)據(jù)結(jié)構(gòu)?？戚o導(dǎo)八 -排序的輔導(dǎo)練習(xí)題及解答 （一）單項(xiàng)選擇題 1. 若對(duì)n個(gè)元素進(jìn)行直接插入排序，則進(jìn)行第i趟排序過(guò)程前，有序表中的元素個(gè)數(shù)為（ ） A n B n+1 C n-1 D 1 2. 若對(duì)n個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第i趟排序時(shí)，為尋找插入位置最多需要進(jìn)行（ ）次元素的比較，假定第0號(hào)元素放有待查的鍵值 A n B n-1 C n+1 D 1 3. 若對(duì)n個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第i趟排序時(shí)，假定元素ri+1的插入位置為rj，則需要移動(dòng)元素的次數(shù)為（ ） A j-i B i-j-1 C i-j D i-j+1 4. 若對(duì)n個(gè)元素進(jìn)行直接插入排

2、序，則進(jìn)行任一趟排序的過(guò)程中，為尋找插入位置而需要的時(shí)間復(fù)雜性為（ ） A O(1 B O(n C O(n2 D O(log2n 5. 在對(duì)n個(gè)元素進(jìn)行直接插入排序的過(guò)程中，共需要進(jìn)行（ ）趟 A n B n+1 C n-1 D 2n 6. 對(duì)n個(gè)元素進(jìn)行直接插入排序時(shí)間復(fù)雜性為（ ） A O(1 B O(n C O(n2 D O(log2n 7. 在對(duì)n個(gè)元素進(jìn)行冒泡排序的過(guò)程中，第一趟排序至多需要進(jìn)行（ ）對(duì)相鄰元素之間的交換 A n B n-1 C n+1 D n/2 8. 在對(duì)n個(gè)元素進(jìn)行冒泡排序的過(guò)程中，最好情況下的時(shí)間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D

3、 O(n 9. 在對(duì)n個(gè)元素進(jìn)行冒泡排序的過(guò)程中，至少需要（ ）趟完成 A 1 B n C n-1 D n/2 10. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，若每次劃分得到的左、右兩個(gè)子區(qū)間中元素的個(gè)數(shù)相等或只差一個(gè)，則整個(gè)排序過(guò)程得到的含兩個(gè)或兩個(gè)元素的區(qū)間個(gè)數(shù)大致為（ ） A n B n/2 C log2n D 2n 11. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，第一次劃分最多需要移動(dòng)（ ）次元素，包括開始把基準(zhǔn)元素移動(dòng)到臨時(shí)變量的一次在內(nèi) A n/2 B n-1 C n D n+1 12. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最好情況下需要進(jìn)行（ ）躺 A n B n/2 C log2n D 2n

4、 13. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最壞情況下需要進(jìn)行（ ）躺 A n B n-1 C n/2 D log2n 14. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，平均情況下的時(shí)間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 15. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最壞情況下的時(shí)間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 16. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，平均情 況下的空間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 17. 在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最壞情況下

5、的空間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 18. 在對(duì)n個(gè)元素進(jìn)行直接插入排序的過(guò)程中，算法的空間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 19. 假定對(duì)元素序列（3, 7, 5, 9, 1）進(jìn)行快速排序，則進(jìn)行第一次劃分時(shí)需要移動(dòng)元素的次數(shù)為（ ），假定不包括開始把基準(zhǔn)元素移動(dòng)到臨時(shí)變量的一次計(jì)算在內(nèi) A 1 B 2 C 3 D 4 20. 對(duì)下列四個(gè)序列進(jìn)行快速排序，各以第一個(gè)元素為基準(zhǔn)進(jìn)行第一次劃分，則在該次劃分過(guò)程中需要移動(dòng)元素次數(shù)最多的序列為（ ） A 1, 3, 5, 7, 9 B 9, 7,

6、 5, 3, 1 C 5, 3, 1, 7, 9 D 5, 7, 9, 1, 3 21. 假定對(duì)元素序列（7, 3, 5, 9, 1, 12, 8, 15）進(jìn)行快速排序，則進(jìn)行第一次劃分后，得到的左區(qū)間中元素的個(gè)數(shù)為（ ） A 2 B 3 C 4 D 5 22在對(duì)n個(gè)元素進(jìn)行直接選擇排序的過(guò)程中，需要進(jìn)行（ ）趟選擇和交換 A n B n+1 C n-1 D n/2 22在對(duì)n個(gè)元素進(jìn)行直接選擇排序的過(guò)程中，在第i趟需要從（ ）個(gè)元素中選擇出最小值元素 A A n-i+1 B n-i C i D i+1 23. 若對(duì)n個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過(guò)程中，為尋找最小值元素所需要的時(shí)

7、間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(n 24. 若對(duì)n個(gè)元素進(jìn)行堆排序，則在構(gòu)成初始堆的過(guò)程中需要進(jìn)行（ ）次篩運(yùn)算 A 1 B n/2 C n D n-1 25. 若對(duì)n個(gè)元素進(jìn)行堆排序，則在由初始堆進(jìn)行每躺排序的的過(guò)程中，共需要進(jìn)行（ ）次篩運(yùn)算 A n+1 B n/2 C n D n-1 26. 若對(duì)n個(gè)元素進(jìn)行堆排序，則每次進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜性為( A O(1 B O(log2n C O(n2 D O(n 27. 在對(duì)n個(gè)元素進(jìn)行堆排序的過(guò)程中，時(shí)間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 28. 在對(duì)n個(gè)

8、元素進(jìn)行堆排序的過(guò)程中，空間復(fù)雜性為（ ） A O(1 B O(log2n C O(n2 D O(nlog2n 29. 假定對(duì)元素序列（7, 3, 5, 9, 1, 12）進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為（ ） A 1, 3, 5, 7, 9, 12 B 1, 3, 5, 9, 7, 12 C 1, 5, 3, 7, 9, 12 D 1, 5, 3, 9, 12, 7 30. 假定一個(gè)初始堆為(1, 5, 3, 9, 12, 7, 15, 10，則進(jìn)行第一趟堆排序后得到的結(jié)果為（ ） A 3, 5, 7, 9, 12, 10, 15, 1 B 3, 5, 9, 7, 12

9、, 10, 15, 1 A 3, 7, 5, 9, 12, 10, 15, 1 B 3, 5, 7, 12, 9, 10, 15, 1 31. 若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為（ ） A n B n-1 C n/2 D ?log2n? 32. 若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行每一趟歸并的時(shí)間復(fù)雜性為（ ） A O(1 B O(log2n C O(n D O(n2 33. 若一個(gè)元素序列基本有序，則選用（ ）方法較快 A 直接插入排序 B 直接選擇排序 C 堆排序 D 快速排序 34. 若要從1000個(gè)元素中得到10個(gè)最小值元素，最好采用（ ）方法 A 直接插入排序 B 直接選擇排序

10、 C 堆排序 D 快速排序 35. 若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用（ ）方法 A 直接插入排序 B 歸并排序 C 堆排序 D 快速排序 36. 若要對(duì)1000個(gè)元素排序，要求既快又節(jié)省存儲(chǔ)空間，則最好采用（ ）方法 A 直接插入排序 B 歸并排序 C 堆排序 D 快速排序 37. 在下列排序方法中，空間復(fù)雜性為O(log2n的方法為（ ） A 直接選擇排序 B 歸并排序 C 堆排序 D 快速排序 38. 在平均情況下速度最快的排序方法為（ ） A 直接選擇排序 B 歸并排序 C 堆排序 D 快速排序 （二）填空題 1每次從無(wú)序子表中取出一個(gè)元素，把它插入到有序子表中的適當(dāng)

11、位置，此種排序方法叫做_排序；每次從無(wú)序子表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_排序 2每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做_排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做_排序 3在直接選擇排序中，記錄比較次數(shù)的時(shí)間復(fù)雜性為_，記錄移動(dòng)次數(shù)的時(shí)間復(fù)雜性為_ 4. 在堆排序的過(guò)程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行_次篩運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹根結(jié)點(diǎn)進(jìn)行_次篩運(yùn)算 5在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜性為_，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜性為_ 6. 對(duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)

12、，最少的比較次數(shù)為_，最少的趟數(shù)為_ 7. 快速排序在平均情況下的時(shí)間復(fù)雜性為_，在最壞情況下的時(shí)間復(fù)雜性為_ 8快速排序在平均情況下的空間復(fù)雜性為_，在最壞情況下的空間復(fù)雜性為_ 9在二路歸并排序中，對(duì)n個(gè)記錄進(jìn)行歸并 的趟數(shù)為_ 10. 在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜性為_，整個(gè)排序過(guò)程的時(shí)間復(fù)雜性為_，空間復(fù)雜性為_ 11對(duì)20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行_趟歸并，在第三趟歸并時(shí)是把長(zhǎng)度為_的有序表兩兩歸并為長(zhǎng)度為_的有序表 12. 若對(duì)一組記錄(46,79,56,38,40,80,35,50,74進(jìn)行直接插入排序，當(dāng)把第8個(gè)記錄插入到前面已排序的有序表時(shí)，為尋找插入位置需比較

13、_次 13. 若對(duì)一組記錄(46,79,56,38,40,80,35,50,74進(jìn)行直接選擇排序，用k表示最小值元素的下標(biāo)，進(jìn)行第一趟時(shí)k的初值為1，則在第一趟選擇最小值的過(guò)程中，k的值被修改_次 14若對(duì)一組記錄(76,38,62,53,80,74,83,65,85進(jìn)行堆排序，已知除第一個(gè)元素外，以其余元素為根的結(jié)點(diǎn)都已是堆，則對(duì)第一個(gè)元素進(jìn)行篩運(yùn)算時(shí)，它將最終被篩到下標(biāo)為_的位置 15假定一組記錄為(46,79,56,38,40,84，則利用堆排序方法建立的初始小根堆為_ 16假定一個(gè)堆為(38,40,56,79,46,84，則利用堆排序方法進(jìn)行第一躺交換和對(duì)根結(jié)點(diǎn)篩運(yùn)算后得到的結(jié)果為_

14、17. 假定一組記錄為(46,79,56,38,40,84，在冒泡排序的過(guò)程中進(jìn)行第一趟排序后的結(jié)果為_ 18. 假定一組記錄為(46,79,56,64,38,40,84,43，在冒泡排序的過(guò)程中進(jìn)行第一趟排序時(shí)，元素79將最終下沉到其后第_個(gè)元素的位置 19. 假定一組記錄為(46,79,56,38,40,80，對(duì)其進(jìn)行快速排序的過(guò)程中，共需要_趟排序 20. 假定一組記錄為(46,79,56,38,40,80，對(duì)其進(jìn)行快速排序的過(guò)程中，含有兩個(gè)或兩個(gè)以上元素的排序區(qū)間的個(gè)數(shù)為_個(gè) 21. 假定一組記錄為(46,79,56,25,76,38,40,80，對(duì)其進(jìn)行快速排序的第一次劃分后，右區(qū)間

15、內(nèi)元素的個(gè)數(shù)為_ 22. 假定一組記錄為(46,79,56,38,40,80，對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為_ 23假定一組記錄為(46,79,56,38,40,80,46,75，對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟歸并后的第2個(gè)子表為_ 24假定一組記錄為(46,79,56,38,40,80,46,75,28,46，對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟歸并后的子表個(gè)數(shù)為_ 25假定一組記錄為(46,79,56,38,40,80,46,75,28,46，對(duì)其進(jìn)行歸并排序的過(guò)程中，第三趟歸并后的第2個(gè)子表為_ 26假定一組記錄為(46,79,56,38,40,80,46,75,28,46，對(duì)其進(jìn)

16、行歸并排序的過(guò)程中，供需要_趟完成 27假定一組記錄為(46,79,56,38,40,80，對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟歸并后的結(jié)果為_ 28. 在時(shí)間復(fù)雜性為O(nlog2n的所有排序方 法中，_排序方法是穩(wěn)定的 29在時(shí)間復(fù)雜性為O(n2的所有排序方法中，_排序方法是不穩(wěn)定的 30在所有排序方法中，_排序方法采用的是二分法的思想 31在所有排序方法中，_方法使數(shù)據(jù)的組織采用的是完全二叉樹的結(jié)構(gòu) 32在所有排序方法中，_方法采用的是兩兩有序表合并的思想 33_排序方法使鍵值大的記錄逐漸下沉，使鍵值小的記錄逐漸上浮 34_排序方法能夠每次使無(wú)序表中的第一個(gè)記錄插入到有序表中 35_排序方法

17、能夠每次從無(wú)序表中順序查找出一個(gè)最小值 （三）應(yīng)用題 1. 已知一組記錄為(46,74,53,14,26,38,86,65,27,34，給出采用直接插入排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果 2. 已知一組記錄為(46,74,53,14,26,38,86,65,27,34，給出采用冒泡排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果 3. 已知一組記錄為(46,74,53,14,26,38,86,65,27,34，給出采用快速排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果 4. 已知一組記錄為(46,74,53,14,26,38,86,65,27,34，給出采用直接選擇排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果 5. 已知一組記錄為(46

18、,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é)果 （四）算法設(shè)計(jì)題 1. 已知奇偶轉(zhuǎn)換排序方法如下所述：第一趟對(duì)所有奇數(shù)i，將ai和ai+1進(jìn)行比較，第二趟對(duì)所有偶數(shù)i，將ai和ai+1進(jìn)行比較，每次比較時(shí)若ai>ai+1，則將兩者交換，重復(fù)以上過(guò)程，直到整個(gè)數(shù)組有序 (1 試問(wèn)：排序結(jié)束的條件是什么？ (2 編寫一個(gè)實(shí)現(xiàn)上述排序過(guò)程的算法：void oesort(int a, int n 2. 一個(gè)線性表中的元

19、素的正整數(shù)或負(fù)整數(shù)，設(shè)計(jì)一個(gè)算法，將正整數(shù)和負(fù)整數(shù)分開，使線性表的前部為負(fù)整數(shù)，后部為正整數(shù)，不要求對(duì)它們排序，但要求盡量減少交換次數(shù) 3編寫一個(gè)直接插入排序算法，使得查找插入位置時(shí)不是采用順序的方法而是采用二分的方法 4編寫一個(gè)對(duì)整型數(shù)組An+1中的A1至An元素進(jìn)行選擇排序的算法，使得首先從待排序區(qū)間中選擇出一個(gè)最小值并同第一個(gè)元素交換，再?gòu)拇判騾^(qū)間中選擇出一個(gè)最大值并同最后一個(gè)元素交換，反復(fù)進(jìn)行直到待排序區(qū)間中元素的個(gè)數(shù)不超過(guò)1為止 練習(xí)題參考解答 （一）單項(xiàng)選擇題 1. A 2. C 3. D 4. B 5. C 6. C 7. B 8. D 9. A 10. B 11. D 12.

20、 C 13. B 14. D 15. C 16. B 17. C 18. A 19. B 20. D 21. B 22. C 23. D 24. B 25. D 26. B 27. D 28. A 29. B 30. A 31. D 32. C 33. A 34. B 35. B 36. C 37. D 38. D （二）填空題 1插入 選擇 2快速 歸并 3O(n2 O(n 4n/2 n-1 5O(log2n O(nlog2n 6n-1 1 7O(nlog2n O(n2 8. O(log2n O(n 9?log2n? 10O(n O(nlog2n O(n 115 4 8 124 132 14

21、8 15. (38,40,56,79,46,84 16. (40,46,56,79,84,38 17. (46,56,38,40,79,84 18. 4 19. 3 20. 4 21. 4 2240 384656 79 80 2340 46 75 80 243 25. 28 46 26. 4 27. 38 46 56 7940 80 28. 歸并 29. 直接選擇 30. 快速 31. 堆排序 32. 歸并排序 33. 冒泡 34. 直接插入 35. 直接選擇 （三）應(yīng)用題 1. (0 46 74 53 14 26 38 86 65 27 34 (1 46 74 53 14 26 38 86

22、65 27 34 (2 46 53 74 14 26 38 86 65 27 34 (3 14 46 53 74 26 38 86 65 27 34 (4 14 26 46 53 74 38 86 65 27 34 (5 14 26 38 46 53 74 86 65 27 34 (6 14 26 38 46 53 74 86 65 27 34 (7 14 26 38 46 53 65 74 86 27 34 (8 14 26 27 38 46 53 65 74 86 34 (9 14 26 27 34 38 46 53 65 74 86 2. (0 46 74 53 14 26 38 86

23、65 27 34 (1 46 53 14 26 38 74 65 27 34 86 (2 46 14 26 38 53 65 27 34 74 86 (3 14 26 38 46 53 27 34 65 74 86 (4 14 26 38 46 27 34 53 65 74 86 (5 14 26 38 27 34 46 53 65 74 86 (6 14 26 27 34 38 46 53 65 74 86 (7 14 26 27 34 38 46 53 65 74 86 3. (0 46 74 53 14 26 38 86 65 27 34 (1 34 27 38 14 26 46 86

24、65 53 74 (2 26 27 14 34 38 46 74 65 53 86 (3 14 26 27 34 38 46 53 65 74 86 (4 14 26 27 34 38 46 53 65 74 86 4. (0 46 74 53 14 26 38 86 65 27 34 (1 14 74 53 46 26 38 86 65 27 34 (2 14 26 53 46 74 38 86 65 27 34 (3 14 26 27 46 74 38 86 65 53 34 (4 14 26 27 34 74 38 86 65 53 46 (5 14 26 27 34 38 74 86 65 53 46 (6 14 26 27 34 38 46 86 65 53 74 (7 14 26 27 34 38 46 53 65 86 74 (8 14 26 27 34 38 46 53