首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-15
71
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,l 。
解析
转载请注明原文地址:https://kaotiyun.com/show/hKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赵匡胤了解高级将领发动兵变夺取政权的危险,他注意分散军权。回答问题:建隆二年,赵匡胤采取了()的措施,收夺武将的兵权
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:对于二里头文化的发现的意义,下列选项表述最准确的是()
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
真值0在原码、反码和补码机器数形式下()。
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
随机试题
习近平总书记指出:“马克思主义哲学深刻揭示了客观世界特别是人类社会发展的一般规律,在当今时代依然有着强大生命力,依然是指导我们共产党人前进的强大思想武器。”实现“两个一百年”奋斗目标、实现中华民族伟大复兴的中国梦,必须不断接受马克思主义哲学智慧的滋养,更加
某患者,45岁,右耳垂下肿物5年,生长缓慢,无痛。检查肿物以耳垂为中心,界限清楚,活动,呈椭圆形,表现呈结节状,硬度中等。最可能的临床诊断是右侧腮腺()
男,42岁。3天来右上后磨牙痛重,冷热加剧,夜间痛而来就诊。近1年多来,右上磨牙进食时咬到某特定位置时出现撕裂样痛,冷热敏感,平时咬物不适。检查:16咬合面似有近远中方向越过边缘嵴的细裂纹,颊尖高陡,无龋洞,不松动,叩痛(+)。最可能的诊断是
系统误差来源于( )。
A、氟马西尼B、亚甲蓝C、维生素K1D、阿托品E、氯磷定用于有机磷中毒的解毒剂是
比较常见的掉期是()
下列关于储蓄国债(电子式)的发行方式的说法中,正确的是()。
医务社会工作是医疗卫生服务系统的有机组成部分。下列社会工作服务中,不属于医务社会工作内容的是()。
小刚今年十五岁,父母外出打工,由年迈的爷爷照看。小刚为了能够在网吧打游戏,偷走了邻居老大爷的手机,价值500元。案发后,小刚被带到派出所。关于此案,下列说法错误的是()。
YouaregoingtoreadamagazinearticleaboutamanwhoteacheschildrenhowtoimprovetheirmemoryChoosethemostsuitableh
最新回复
(
0
)