首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于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
71
问题
对于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
学硕统考专业
相关试题推荐
试述中国古代经济重心南移的过程及原因。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
对阿拉伯半岛的统一起了促进作用的宗教是()。
明初和清初,政府为了发展经济采取的相似措施有()。
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
屋大维的权力达到顶峰是在获得了哪一称号之后?()
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
A.贝壳B.耳后腺及皮肤腺的干燥分泌物C.干燥整体D.除去内脏的干燥体E.病理产物蟾酥的药用部位是()。
学习社会强调四种基本的学习,即__________、学会做事、学会共同生活和学会生存。
下列说法中属于代谢性酸中毒的病因的是
下列各项中,不属于人工日工资单价中特殊情况下支付的工资是()。
某公募基金管理公司基金经理甲的妻子进行证券投资,甲没有向所在公司事先申报,违反了()职业道德要求。[2015年9月真题]
阅读下列材料,根据要求写一篇论说文。我国著名的教育家叶圣陶说:“教育就是培养习惯。”习惯就像是走路,人们如果选择了一条道路,就会沿着这条道路一直走下去。好的习惯是成就孩子美好未来的捷径,能让孩子在不知不觉中健康成长;不好的习惯则像缠在身上的铁链,阻碍着孩
甲某是A电脑公司的销售人员,随身携带盖有该企业公章的空白合同书,便于对外签约。后甲某因收取回扣而被公司除名,但空白合同书未被该公司收回。甲某以此合同书与他人签订了一份电脑买卖合同,该买卖合同的性质应被认定为()。
下列不属于信息存储的条件的是()
Jason(he)wasanidealist(who)refusedtomakeany(compromise)concerningthe(establishment)oftheassociation.
Bysayingthatvillageisnotdead,but"villagelife"isdead,thewritersuggeststhat______.Theexpression"thereisnopoi
最新回复
(
0
)