首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
admin
2019-08-01
25
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
(1)当n=7时,在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时,给出一个最好情况的初始排序的实例。
(3)当n=7时,在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时,给出一个最坏情况的初始排序的实例。
选项
答案
(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[n/2]的子文件,第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,各需2次,共10次即可. (2)在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7。 (3)在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能得到左(或右) 子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n
2
)。所以当n=7时,最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例:7,6,5,4,3,2,1,要求按递增排序。 提示:此题考查的知识点是快速排序的思想。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
解析
转载请注明原文地址:https://kaotiyun.com/show/9VCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
对1929—1933年的世界经济危机的特点,表述不正确的是()。
斯大林时期的经济体制最本质的特点是()。
对于清政府在预备立宪的过程中的做法,表述不正确的是()
在太平天国时期,对晚清兵制以及政局产生深远影响的是()。
北宋在统一全国的过程中采用了()战略。
据史记《商君传》商鞅变法,“为田开阡陌封疆,而赋税平”其目的
评述马基雅维利的政治思想。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
编写判定给定的二叉树是否是二叉排序树的函数。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
随机试题
男,3个月。出生体重2.8kg,母乳喂养,未添加辅食,食欲好。大便次数每天6~8次,为黄色软便,无特殊臭味,经治无好转,现在体重5.5kg,体格检查无异常。该患儿最可能的诊断是()
()如果抽油机井下泵越深,则理论示功图为整体就越靠近基线。
下列各项,属外科辨别阴证、阳证要点的是()
患者刘先生,因高热行物理降温,物理降温后将所测得的体温绘制在体温单上,下列选项中表述正确的是
下列关于项目融资的说法叙述正确的有()。
甲公司为增值税一般纳税企业,该企业购进固定资产相关的增值税额可以抵扣,适用的增值税税率为17%。甲公司20lO年至2013年与固定资产有关的业务资料如下:(1)2010年11月1日,甲公司以自营方式建造一条生产线。购人工程物资,取得的增值税专用发票上注明
Whatisthebesttitleforthispassage?Accordingtothepassage,recordedhistoryhastaughtus______.
解放生产力和发展生产力的关系是()
设有如下变量声明语句:Dima,bAsBolean则下面叙述中正确的是
Rubbishdumpsthroughouttheindustrialworldarenearlyfull,heraldingacrisisforcityauthoritiesastheylookatalternati
最新回复
(
0
)