数据结构专科辅导八
------排序的辅导练习题及解答
（一）单项选择题
1. 若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（ ）
A n B n+1 C n-1 D 1
2. 若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元素放有待查的键值
A n B n-1 C n+1 D 1
3. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）
A j-i B i-j-1 C i-j D i-j+1
4. 若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂性为（ ）
A O(1) B O(n) C O(n2) D O(log2n)
5. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟
A n B n+1 C n-1 D 2n
6. 对n个元素进行直接插入排序时间复杂性为（ ）
A O(1) B O(n) C O(n2) D O(log2n)
7. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换
A n B n-1 C n+1 D n/2
8. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(n)
9. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成
A 1 B n C n-1 D n/2
10. 在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（ ）
A n B n/2 C log2n D 2n
11. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量的一次在内
A n/2 B n-1 C n D n+1
12. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）躺
A n B n/2 C log2n D 2n
13. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）躺
A n B n-1 C n/2 D log2n
14. 在对n个元素进行快速排序的过程中，平均情况下的时间复杂性为（ ）
A 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. 在对n个元素进行快速排序
的过程中，平均情况下的空间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(nlog2n)
17. 在对n个元素进行快速排序的过程中，最坏情况下的空间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(nlog2n)
18. 在对n个元素进行直接插入排序的过程中，算法的空间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(nlog2n)
19. 假定对元素序列（3, 7, 5, 9, 1）进行快速排序，则进行第一次划分时需要移动元素的次数为（ ），假定不包括开始把基准元素移动到临时变量的一次计算在内
A 1 B 2 C 3 D 4
20. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）
A 1, 3, 5, 7, 9 B 9, 7, 5, 3, 1
C 5, 3, 1, 7, 9 D 5, 7, 9, 1, 3
21. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）
A 2 B 3 C 4 D 5
22．在对n个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换
A n B n+1 C n-1 D n/2
22．在对n个元素进行直接选择排序的过程中，在第i趟需要从（ ）个元素中选择出最小值元素
A
A n-i+1 B n-i C i D i+1
23. 若对n个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(n)
24. 若对n个元素进行堆排序，则在构成初始堆的过程中需要进行（ ）次筛运算
A 1 B n/2 C n D n-1
25. 若对n个元素进行堆排序，则在由初始堆进行每躺排序的的过程中，共需要进行（ ）次筛运算
A n+1 B n/2 C n D n-1
26. 若对n个元素进行堆排序，则每次进行筛运算的时间复杂性为( )
A O(1) B O(log2n) C O(n2) D O(n)
27. 在对n个元素进行堆排序的过程中，时间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(nlog2n)
28. 在对n个元素进行堆排序的过程中，空间复杂性为（ ）
A O(1) B O(log2n) C O(n2) D O(nlog2n)
29. 假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ ）
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. 假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后得到的结果为（ ）
A 3, 5, 7, 9, 12, 10, 15,
1 B 3, 5, 9, 7, 12, 10, 15, 1
A 3, 7, 5, 9, 12, 10, 15, 1 B 3, 5, 7, 12, 9, 10, 15, 1
31. 若对n个元素进行归并排序，则进行归并的趟数为（ ）
A n B n-1 C n/2 D ?log2n?
32. 若对n个元素进行归并排序，则进行每一趟归并的时间复杂性为（ ）
A O(1) B O(log2n) C O(n) D O(n2)
33. 若一个元素序列基本有序，则选用（ ）方法较快
A 直接插入排序 B 直接选择排序
C 堆排序 D 快速排序
34. 若要从1000个元素中得到10个最小值元素，最好采用（ ）方法
A 直接插入排序 B 直接选择排序
C 堆排序 D 快速排序
35. 若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法
A 直接插入排序 B 归并排序
C 堆排序 D 快速排序
36. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（ ）方法
A 直接插入排序 B 归并排序
C 堆排序 D 快速排序
37. 在下列排序方法中，空间复杂性为O(log2n)的方法为（ ）
A 直接选择排序 B 归并排序
C 堆排序 D 快速排序
38. 在平均情况下速度最快的排序方法为（ ）
A 直接选择排序 B 归并排序
C 堆排序 D 快速排序
（二）填空题
1．每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做________排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序
2．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序
3．在直接选择排序中，记录比较次数的时间复杂性为________，记录移动次数的时间复杂性为________
4. 在堆排序的过程中，对n个记录建立初始堆需要进行________次筛运算，由初始堆到堆排序结束，需要对树根结点进行_______次筛运算
5．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为________，整个堆排序过程的时间复杂性为________
6. 对n个记录进行冒泡排序时，最少的比较次数为________，最少的趟数为_______
7. 快速排序在平均情况下的时间复杂性为________，在最坏情况下的时间复杂性为________
8．快速排序在平均情况下的空间复杂性为________，在最坏情况下的空间复杂性为________
9．在二路归并排序中，
对n个记录进行归并的趟数为________
10. 在归并排序中，进行每趟归并的时间复杂性为________，整个排序过程的时间复杂性为________，空间复杂性为________
11．对20个记录进行归并排序时，共需要进行________趟归并，在第三趟归并时是把长度为________的有序表两两归并为长度为________的有序表
12. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较________次
13. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接选择排序，用k表示最小值元素的下标，进行第一趟时k的初值为1，则在第一趟选择最小值的过程中，k的值被修改________次
14．若对一组记录(76,38,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为________的位置
15．假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立的初始小根堆为____________________
16．假定一个堆为(38,40,56,79,46,84)，则利用堆排序方法进行第一躺交换和对根结点筛运算后得到的结果为____________________
17. 假定一组记录为(46,79,56,38,40,84)，在冒泡排序的过程中进行第一趟排序后的结果为____________________
18. 假定一组记录为(46,79,56,,38,40,84,43)，在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第_______个元素的位置
19. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，共需要________趟排序
20. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，含有两个或两个以上元素的排序区间的个数为________个
21. 假定一组记录为(46,79,56,25,76,38,40,80)，对其进行快速排序的第一次划分后，右区间内元素的个数为__________
22. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为____________________
23．假定一组记录为(46,79,56,38,40,80,46,75)，对其进行归并排序的过程中，第二趟归并后的第2个子表为________________
24．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为________________
25．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为________________
26．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要__________趟完成
27．假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________
28. 在时间复杂性为O(nl
og2n)的所有排序方法中，________排序方法是稳定的
29．在时间复杂性为O(n2)的所有排序方法中，________排序方法是不稳定的
30．在所有排序方法中，________排序方法采用的是二分法的思想
31．在所有排序方法中，________方法使数据的组织采用的是完全二叉树的结构
32．在所有排序方法中，________方法采用的是两两有序表合并的思想
33．________排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮
34．________排序方法能够每次使无序表中的第一个记录插入到有序表中
35．________排序方法能够每次从无序表中顺序查找出一个最小值
（三）应用题
1. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果
2. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果
3. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果
4. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接选择排序法进行排序时每一趟的排序结果
5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果
6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果
（四）算法设计题
1. 已知奇偶转换排序方法如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较，第二趟对所有偶数i，将a[i]和a[i+1]进行比较，每次比较时若a[i]>a[i+1]，则将两者交换，重复以上过程，直到整个数组有序
(1) 试问：排序结束的条件是什么？
(2) 编写一个实现上述排序过程的算法：void oesort(int a[], int n)
2. 一个线性表中的元素的正整数或负整数，设计一个算法，将正整数和负整数分开，使线性表的前部为负整数，后部为正整数，不要求对它们排序，但要求尽量减少交换次数
3．编写一个直接插入排序算法，使得查找插入位置时不是采用顺序的方法而是采用二分的方法
4．编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最小值并同第一个元素交换，再从待排序区间中选择出一个最大值并同最后一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止
练习题参考解答
（一）单项选择题
1. A 2. C 3. D 4. B 5. C 6. C
7. B 8. D 9. A 10. B 11. D 12. 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．快速 归并
3．O(n2) O(n) 4．n/2 n-1
5．O(log2n) O(nlog2n) 6．n-1 1
7．O(nlog2n) O(n2) 8. O(log2n) O(n)
9．?log2n? 10．O(n) O(nlog2n) O(n)
11．5 4 8 12．4
13．2 14．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 22．[40 38]46[56 79 80]
23．[40 46 75 80] 24．3
25. [28 46] 26. 4
27. [38 46 56 79][40 80] 28. 归并
29. 直接选择 30. 快速
31. 堆排序 32. 归并排序
33. 冒泡 34. 直接插入
35. 直接选择
（三）应用题
1.
(0) [46] 74 53 14 26 38 86 65 27 34
(1) [46 74] 53 14 26 38 86 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 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 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 65 [86 74]
(9) 14 26 27 34 38 46 53 65 74 [86]
5.
构成初始堆（即建堆
）的过程：
1 2 3 4 5 6 7 8 9 10
(0) 46 74 53 14 26 38 86 65 27 34
(1) 46 74 53 14 26 38 86 65 27 34
(2) 46 74 53 14 26 38 86 65 27 34
(3) 46 74 38 14 26 53 86 65 27 34
(4) 46 14 38 27 26 53 86 65 74 34
(5) 14 26 38 27 34 53 86 65 74 46
进行堆排序的过程：
(0) 14 26 38 27 34 53 86 65 74 46
(1) 26 27 38 46 34 53 86 65 74 [14]
(2) 27 34 38 46 74 53 86 65 [26 14]
(3) 34 46 38 65 74 53 86 [27 26 14]
(4) 38 46 53 65 74 86 [34 27 26 14]
(5) 46 65 53 86 74 [38 34 27 26 14]
(6) 53 65 74 86 [46 38 34 27 26 14]
(7) 65 86 74 [53 46 38 34 27 26 14]
(8) 74 86 [65 53 46 38 34 27 26 14]
(9) 86 [74 65 53 46 38 34 27 26 14]
6.
(0) [46][74][53][14][26][38][86][65][27][34]
(1) [46 74][14 53][26 38][65 86][27 34]
(2) [14 46 53 74][26 38 65 86][27 34]
(3) [14 26 38 46 53 65 74 86][27 34]
(3) [14 26 27 34 38 46 53 65 74 86]
（四）算法设计题
每个算法设计题解答从略
1
1
2、业精于勤，荒于嬉；行成于思，毁于随——韩愈下载本文
