首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏情况下需进行多少次比较?
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏情况下需进行多少次比较?
admin
2023-02-06
19
问题
对于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/IBwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲本科毕业后,心系祖国边远地区的孩子,于是他到某边远贫困地区从事教育教学工作,地方政府不需要给予甲补贴。()
美国著名教育学心理学家奥苏伯尔指出:“假如让我把全部教育心理学仅仅归纳为一句原理的话,那么我将以一言蔽之:影响学习的唯一重要因素就是学生已经知道了什么。要探明这点,并应据此进行教学。”这说明()。
非正式群体在学校人际关系中起主导作用。()
生产力的发展促进教学内容、教学方法和教学组织形式的变化。()
通常来说,作业有课内和课外两种形式。教师在布置课外作业时要尽量做到“分量适中,难度要大”,以保证学生充分的休息时间和增加学生知识的储备。()
如果将期末考试结果解释为总结性评价,那么对教学过程中实施测验的解释就是()。
在操作技能的形成过程中,在不断的练习期间会出现一个明显的、暂时的停顿期,称为()。
给定资料: 1.2013年7月1日起,修改后的劳动合同法正式施行,其中规定被派遣劳动者享有与用工单位的劳动者同工同酬的权利。为加强操作性,人社部又针对劳务派遣法条进行细化并发布了征求意见稿。然而,现实中比比皆是的同工难同酬的现象让“同工同酬"这块改革的“
通话记录:手机
微生物是地球最早出现的生命形式,这种简单而古老的生命决定了地球演化的方向和进程,推动了土壤的发生和发育,孕育了人类的文明。事实上,土壤中蕴藏的微生物的多样性,被称为地球关键元素循环过程的引擎,是联系大气圈、水圈、岩石圈及生物圈物质与能量交换的重要纽带,维系
随机试题
大黄药材含有的主要化学成分是
患者,男,33岁。近2周来无明显诱因出现双颈部和左腋下无痛性进行性淋巴结肿大,化验血常规无异常,诊断恶性淋巴瘤,为确定疾病分期,下列最有意义的检查是
杨某购买菜刀1把,欲去教训其前女友的现男友黄某。一日畅某至某宾馆用菜刀砍伤了黄某的左颈部,经鉴定,构成轻伤二级。后杨某为阻止黄某报案,乘其不敢反抗之际,将黄某的两部手机拿走,同时,还劫走旧钱包1个。杨某打开钱包后未发现财物,又怕手机有定位,遂将上述手机及钱
投标保证金有效期应当超出投标有效期()。
委托方有()行为,税务师事务所可以在代理期限内单方终止代理行为。
可以用于出质的权利凭证不包括()。
全面推进依法治国的总目标既明确了全面推进依法治国的性质和方向,又突出了全面推进依法治国的工作重点和总抓手,对全面推进依法治国具有纲举目张的意义。全面依法治国的总目标是
【B1】【B9】
Igreatlyappreciate______theopportunitytostudyabroadtwoyearsago.
FormanypeopleintheU.S.,sportsarenotjustforfun.Theyarealmostareligion.Thousandsofsportsfansbuyexpensivetic
最新回复
(
0
)