排序练习题(答案).doc

1、排序练习题一、单项选择题1. 若对 n个元素进行直接插入排序，在进行第 i趟排序时，假定元素 ri+1的插入位置为 rj，则需要移动元素的次数为（ ） 。A. j-i B. i-j-1 C. i-j D. i-j+12. 在对 n 个元素进行直接插入排序的过程中，共需要进行（ ）趟。A. n B. n+1 C. n-1 D. 2n3. 在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ） 。A. O(1) B. O(log2n) C. O(n2) D. O(n)4. 在对 n 个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则排序的时间复

2、杂度为（ ） 。A. O(1) B. O(nlog2n) C. O(n2) D. O(n)5. 在对 n 个元素进行直接插入排序的过程中，算法的空间复杂度为（ ） 。A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)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，87. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元

3、素次数最多的序列为（ ） 。A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1C. 5, 1, 3, 7, 9 D. 5, 7, 9, 3, 18. 在对 n 个元素进行堆排序的过程中，时间复杂度为（ ） 。A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)9. 以下序列不可以构成小跟堆的是（ ） 。A. 12, 9, 7, 5, 3, 1 B. 1, 3, 5, 9, 7, 12C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 710. 设一组初始记录关键字序列(5，8，6，3，2) ，以第一个记录关键字 5 为基

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

5、, 10, 15, 1 B. 3, 5, 9, 7, 12, 10, 15, 1-2-C. 3, 7, 5, 9, 12, 10, 15, 1 D. 3, 5, 7, 12, 9, 10, 15, 113. 若对 n 个元素进行归并排序，则进行归并的趟数为（ ） 。A. n B. n-1 C. n/2 D. log2n14. 若要从 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(nlog2n)的所有排序方法中，_归并_排序方法是稳定的。7. 设有一无序序列32，45 ，41，12，1，9 ，进行从小到大的希尔排序，且分组增量 d=3，则一趟希尔排序后的序列为_ 12,1,9,32,45,41 _。三、判断题1 希尔排序算法的平均时间复杂度为 O(n2)。( 0 )2 堆是完全二叉树，完全二叉树不一定是堆。 （ 1 ）3 在对排序中，若要进行升序排序，则需要建立大根堆。 （ 1 ）4 若给出的待排序序列已有序，则使用快速排序的进行排序的时间复杂度是 O(n)。 （ 0 ）5 若待排序序列已基本有序，则使用冒泡排序会比快速排序的时间效

8、率会更好。 （1 ） 6 堆排序是稳定的排序算法。 （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)，给出采用简单选择排序法进行排序时-3-每一趟的排序结

9、果。5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。-4-四、应用题（参考答案）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 3

10、8 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 38 46 53 2

11、7 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 27 34 38 46

12、 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 27 34 38 46

13、53 65 86 74-5-(9) 14 26 27 34 38 46 53 65 74 865. 构成初始堆（即建堆）的过程：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

14、 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 146.(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