资源描述：
《排序练习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《排序》练习题一、单项选择题1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。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(n2)D.O(n)4.在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则排序的时间复杂度为（）。A.O(1)B.O(nlog2n)C.O(n2)D.
2、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.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。A.1,3,5,7,9B.9,7,5,3,1C.5,1,3,7,9D.5,7,9,3,18.在对n个元素
3、进行堆排序的过程中，时间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)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，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,1
4、2B.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.3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1-5-C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,11.若对n个元素进行归并排序，则进行归并的趟数为（）。A.nB.n-1C.n/2D.élog2nù2.若要从1000个元素中得到10个最小值元素，最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序3.若要对100
5、0个元素排序，要求既快又稳定，则最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序二、填空题1.对n个记录进行冒泡排序时，最少的比较次数为__n-1______，最少的趟数为_1______。2.快速排序在平均情况下的时间复杂度为__O(nlog2n)______，在最坏情况下的时间复杂度为__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
6、,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(n2)。(0)2．堆是完全二叉树，完全二叉树不一定是堆。（1）3．在对排序中，若要进行升序排序，则需要建立大根堆。（1）4．若给出
7、的待排序序列已有序，则使用快速排序的进行排序的时间复杂度是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)，给出采用冒泡排
