首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-15
67
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,l 。
解析
转载请注明原文地址:https://kaotiyun.com/show/hKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:在甲骨文的研究流域,对甲骨文研究作出了重大贡献,被后人称为“甲骨四堂”的四位学者是(
基督教产生的时间是()。
下列选项中,不属于西汉农业发展状况的是()
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
计算机系统采用补码运算是为了()。
UDP的报文头部不包括()。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
若浮点运算结果尾数不是规格化数,将进行结果规格化。结果规格化有左规和右规之分,下列操作中,属于结果规格化的操作是()。I.尾数左移1位,阶码加1Ⅱ.尾数左移1位,阶码减1Ⅲ.尾数右移1位,阶码加1Ⅳ.尾数右移1位,阶码减1
随机试题
如下图所示,某园区网用2.5Gbps的POS技术与Internet相连,POS接口的帧格式是SONET。路由协议的选择方案是:园区网内部采用OSPF动态路由协议,园区网与Internet的连接使用静态路由。问题:请阅读以下R3和R4的部分配置信息,并
世界各国对劳动合同的普遍立法通例是()
焊接作业的不安全因素有哪些?
唯心主义否认思维与存在的同一性。
哪本医学著作提出了“止血、消瘀、宁血、补血”的治血四法
不属于固体分散技术的方法是
患者,男性,43岁,3次不同的门诊时间,测得其血压142~150/92~96mmHg。患者预约下次门诊的时间应在()
领海为沿海国家主权管辖下的与其陆地领土、内水以外相邻接的一定范围的海域。根据《联合国海洋法公约》,国家有权确定其海域宽度,我国的领海宽度为:
以下是一则广告:本网络文学培训班有着其他同类培训班所没有的特点,除了传授高超的写作技巧、帮助同学打开认识世界的多维视角和宏观视野、丰富学员的文化知识和艺术涵养外,还负责向毕业班学员提供切实有效的就业咨询。去年进行咨询的毕业班学员,100%都找到了
Everybodyloathesit,buteverybodydoesit.Arecentpollshowedthat40%ofAmericans【C1】______thepractice.InAmericaalone,
最新回复
(
0
)