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

admin2019-08-15 67

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

基督教产生的时间是()。

下列选项中，不属于西汉农业发展状况的是()

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

计算机系统采用补码运算是为了()。

UDP的报文头部不包括()。

如下图所示，某园区网用2．5Gbps的POS技术与Internet相连，POS接口的帧格式是SONET。路由协议的选择方案是：园区网内部采用OSPF动态路由协议，园区网与Internet的连接使用静态路由。问题：请阅读以下R3和R4的部分配置信息，并

世界各国对劳动合同的普遍立法通例是()

焊接作业的不安全因素有哪些?

唯心主义否认思维与存在的同一性。

哪本医学著作提出了“止血、消瘀、宁血、补血”的治血四法

不属于固体分散技术的方法是

患者，男性，43岁，3次不同的门诊时间，测得其血压142～150／92～96mmHg。患者预约下次门诊的时间应在()

领海为沿海国家主权管辖下的与其陆地领土、内水以外相邻接的一定范围的海域。根据《联合国海洋法公约》，国家有权确定其海域宽度，我国的领海宽度为：

Everybodyloathesit,buteverybodydoesit.Arecentpollshowedthat40%ofAmericans【C1】______thepractice.InAmericaalone,

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

计算机408

学硕统考专业

基督教产生的时间是()。

下列选项中，不属于西汉农业发展状况的是()

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

计算机系统采用补码运算是为了()。

UDP的报文头部不包括()。

如下图所示，某园区网用2．5Gbps的POS技术与Internet相连，POS接口的帧格式是SONET。路由协议的选择方案是：园区网内部采用OSPF动态路由协议，园区网与Internet的连接使用静态路由。问题：请阅读以下R3和R4的部分配置信息，并

世界各国对劳动合同的普遍立法通例是()

焊接作业的不安全因素有哪些?

唯心主义否认思维与存在的同一性。

哪本医学著作提出了“止血、消瘀、宁血、补血”的治血四法

不属于固体分散技术的方法是

患者，男性，43岁，3次不同的门诊时间，测得其血压142～150／92～96mmHg。患者预约下次门诊的时间应在()

领海为沿海国家主权管辖下的与其陆地领土、内水以外相邻接的一定范围的海域。根据《联合国海洋法公约》，国家有权确定其海域宽度，我国的领海宽度为：

Everybodyloathesit,buteverybodydoesit.Arecentpollshowedthat40%ofAmericans【C1】______thepractice.InAmericaalone,

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