首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-01
37
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1。
解析
转载请注明原文地址:https://kaotiyun.com/show/Y3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
日本文化逐渐摆脱对中国文化的简单模仿,由所谓唐风文化转向具有日本特点的国风文化是在()。
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
提出“天有常道,地有常数”,“制天命而用之”的思想家是()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
设一段正文由字符集{A,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
系统总线中地址线的功能是用于选择()。
并发使得处理机的利用率得到提高,其主要原因是处理机与IO可以同时为多个进程服务,也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加,而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发,调度算法采用
5位二进制定点小数,用补码表示时,最小负数是()。
试比较脱机I/O和联机I/O。
随机试题
驾驶人在实习期内驾驶机动车时,应当在车身后部粘贴或者悬挂统一式样的实习标志。
简述形成理论/概念框架的基本过程。
按照投资对象不同,消费者常用的投资类型有哪些?
吃蚕豆和接触樟脑丸等诱因作用下发生溶血的疾病是
流行病学实验研究在选择研究对象时,下列哪条是错误的
A、花蕾期B、落果期C、霜降期D、7月12日至30日E、全年均可松萝的适宜采收期为
判定风险的级别一般分为()。
甲、乙、丙、丁四人共同投资设立A普通合伙企业。合伙协议的部分内容如下:由甲、乙执行合伙企业事务,丙、丁不得过问企业事务;利润和损失由甲、乙、丙、丁平均分配和分担。在执行合伙企业事务过程中,为提高管理水平,甲自行决定聘请王某担任合伙企业经营管理人员。因合伙企
化学教师所拥有的教育学、心理学方面的知识属于()。
Whattimeisitnow?Whatdotheywanttodo?
最新回复
(
0
)