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

admin2019-08-15 35

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/OMGjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

严复翻译的《天演论》一书的出版时间是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

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

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

通常通信信道的带宽越大，在数据传输中失真将会()。

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

以下关于校验码的叙述中，正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用

上海豫园：是属于()。

人民检察院认为公安机关对应该立案的案件没有立案的，应当要求公安机关

A.CanIspeaktoMr.Johnson,pleaseBI’lltellhimyou’vecalledCI’llgivehimthemessageDWhatcanIdoforyouE.Cany

《中华人民共和国药典》(1995年版)中规定，称取“2.00g”系指（　　）。

建筑体型和立面设计必须符合建筑造型和立面构图的规律,把()有机地结合起来。

“备案号”栏：()。“商品编码”栏：()。

下列关于股票的说法中，不正确的是()。

顿悟说的重要代表人物是()

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

计算机408

学硕统考专业

严复翻译的《天演论》一书的出版时间是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

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

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

通常通信信道的带宽越大，在数据传输中失真将会()。

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

以下关于校验码的叙述中，正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用

上海豫园：是属于()。

人民检察院认为公安机关对应该立案的案件没有立案的，应当要求公安机关

A.CanIspeaktoMr.Johnson,pleaseBI’lltellhimyou’vecalledCI’llgivehimthemessageDWhatcanIdoforyouE.Cany

《中华人民共和国药典》(1995年版)中规定，称取“2.00g”系指（ ）。

建筑体型和立面设计必须符合建筑造型和立面构图的规律,把()有机地结合起来。

“备案号”栏：()。“商品编码”栏：()。

下列关于股票的说法中，不正确的是()。

顿悟说的重要代表人物是()

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

《中华人民共和国药典》(1995年版)中规定，称取“2.00g”系指（　　）。