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

admin2019-08-01 56

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

我国第一部系统的史学理论著作是（）。

在抗日战争相持阶段，蒋介石的政治态度表现出两面性的最主要原因是()。

提出“天有常道，地有常数”，“制天命而用之”的思想家是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

1931年，英国被迫承认自治领在内政外交上都独立自主的根本原因是()。

真值0在原码、反码和补码机器数形式下()。

IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

简述艺术品的层次结构，并说明其内在关系。

________是商品经济的基本规律。

计算

局限性脂肪肝的表现是

关于利尿药

下列有关法院审理反补贴案件的说法，哪些是错误的?

在缺省方式下，新打开的Excel2003工作簿中含有()张工作表。

根据《基金管理公司特定客户资产管理业务试点办法》的规定，符合条件的基金管理公司只能为单一客户办理特定的资产管理业务，为特定的多个客户办理特定资产管理业务时须经国家相关部门批准。()

Manyprivateinstitutionsofhighereducationaroundthecountryareindanger.Notallwillbesaved,andperhapsnotalldeser

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

计算机408

学硕统考专业

我国第一部系统的史学理论著作是（）。

在抗日战争相持阶段，蒋介石的政治态度表现出两面性的最主要原因是()。

提出“天有常道，地有常数”，“制天命而用之”的思想家是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

1931年，英国被迫承认自治领在内政外交上都独立自主的根本原因是()。

真值0在原码、反码和补码机器数形式下()。

IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

简述艺术品的层次结构，并说明其内在关系。

________是商品经济的基本规律。

计算

局限性脂肪肝的表现是

关于利尿药

下列有关法院审理反补贴案件的说法，哪些是错误的?

在缺省方式下，新打开的Excel2003工作簿中含有()张工作表。

根据《基金管理公司特定客户资产管理业务试点办法》的规定，符合条件的基金管理公司只能为单一客户办理特定的资产管理业务，为特定的多个客户办理特定资产管理业务时须经国家相关部门批准。()

Manyprivateinstitutionsofhighereducationaroundthecountryareindanger.Notallwillbesaved,andperhapsnotalldeser

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