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

admin2019-08-15 75

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

中共八届九中全会提出的恢复和调整国民经济的方针是()。

宗教问题已成为某些国家和地区之间冲突的主要原因。信仰“真主”安拉，以《古兰经》为经典的宗教是()

在操作系统中，P，V操作是一种()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

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

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

我国法律明确禁止的健康歧视，除了残疾歧视，还包括()

Ihopetomeetyouagain______nextyear.

脂肪酸β-氧化在细胞内进行的部位有

肺活量检测与下列因素不相关的是

牙本质和牙骨质来源于

桑代克曾做过一项实验：被试者被蒙上眼睛后练习画4英寸长的线段，经过3000多次练习，毫无进步。对该实验的结果最适当的解释是()。

年龄越小，()。

在指导学生面试时，教师非常重视训练学生进入面试考场时的仪态、仪表、眼神、与面试官打招呼等细节，以期给面试官留下好印象，这是充分利用了()。

试比较实际均衡利率理论、凯恩斯利率理论、可贷资金理论的联系与区别。

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

计算机408

学硕统考专业

中共八届九中全会提出的恢复和调整国民经济的方针是()。

宗教问题已成为某些国家和地区之间冲突的主要原因。信仰“真主”安拉，以《古兰经》为经典的宗教是()

在操作系统中，P，V操作是一种()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

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

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

我国法律明确禁止的健康歧视，除了残疾歧视，还包括()

Ihopetomeetyouagain______nextyear.

脂肪酸β-氧化在细胞内进行的部位有

肺活量检测与下列因素不相关的是

牙本质和牙骨质来源于

桑代克曾做过一项实验：被试者被蒙上眼睛后练习画4英寸长的线段，经过3000多次练习，毫无进步。对该实验的结果最适当的解释是()。

年龄越小，()。

在指导学生面试时，教师非常重视训练学生进入面试考场时的仪态、仪表、眼神、与面试官打招呼等细节，以期给面试官留下好印象，这是充分利用了()。

试比较实际均衡利率理论、凯恩斯利率理论、可贷资金理论的联系与区别。

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