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

admin2019-08-01 44

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述隋唐科举制的内容和意义。

洪武八年，朱元璋仿照元朝的办法，印造()，命令民间通行，形成了钱、钞并用的货币制度。

论述欧洲一体化的进程及影响。

对于清政府在预备立宪的过程中的做法，表述不正确的是()

论述世界反法西斯联盟形成的过程。

新文化运动前期的指导思想是()。

德国纳粹党消灭资产阶级民主制的关键性事件是()。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

在AOE网络中关键路径叙述正确的是()。

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：

A.钩端螺旋体 B.沙眼衣原体 C.产气荚膜梭菌 D.大肠埃希菌 E.结核分枝杆菌能通过除菌滤器的是

A．HBsAgB．抗-HBsC．HBeAgD．抗-HBeE．抗-HBc

内源性凝血途径和共同途径的筛选试验

集料碱活性检验是测定水泥砂浆试件的长度变化，以鉴定水泥中的碱与活性集料之间的反应所引起的膨胀是否有潜在危害。()

依据我国投资项目资本金制度的相关规定，适用“资本金比例最低为20%”规定的行业主要有()。

设函数y＝y(χ)由χ＋y＝tany确定，求dy．

WhoisMr.Paget?

Iftheprofitsinoneyeararenotsufficienttopaythedividend,the______willbepaidfromtheprofitsoflateryear.

A、Herhometowndoctorworksatthestudenthealthcenter.B、Shecannothelpthemanchooseadoctor.C、Shedidn’tknowsheneeded

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

计算机408

学硕统考专业

简述隋唐科举制的内容和意义。

洪武八年，朱元璋仿照元朝的办法，印造()，命令民间通行，形成了钱、钞并用的货币制度。

论述欧洲一体化的进程及影响。

对于清政府在预备立宪的过程中的做法，表述不正确的是()

论述世界反法西斯联盟形成的过程。

新文化运动前期的指导思想是()。

德国纳粹党消灭资产阶级民主制的关键性事件是()。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

在AOE网络中关键路径叙述正确的是()。

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：

A.钩端螺旋体 B.沙眼衣原体 C.产气荚膜梭菌 D.大肠埃希菌 E.结核分枝杆菌能通过除菌滤器的是

A．HBsAgB．抗-HBsC．HBeAgD．抗-HBeE．抗-HBc

内源性凝血途径和共同途径的筛选试验

集料碱活性检验是测定水泥砂浆试件的长度变化，以鉴定水泥中的碱与活性集料之间的反应所引起的膨胀是否有潜在危害。()

依据我国投资项目资本金制度的相关规定，适用“资本金比例最低为20%”规定的行业主要有()。

设函数y＝y(χ)由χ＋y＝tany确定，求dy．

WhoisMr.Paget?

Iftheprofitsinoneyeararenotsufficienttopaythedividend,the______willbepaidfromtheprofitsoflateryear.

A、Herhometowndoctorworksatthestudenthealthcenter.B、Shecannothelpthemanchooseadoctor.C、Shedidn’tknowsheneeded

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