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

admin2019-08-15 71

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：建隆二年，赵匡胤采取了()的措施，收夺武将的兵权

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

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

真值0在原码、反码和补码机器数形式下()。

有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

某患者，45岁，右耳垂下肿物5年，生长缓慢，无痛。检查肿物以耳垂为中心，界限清楚，活动，呈椭圆形，表现呈结节状，硬度中等。最可能的临床诊断是右侧腮腺()

系统误差来源于（　　）。

A、氟马西尼B、亚甲蓝C、维生素K1D、阿托品E、氯磷定用于有机磷中毒的解毒剂是

比较常见的掉期是()

下列关于储蓄国债(电子式)的发行方式的说法中，正确的是()。

医务社会工作是医疗卫生服务系统的有机组成部分。下列社会工作服务中，不属于医务社会工作内容的是()。

小刚今年十五岁，父母外出打工，由年迈的爷爷照看。小刚为了能够在网吧打游戏，偷走了邻居老大爷的手机，价值500元。案发后，小刚被带到派出所。关于此案，下列说法错误的是()。

YouaregoingtoreadamagazinearticleaboutamanwhoteacheschildrenhowtoimprovetheirmemoryChoosethemostsuitableh

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

计算机408

学硕统考专业

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：建隆二年，赵匡胤采取了()的措施，收夺武将的兵权

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

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

真值0在原码、反码和补码机器数形式下()。

有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

某患者，45岁，右耳垂下肿物5年，生长缓慢，无痛。检查肿物以耳垂为中心，界限清楚，活动，呈椭圆形，表现呈结节状，硬度中等。最可能的临床诊断是右侧腮腺()

系统误差来源于（ ）。

A、氟马西尼B、亚甲蓝C、维生素K1D、阿托品E、氯磷定用于有机磷中毒的解毒剂是

比较常见的掉期是()

下列关于储蓄国债(电子式)的发行方式的说法中，正确的是()。

医务社会工作是医疗卫生服务系统的有机组成部分。下列社会工作服务中，不属于医务社会工作内容的是()。

小刚今年十五岁，父母外出打工，由年迈的爷爷照看。小刚为了能够在网吧打游戏，偷走了邻居老大爷的手机，价值500元。案发后，小刚被带到派出所。关于此案，下列说法错误的是()。

YouaregoingtoreadamagazinearticleaboutamanwhoteacheschildrenhowtoimprovetheirmemoryChoosethemostsuitableh

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

系统误差来源于（　　）。