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

admin2019-08-15 50

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

一战后，英国拒绝加入法国的安全保障体系，其原因是()。

波士顿倾茶事件

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

操作系统采用页式存储管理方法，要求()。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中，且x=一8．25，则FRl的内容是____。

基金公司募集基金前，须在公司网站上公告的文件不包括()。

以舞台演出为存在形式，以演员的动作和对话为主要表现手段，为观众当场表演故事的艺术样式叫作()。

A、藿香正气散B、痛泻要方C、保和丸D、参苓白术散E、四神丸食滞肠胃泄泻宜用

符合汽车库、修车库防火分隔要求的有()。

专利权、商标权等不具有实物形态，因此不属于资产。()

下面属于海运单的特征的是（）。

班主任工作是从()开始的。

TCP/IP参考模型中，互联层与OSI参考模型中的哪一(或哪些)层相对应?______。

下图是校园网某台主机在命令行模式执行某个命令时用sniffer捕获的数据包。根据图中信息回答下列问题。IP地址为202．113．77．253的设备应具备的功能是[20]。

AbrahamLincolnturns200thisyear,andhe’sbeginningtoshowhisage.Whenhisbirthdayarrives,onFebruary12,Congresswil

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

一战后，英国拒绝加入法国的安全保障体系，其原因是()。

波士顿倾茶事件

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

操作系统采用页式存储管理方法，要求()。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中，且x=一8．25，则FRl的内容是____。

基金公司募集基金前，须在公司网站上公告的文件不包括()。

以舞台演出为存在形式，以演员的动作和对话为主要表现手段，为观众当场表演故事的艺术样式叫作()。

A、藿香正气散B、痛泻要方C、保和丸D、参苓白术散E、四神丸食滞肠胃泄泻宜用

符合汽车库、修车库防火分隔要求的有()。

专利权、商标权等不具有实物形态，因此不属于资产。()

下面属于海运单的特征的是（）。

班主任工作是从()开始的。

TCP/IP参考模型中，互联层与OSI参考模型中的哪一(或哪些)层相对应?______。

下图是校园网某台主机在命令行模式执行某个命令时用sniffer捕获的数据包。根据图中信息回答下列问题。IP地址为202．113．77．253的设备应具备的功能是[20]。

AbrahamLincolnturns200thisyear,andhe’sbeginningtoshowhisage.Whenhisbirthdayarrives,onFebruary12,Congresswil

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