对一个具有7个记录的文件进行快速排序，请问：在最坏情况下需进行多少次比较?为什么?请给出相应实例。

admin2019-08-15 68

问题对一个具有7个记录的文件进行快速排序，请问：
在最坏情况下需进行多少次比较?为什么?请给出相应实例。

选项

答案在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n²)，反而不快了。对于n=7的记录文件，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，l 。

解析

转载请注明原文地址:https://kaotiyun.com/show/hKCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对一个具有7个记录的文件进行快速排序，请问：在最坏情况下需进行多少次比较?为什么?请给出相应实例。

计算机408

学硕统考专业

马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：对于二里头文化的发现的意义，下列选项表述最准确的是()

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

快速排序最易发挥其长处的情况是()。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

以下方法中，不能确定目前存在幽门螺杆菌感染的是

《莫利尔法案》是指1857年美国国会议员贾斯丁．莫利尔提出的一项通过赠地建立研究型大学的建议。()

急性胰腺炎的临床表现中，下列哪项是错误的

32岁妇女，因经期腹痛并逐渐加剧前来就诊。检查子宫后倾，粘连固定，子宫峡部后壁可触及多个小结节，触痛明显，右附件区增厚，在附件区触及直径约6cm的囊性粘连包块。最可能的诊断是

关于起诉与受理的表述，下列哪些选项是正确的?(2012年试卷三第79题)

法国学者费奈隆认为：“民众支配雅典，演说支配民众。”这句话表明他对古代雅典民主政治的看法是()。

简述学校德育的主要内容。

假设你用保证金从你的经纪人处以每股70美元购买了200股XYZ股票。如果初始保证金是55%，你从你的经纪人处借了多少钱?()

Today,mostcountriesintheworldhavecanals.Manycountrieshavebuiltcanalsnearthecoast,andparallel【C1】______thecoast

对一个具有7个记录的文件进行快速排序，请问： 在最坏情况下需进行多少次比较?为什么?请给出相应实例。

计算机408

学硕统考专业

马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：对于二里头文化的发现的意义，下列选项表述最准确的是()

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

快速排序最易发挥其长处的情况是()。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

以下方法中，不能确定目前存在幽门螺杆菌感染的是

《莫利尔法案》是指1857年美国国会议员贾斯丁．莫利尔提出的一项通过赠地建立研究型大学的建议。()

急性胰腺炎的临床表现中，下列哪项是错误的

32岁妇女，因经期腹痛并逐渐加剧前来就诊。检查子宫后倾，粘连固定，子宫峡部后壁可触及多个小结节，触痛明显，右附件区增厚，在附件区触及直径约6cm的囊性粘连包块。最可能的诊断是

关于起诉与受理的表述，下列哪些选项是正确的?(2012年试卷三第79题)

法国学者费奈隆认为：“民众支配雅典，演说支配民众。”这句话表明他对古代雅典民主政治的看法是()。

简述学校德育的主要内容。

假设你用保证金从你的经纪人处以每股70美元购买了200股XYZ股票。如果初始保证金是55%，你从你的经纪人处借了多少钱?()

Today,mostcountriesintheworldhavecanals.Manycountrieshavebuiltcanalsnearthecoast,andparallel【C1】______thecoast

对一个具有7个记录的文件进行快速排序，请问：在最坏情况下需进行多少次比较?为什么?请给出相应实例。