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

admin2019-08-15 77

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

雅尔塔会议和波茨坦会议在内容上的一致之处是()。

系统阐明社会主义初级阶段理论是在()。

“两个凡是”

在集中式总线仲裁中，()方式响应时间最快。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

TCP使用()机制来进行流量控制。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

在学校中，’’班级’’与’’学生’’两个实体集之间的联系属于()关系。

下列哪部作品揭露了封建贵族的罪恶【】

极低出生体重儿是指出生1小时内体重低于_g；超低出生体重儿是指出生1小时内体重低于_g。

获得性免疫缺陷综合征患者主要受损的靶细胞是

设方程x2+y2+z2=4z确定可微函数z=z(x，y)，则全微分dz等于()。[2014年真题]

把收益性支出作为资本性支出，会虚增企业的资产，虚增企业的利润。（　　）

下列属于银团贷款目的的有（）

在常规格式下，在Excel单元格中输入5／20，则单元格中的数据为()。

软件生命周期中所花费用最多的阶段是

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

计算机408

学硕统考专业

雅尔塔会议和波茨坦会议在内容上的一致之处是()。

系统阐明社会主义初级阶段理论是在()。

“两个凡是”

在集中式总线仲裁中，()方式响应时间最快。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

TCP使用()机制来进行流量控制。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

在学校中，’’班级’’与’’学生’’两个实体集之间的联系属于()关系。

下列哪部作品揭露了封建贵族的罪恶【】

极低出生体重儿是指出生1小时内体重低于_________g；超低出生体重儿是指出生1小时内体重低于_________g。

获得性免疫缺陷综合征患者主要受损的靶细胞是

设方程x2+y2+z2=4z确定可微函数z=z(x，y)，则全微分dz等于()。[2014年真题]

把收益性支出作为资本性支出，会虚增企业的资产，虚增企业的利润。（ ）

下列属于银团贷款目的的有（）

在常规格式下，在Excel单元格中输入5／20，则单元格中的数据为()。

软件生命周期中所花费用最多的阶段是

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

极低出生体重儿是指出生1小时内体重低于_g；超低出生体重儿是指出生1小时内体重低于_g。

把收益性支出作为资本性支出，会虚增企业的资产，虚增企业的利润。（　　）