排序练习题答案

排序练习题答案

ID:22627621

大小:63.51 KB

页数:5页

时间:2018-10-30

排序练习题答案_第1页
排序练习题答案_第2页
排序练习题答案_第3页
排序练习题答案_第4页
排序练习题答案_第5页
资源描述:

《排序练习题答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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),给出采用冒泡排

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。