首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
admin
2017-11-14
31
问题
对于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/H3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二战后主要资本主义国家经济恢复和发展的杠杆是()①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
1934年9月苏联加入国联,对此说法错误的一项是()。
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
晚清时期清帝年号的正确排序是
周王室的两大官僚系统是()。
唐朝时期,每丁服徭役二十天,是为正役,国家若不需要其服役,则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准,交足二十天的数额以代役,称为()。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
假设某系统总线在一个总线周期中并行传输4B信息,一个总线周期占用2个时钟周期,总线时钟频率为10MHz,则总线带宽是____。
随机试题
乙市某建筑公司招收了一批农村合同工人,双方签订的劳动合同中约定,工资为每个月280元人民币,由公司提供食宿。后来,工人们得知该市最低工资标准为320元,企业支付工资一律不得低于该标准。于是,工人们向公司要求将工资涨到每月每人320元。但公司认为,公司除向工
简述荀子的教师论。
我国现阶段,不同国有企业的职工,付出同样的劳动,获得的劳动报酬却会有所差别,这是因为()
简答我国社会主义法治理念的主要内容,并阐释社会主义法治的核心内容的基本内涵。答题要求1.观点明确,表述完整、准确。2.不少于400字。
首次明确依法继承的宅基地使用权合法地位的法律文件是()。
建设项目对区域市场竞争结构的影响,重点从()进行分析。
实施建筑工程监理前,建设单位应当将(),书面通知被监理的建筑施工企业。
文艺复兴运动的发源地及中心是()。
RAM的特点是()。
Fromthehealthpointofviewwearelivinginamarvelousage.Weareimmunizedfrombirthagainstmanyofthemostdangerousd
最新回复
(
0
)