首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
admin
2019-01-16
57
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
(1)当n=7时,在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时,给出一个最好情况的初始排序的实例。
(3)当n=7时,在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时,给出一个最坏情况的初始排序的实例。
选项
答案
(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[*91]的子文件,第二遍划分得到4个长度均为[*]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,后=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/7eRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
论述周公东征的作用与意义。
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
下图是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
随机试题
当病人神志消失,诊断心跳停止的指标是()
患儿虫积日久,腹胀便溏,午后潮热,烦躁不宁,白睛干涩,黑睛糜烂。
w房地产开发公司拟在某市H乡的一处废旧厂房区建设商品房,向社会出售,该废旧厂房及土地属于H乡集体所有。根据土地使用权出让合同约定,w公司获得的这块土地只能建设住宅。W公司在对当地房地产市场形势进行了多次分析研究后,决定调整最初确定的开发方案,减少住宅用地,
建筑外窗有抗风压、气密、水密、保温、隔热及采光六大性能分级指标,在下列四项性能中,哪项数值愈小,其性能愈好?[2006年第011题]
某工程水泥从两个地方供货,甲地供货200t,原价为240元/t;乙地供货300t,原价为250元/t。甲、乙运杂费分别为20元/t、25元/t,运输损耗率均为2%,采购及保管费率均为3%,则该工程水泥的材料基价为()元/t。
市场竞争越激烈,基金费率通常()。
某企业长期持有A股票,目前每股现金股利2元,每股市价20元,在保持目前的经营效率和财务政策不变,且不从外部进行股权融资的情况下,其预计收入增长率为10%,则该股票的股利收益率和期望报酬率分别为()元。
决定项目的质量和成功时,与人员有关的过程主要包括________。
根据所给资料,回答121~125题。2008年上半年,全社会固定资产投资68402亿元,同比增长26.3%。其中,城镇固定资产投资58436亿元,同比增长26.8%;农村固定资产投资9966亿元,同比增长23.2%。在城镇投资中,国
A、Bybus.B、Bybike.C、Bytaxi.D、Onfoot.A
最新回复
(
0
)