首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-01
38
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1。
解析
转载请注明原文地址:https://kaotiyun.com/show/Y3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于20世纪历史的叙述,全部错误的是()。①朝鲜建国的时间早于中国②1948年3月,英国、法网、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年,周恩来到达莫斯科,中苏缔结了《中苏互不侵犯条约》,标志着社会主义阵
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
论述世界反法西斯联盟形成的过程。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
在集中式总线仲裁中,()方式响应时间最快。
若某浮点机基数为4,尾数采用补码表示,则该浮点机的规格化尾数形式为()。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
在机器数中,正数的符号位用“1”表示的是()。
下列选项中,不属于网络体系结构所描述的内容是____。
随机试题
______herealizeditwastoolatetoreturnhome.
A.螺旋器B.骨半规管C.前庭D.壶腹嵴E.耳蜗属于听觉感受器的是
药物与血浆蛋白结合
甲因走私武器被判处15年有期徒刑,剥夺政治权利5年;因组织他人偷越国境被判处14年有期徒刑,并处没收财产5万元,剥夺政治权利3年;因骗取出口退税被判处10年有期徒刑,并处罚金20万元。关于数罪并罚,下列哪一选项符合《刑法》规定?(2012年卷二12题)
()属于质量保证资料范畴。
某公司承包了一条单跨城市隧道,隧道长度800m,跨度15m,地质条件复杂。设计采用浅埋暗挖法进行施工,其中支护结构由建设单位直接分包给一家专业施工单位。施工准备阶段,某公司项目部建立了现场管理体系,设置了组织机构,确立了项目经理的岗位职责和工作程序;在暗
银行间债券市场的交易制度不包括()。
“业精于勤荒于嬉,行成于思毁于随。”下列选项对这句话的理解不正确的是()。
一、注意事项1.申论考试是对考生阅读理解能力、综合分析能力、提出和解决问题能力以及文字表达能力的测试。2.作答参考时限:阅读资料40分钟,作答110分钟。3.仔细阅读给定的资料,按照后面提出的“作答要求”依次作答。二、给定资料
Intheeyesofvisitorsfromtheoutsideworld______.Familiesinfrontiersettlementsusedtoentertainstrangers______.
最新回复
(
0
)