数据结构排序部分练习题

一、单选题

12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。 A．冒泡排序 B．快速排序 C．堆排序 D．归并排序

1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( ) A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k) 2．最好和最坏时间复杂度均为O(nlog2n)且稳定的排序方法是( )。 A．快速排序 B．堆排序 C．归并排序 D．基数排序 3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。 A．起泡排序 B．希尔排序 C．堆排序 D．快速排序 4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（ ） A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 5．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B．选择 C．希尔 D．快速 6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是( )。 A．堆排序 B．直接插入排序 C．快速排序 D．直接选择排序 7．关键字比较次数与数据的初始状态无关的排序算法是( )。 A．直接选择排序 B．冒泡排序 C．直接插入排序 D．希尔排序 8. 若一个元素序列基本有序，则选用（ ）方法较快。 A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序 9. 若要从1000个元素中得到4个最小值元素，最好采用（ ）方法。 A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序 10. 若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法。 A．直接插入排序 B．归并排序 C．堆排序 D．快速排序

11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（ ）方法。 A．直接插入排序 B．归并排序 C．堆排序 D．快速排序 12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（ ）。 A．直接选择排序 B．归并排序 C．堆排序 D．快速排序 13. 在平均情况下速度最快的排序方法为（ ）。 A．直接选择排序 B．归并排序 C．堆排序 D．快速排序

14、设有关键字初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，则用下列哪种排序方法进行第一趟扫描的结果为{F,H,C,D,P,A,M,Q,R,S,Y,X}？ A．直接插入排序 B．二路归并排序 C．以第一元素为基准的快速排序 D．基数排序

15．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A．插入 B．选择 C．希尔 D．二路归并 16．下面排序法中，( )排序法是不稳定的。 A．插入 B．冒泡 C．二路归并 D．堆 17.下列排序方法中，不稳定的是（ ） A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序

18. 在直接插入排序的第i趟排序前，有序表中的元素个数为（ ）。 A．i B．i+1 C．i-1 D．1

19. 在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元

素作监视哨。 A．i B．i-1 C．i+1 D．1

20. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）。 A．j-i B．i-j-1 C．i-j D．i-j+1

21. 对n个元素进行直接插入排序，则各趟排序中寻找插入位置的平均时间复杂性为（ ）。 A．O(1) B．O(n) C．O(n2) D．O(log2n) 22. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。 A．n B．n+1 C．n-1 D．2n 23. 对n个元素进行直接插入排序时间复杂性为（ ）。 A．O(1) B．O(n) C．O(n2) D．O(log2n) 24、n个记录直接插入排序时所需的记录最小比较次数是( ) A．n-1 B．n C．n(n-1)/2 D．n(n+1)/2 25. 对n个元素进行直接插入排序，空间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)

26. 对n个元素进行冒泡排序，第一趟至多需要进行（ ）对相邻元素之间的交换。 A．n B．n-1 C．n+1 D．n/2 27. 对n个元素进行冒泡排序，最好情况下的时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(n) 28. 对n个元素进行冒泡排序，至少需要（ ）趟完成。 A．1 B．n C．n-1 D．n/2

6．快速排序的记录移动次数（ ）比较次数，其总执行时间为0（nlog2n）。 A）大于 B）大于等于 C）小于等于 D）小于

29. 对n个元素进行快速排序，第一次划分最多需要移动（ ）次元素，假定包括基准和临时量之间的移动。 A．n/2 B．n-1 C．n D．n+1

30.对序列（3, 7, 5, 9, 1）进行快速排序，则第一次划分时需要移动元素的次数为（ ），假定不包括基准和临时量之间的移动。 A．1 B．2 C．3 D．4 31. 对n个元素进行快速排序，最好情况下需要进行（ ）趟。 A．n B．n/2 C．log2n D．2n 32. 对n个元素进行快速排序，最坏情况下需要进行（ ）趟。 A．n B．n-1 C．n/2 D．log2n 33. 对n个元素进行快速排序，平均情况下的时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n) 34. 对n个元素进行快速排序，最坏情况下的时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n) 35. 对n个元素进行快速排序，平均情况下的空间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n) 36. 对n个元素进行快速排序，最坏情况下的空间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)

37. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。

A．1, 3, 5, 7, 9 B． 9, 7, 5, 3, 1 C．5, 3, 1, 7, 9 D．5, 7, 9, 1, 3

38. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。 A．2 B．3 C．4 D．5

39．对n个元素进行直接选择排序，需要进行（ ）趟选择和交换。 A．n B．n+1 C．n-1 D．n/2

40．对n个元素进行直接选择排序，在第i趟需要从（ ）个元素中选择最小者。 A．n-i+1 B．n-I C．I D．i+1

41. 对n个元素进行直接选择排序，则各趟寻找最小值元素所需时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(n)

5．堆排序在最坏情况下，其时间复杂性为（ ）。 A）?(nlog2n) B）?(n2) C）?(log2n2) D）?(log2n) 42. 对n个元素进行堆排序，在构成初始堆的过程中需要进行（ ）次筛运算。 A．1 B．n/2 C．n D．n-1 43. 对n个元素进行堆排序，建初始堆后，还要进行( )次筛选运算。 A．n+1 B．n/2 C．n D．n-1 44. 对n个元素进行堆排序，每次筛运算的时间复杂性为( )。 A．O(1) B．O(log2n) C．O(n2) D．O(n) 45. 对n个元素进行堆排序，时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n) 46. 对n个元素进行堆排序，空间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n2) D．O(nlog2n)

12．对排序码(47、78、61、33、39、80)用堆排序的方法建立的初始堆为( )。 A．78、47、61、33、39、80 B．80、78、61、33、39、47 C．80、78、61、47、39、33 D．80、61、78、39、47、33 47. 假定用小根堆对（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

48. 假定初始堆为(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

49．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ） A．n B．2n－1 C．2n D．n-1 50. 若对n个元素进行归并排序，则进行归并的趟数为（ ）。 A．n B．n-1 C．n/2 D．?log2n? 51. 若对n个元素进行归并排序，则进行每一趟归并的时间复杂性为（ ）。 A．O(1) B．O(log2n) C．O(n) D．O(n2)

二、判断题

如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 对数据按关键字进行排序能够有效地提高查找速度。

直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，所以也是稳定的。

用直接选择排序方法分别对序列S1=(1,2,3,4,5,6,7)和序列S2=(7,5,3,2,4,1,6)进行排序，两者的比较次数不相同。

直接选择排序的比较次数与序列的初始状态无关。

堆排序法在最好和最坏情况下时间复杂性都是O(nlog2n)。 堆的存储表示是顺序的。

以中序方式遍历一个堆，则得到一个有序序列。

二路归并排序的核心操作是把两个有序序列合并为一个有序序列。 快速排序法总是效率最高的排序法。

顾名思义，快速排序法是在所有情况下，速度最快的排序方法。

三、填空题

11．最简单的交换排序方法是________________排序。 11．直接插入排序需要___________个记录的辅助空间。

12．在插入和选择排序中，若初始数据基本正序，则选用___________；若初始数据基本反序，则选用___________。

1．评价排序效率的主要标准是________。

2．在时间复杂性为O(n2)的所有排序方法中，____直接选择____排序方法是不稳定的。 3．在所有排序方法中，____快速____排序方法采用的是二分法的思想。

4．在所有排序方法中，____堆排序____方法使数据的组织采用的是完全二叉树的结构。 5．在所有排序方法中，____归并排序____方法采用的是两两有序表合并的思想。

3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为____3___。若A初始状态为递减排列，则记录的交换次数为____4___。 6．____冒泡____排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。 7．____直接插入____排序方法能够每次使无序表中的第一个记录插入到有序表中。 8．____直接选择____排序方法能够每次从无序表中顺序查找出一个最小值。

9．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__插入__排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__选择__排序。 10．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做__交换__排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做__归并__排序。

11．对n个数据进行直接插入排序，最少比较次数为_________。

12. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较____4____次。

13．取增量为3，对记录(46,79,56,38,40,80,35,50,74)进行一趟希尔排序的结果为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

14. 对n个记录进行冒泡排序时，最多比较次数为_______、最少的比较次数为__ n-1__，最少的趟数为____1___。

15．用起泡法对n个关键码排序，在最好情况下，只需做 n-1 次比较和 0 次移动；在最坏的情况下要做_________次比较。

16.两个序列：L1={25,57,48,37,92,86,12,33}、L2={25,37,33,12,48,57,86,92}

用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列____________。 17. 对(46,79,56,38,40,84)进行冒泡排序，第一趟排序后的结果为__(46,56,38,40,79,84)__。

18. 对(46,79,56,64,38,40,84,43)进行冒泡排序，第一趟排序时，元素79将最终下沉到其后第__4__个元素的位置。

19. 快速排序的平均时间复杂性为__O(nlog2n)__，最坏时间复杂性为____O(n2)____。 20．快速排序的平均空间复杂性为__O(log2n)__，最坏空间复杂性为____O(n)____。 21．快速排序每次划分时，是从当前待排序区间的__两端__向__中间__依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。 22. 对(46,79,56,38,40,80)进行快速排序，对应判定树的深度为_____，分支结点数为_____。 23. 对(46,79,56,38,40,80)进行快速排序，共需要____3____趟排序。

24. 对(46,79,56,38,40,80)进行快速排序，含有两个或两个以上元素的排序区间的个数为____4____个。 25. 对(46,79,56,25,76,38,40,80)进行快速排序，第一次划分后，右区间内元素的个数为_____4_____。 26．对(46,79,56,38,40,80)进行快速排序，第一次划分后的结果为__[40 38]46[56 79 80]__。

27．在直接选择排序中，记录比较次数的时间复杂度为__O(n2)__，记录移动次数的时间复杂度为__O(n)__。 28. 对记录(46,79,56,38,40,80,35,50,74)进行直接选择排序，用k表示最小值元素的下标，k初值为1，则在第一趟选择最小值的过程中，k的值被修改__2__次。

29. 在堆排序的过程中，对n个记录建立初始堆需要进行__?n/2?__次筛运算，由初始堆到堆排序结束，需要对树根结点进行__n-1__次筛运算。

30．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为__O(log2n) _____，整个堆排序过程的时间复杂性为__O(nlog2n) __。

31．对n个元素建立初始堆时，最多进行_____次关键字比较。 32．对(46,79,56,38,40,84)进行堆排序，初始小根堆为__(38,40,56,79,46,84)__，大根堆为___________________。 33．对(76,38,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外，以其余元素为根的子树都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为__8__的位置。

34．假定一个堆为(38,40,56,79,46,84)，则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为__(40,46,56,79,84,38)__。

35．在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为__2i__，右孩子元素的下标为__2i+1__。

36．在一个小根堆中，堆顶结点的值是所有结点中的__最小的__，在一个大根堆中，堆顶结点的值是所有结点中的__最大的__。

37.将长度分别为m和n（m>n）的有序表归并成一个有序表，至少进行__n__次键值比较。 38．在二路归并排序中，对n个记录进行归并的趟数为__?log2n?__。

39. 在归并排序中，进行每趟归并的时间复杂性为__O(n) __，整个排序过程的时间复杂性为__O(nlog2n)__，空间复杂性为__O(n)__。

40．对20个记录进行归并排序时，共需要进行__5__趟归并，在第三趟归并时是把长度为__4__的有序表两两归并为长度为__8__的有序表。

41．假定一组记录为(46,79,56,38,40,80,46,75)，对其进行归并排序的过程中，第二趟归并后的第2个子表为__[40 46 75 80]__。

42．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为__3__。

43．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为__[28 46]__。

44．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要__4__趟完成。 45．假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为__[38 46 56 79][40 80]__。

46. 在时间复杂性为O(nlog2n)的所有排序方法中，__归并__排序方法是稳定的。

四、应用题、综合题

1．试给出由5个数据{1，2，3，4，5}组成的一个序列，使得在快速排序的第一趟划分时，移动次数最多。 2．试给出由5个数据{1，2，3，4，5}组成的一个序列，使得用直接选择排序时，移动次数最多。

3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。

4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？ 5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果。 (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]

6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。 (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

7. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。 (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

8. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接选择排序法进行排序时每一趟的排序结果。 (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]

9. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。

构成初始堆（即建堆）的过程：

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]

10. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。 (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]

本文来源：https://www.bwwdw.com/article/uwo2.html