首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-15
74
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,l 。
解析
转载请注明原文地址:https://kaotiyun.com/show/hKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
下列选择中,()不是操作系统关心的主要问题。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
高度为7的AVL树最少有()个结点。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
随机试题
A.按病变部位以局部取穴配肾俞、太溪B.按病变部位以局部取穴配阴陵泉C.按病变部位以局部取穴配行间、太冲D.按病变部位以局部取穴配大椎、曲池E.按病变部位以局部取穴配膈俞、血海治疗着痹宜
女性患者,21岁。无明确诱因出现新鲜血便。查体:皮肤与黏膜可见成簇的细小的呈鲜红色的毛细血管扩张,肝脾未触及,最可能的诊断是
常用作阴性对比剂的是
投保人、被保险人或者受益人故意造成被保险人死亡的保险事故,骗取保险金的构成故意杀人罪。( )
高水平学生在测验中能得高分,而低水平的学生只能得低分,说明该测验的()质量指标高。
人身权:是与公民人身不能分离的没有财产内容的民事权利。其特征是:①人身权与民事权利主体的人身紧密相连,不能转让,随主体的消亡而自动消失;②人身权没有财产内容;③人身权基于人身关系而产生,具有专有性。根据上述定义,下列权利中哪个不属于人身权?
在文化对一个国家存在和发展的作用问题上,有一种说法:“欲灭—国,先灭其文化”。
设函数f(x)=ln(2+t)dt,则f’(x)的零点个数()
太空垃圾,主要由滞留在太空的废弃卫星和火箭残体(又称空间碎片)构成,还包括天然流星体。它们不仅对地面的人类造成危害,还威胁到在太空中飞行的航天器的安全。有没有办法清除掉太空垃圾呢?经过多年的研究探索,科学家们已经找出了一些清除太空垃圾的方法。
AustraliaisgenerallydividedintothefollowingthreetopographicalregionsEXCEPT
最新回复
(
0
)