排序练习题(答案).pdf

排序练习题排序练习题一、单项选择题1.若对 n 个元素进行直接插入排序，在进行第i 趟排序时，假定元素 ri+1的插入位置为 rj，则需要移动元素的次数为（）。A.j-iB.i-j-1 C.i-jD.i-j+12.在对 n 个元素进行直接插入排序的过程中，共需要进行（）趟。A.n B.n+1C.n-1 A.O(1)B.O(log2n)C.O(n)或只差一个，则排序的时间复杂度为（）。A.O(1)B.O(nlog2n)C.O(n)222D.2nD.O(n)3.在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。4.在对 n 个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等D.O(n)D.O(nlog2n)5.在对 n 个元素进行直接插入排序的过程中，算法的空间复杂度为（）。A.O(1)B.O(log2n)C.O(n)进行比较，则第一趟冒泡排序的结果为（）。(A)2，5，3，6，8(C)2，3，5，6，8需要移动元素次数最多的序列为（）。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(n)9.以下序列不可以构成小跟堆的是（）。A.12,9,7,5,3,1 C.1,5,3,7,9,12 B.1,3,5,97,12 D.1,5,3,9,12,726.设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，且排序中从后往前(B)2，5，6，3，8(D)2，3，6，5，87.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中D.O(nlog2n)10.设一组初始记录关键字序列(5，8，6，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,12 C.1,5,3,7,9,12（）。A.3,5,7,9,12,10,15,1 B.3,5,9,7,12,10,15,1 B.1,3,5,9,7,12 D.1,5,3,9,12,712.假定一个初始堆为(1,5,3,9,12,7,15,10)，则进行第一趟堆排序后，再重新建堆得到的结果为 C.3,7,5,9,12,10,15,1 D.3,5,7,12,9,10,15,113.若对 n 个元素进行归并排序，则进行归并的趟数为（）。A.nB.n-1C.n/2D.log2n14.若要从 1000 个元素中得到 10 个最小值元素，最好采用（）方法。A.直接插入排序 C.堆排序 A.直接插入排序二、填空题1.对 n 个记录进行冒泡排序时，最少的比较次数为_n-1_，最少的趟数为_1_。2.快速排序在平均情况下的时间复杂度为_O(nlog2n)_，在最坏情况下的时间复杂度为_O(n)_。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)，对其进行归并排序的过程中，供需要_4_趟完成。6.在时间复杂度为 O(nlog2n)的所有排序方法中，_归并_排序方法是稳定的。7.设有一无序序列32，45，41，12，1，9，进行从小到大的希尔排序，且分组增量d=3，则一趟希尔排序后的序列为_ 12,1,9,32,45,41_。三、判断题1 希尔排序算法的平均时间复杂度为O(n)。(0)2 堆是完全二叉树，完全二叉树不一定是堆。（1）3 在对排序中，若要进行升序排序，则需要建立大根堆。（1）4 若给出的待排序序列已有序，则使用快速排序的进行排序的时间复杂度是O(n)。（0）5 若待排序序列已基本有序，则使用冒泡排序会比快速排序的时间效率会更好。（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)，给出采用简单选择排序法进行排序时-2-22B.归并排序D.快速排序C.堆排序D.快速排序15.若要对 1000 个元素排序，要求既快又稳定，则最好采用（）方法。B.归并排序每一趟的排序结果。5.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。6.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。-3-四、应用题（参考答案）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 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 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 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 27 34 38 46 53 65 86 74-4-(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 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-5-