排序练习题(答案)

1、WORD格式"排序"练习题一、单项选择题1.假设对 n 个元素进展直接插入排序，在进展第i 趟排序时，假定元素 ri+1的插入位置为 rj，那么需要移动元素的次数为。A. j-iB. i-j-1C. i-jD. i-j+12.在对 n 个元素进展直接插入排序的过程中，共需要进展趟。A. nB. n+1C. n-1D. 2n3.在对 n 个元素进展冒泡排序的过程中，最好情况下的时间复杂度为。A. O(1)B. O(log2n)C. O(n 2)D. O(n)4. 在对 n 个元素进展快速排序的过程中，假设每次划分得到的左、右两个子区间中元素的个数相等专业资料整理WORD格式或

2、只差一个，那么排序的时间复杂度为。专业资料整理WORD格式A. O(1)B. O(nlog2n)C. O(n2)D. O(n)专业资料整理WORD格式5.在对n 个元素进展直接插入排序的过程中，算法的空间复杂度为。专业资料整理WORD格式A. O(1)B. O(log2n)C. O(n2)D. O(nlog2n)专业资料整理WORD格式6. 设一组初始记录关键字序列 (5，2，6， 3， 8)，利用冒泡排序进展升序排序，且排序中从后往前进展比较，那么第一趟冒泡排序的结果为。(A) 2， 5，3， 6， 8(B) 2， 5，6， 3， 8(C) 2， 3，5， 6， 8(D) 2， 3，6， 5

3、， 87. 对以下四个序列进展快速排序，各以第一个元素为基准进展第一次划分，那么在该次划分过程中需要移动元素次数最多的序列为。A. 1,3,5,7,9B. 9,7,5,3,1C. 5,1,3,7,9D. 5,7,9,3,18.在对 n 个元素进展堆排序的过程中，时间复杂度为。A. O(1)B. O(log 2n)C. O(n 2)D. O(nlog2n)9.以下序列不可以构成小跟堆的是。A. 12, 9, 7, 5, 3, 1B. 1, 3, 5, 9, 7, 12C. 1, 5, 3, 7, 9, 12D. 1, 5, 3, 9, 12, 710.设一组初始记录关键字序列(5， 8， 6，

4、3， 2)，以第一个记录关键字 5为基准进展一趟从大到小快速排序的结果为。A. 2， 3，5， 8， 6B.2，3， 5， 6，8C. 3， 2，5， 8， 6D.3，2， 5， 8， 611. 假定对元素序列 7, 3, 5, 9, 1, 12进展堆排序，并且采用小根堆，那么由初始数据构成的初始堆为。A. 1, 3, 5, 7, 9, 12B. 1, 3, 5, 9, 7, 12C. 1, 5, 3, 7, 9, 12D. 1, 5, 3, 9, 12, 712. 假定一个初始堆为 (1, 5, 3, 9, 12, 7, 15, 10) ，那么进展第一趟堆排序后，再重新建堆得到的结果为。A.

5、 3, 5, 7, 9, 12, 10, 15, 1B. 3, 5, 9, 7, 12, 10, 15, 1专业资料整理WORD格式C. 3, 7, 5, 9, 12, 10, 15, 1D. 3, 5, 7, 12, 9, 10, 15, 113.假设对 n 个元素进展归并排序，那么进展归并的趟数为。A. nB. n-1C. n/2D. log 2 n14.假设要从1000 个元素中得到10个最小值元素，最好采用方法。A.直接插入排序B.归并排序C.堆排序D. 快速排序15.假设要对1000 个元素排序，要求既快又稳定，那么最好采用方法。A.直接插入排序B.归并排序C. 堆排序D. 快速排序

6、二、填空题1.对 n 个记录进展冒泡排序时，最少的比较次数为_n-1_ _，最少的趟数为_1_。2. 快速排序在平均情况下的时间复杂度为_O(nlog 2n)_ ，在最坏情况下的时间复杂度为_O(n2)_ _。3. 假定一组记录为(46,79,56,38,40,84)，那么利用堆排序方法建立的初始小根堆为_(38,40,56,79,46,84)_。4. 假定一组记录为(46,79,56,38,40,80)，对其进展快速排序的第一次划分后的结果为_(40,38,46,56,79,80)_。5.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进展归并排序的过程中，

7、供需要_4_趟完成。6.在时间复杂度为O(nlog 2n) 的所有排序方法中，_归并 _排序方法是稳定的。7.设有一无序序列32 ， 45，41， 12，1， 9 ，进展从小到大的希尔排序，且分组增量d=3，那么一趟希尔排序后的序列为 _12,1,9,32,45,41_。三、判断题1希尔排序算法的平均时间复杂度为O(n2) 。 (0 )2堆是完全二叉树，完全二叉树不一定是堆。13在对排序中，假设要进展升序排序，那么需要建立大根堆。14假设给出的待排序序列已有序，那么使用快速排序的进展排序的时间复杂度是O(n) 。 05假设待排序序列已根本有序，那么使用冒泡排序会比快速排序的时间效率会更好。16

8、堆排序是稳定的排序算法。0四、应用题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)，给出采用简单项选择择排序法进展排序时专业资料整理WORD格式-2-专业资料整理WORD格式每一趟的排序结果。5

9、.一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进展排序时每一趟的排序结果。6.一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进展排序时每一趟的排序结果。专业资料整理WORD格式-3-专业资料整理WORD格式四、应用题参考答案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 2

10、6 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 862.(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

11、 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 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) 14 26 27 34 38 46 53 65 74 86(4) 14 26

12、27 34 38 46 53 65 74 864.(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 2

13、7 34 38 46 53 65 86 74专业资料整理WORD格式-4-专业资料整理WORD格式(9) 14 26 27 34 38 46 53 65 74 865. 构成初始堆即建堆的过程：1 2345678910(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 38 14 26 53 86 65 27 34(5) 46 14 38 27 26 53 86 65 74 34(6) 14 26 38 27 34 53 86 6

14、5 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