对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。

admin2019-08-01 36

问题对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：
当n=7时，在最好情况下需进行多少次比较?请说明理由。

选项

答案在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[n／2]的子文件，第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，各需2次，共10次即可。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。

计算机408

学硕统考专业

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

标志着整风运动开始向反“右派”斗争转变的重要文件是()。

中国第一个资产阶级革命团体兴中会建立的时间是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

论述世界反法西斯联盟形成的意义。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

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

操作系统的职能有三个：管理系统硬软件资源、合理地组织计算机工作流程以及()。

说明WindowsNT内核的特点。

政府公共关系的具体工作任务是什么?

衡量中间商绩效的主要标准是()

患者，男性，6岁，开水烫伤，面积达80％，患儿口渴应给予

滤过分数是指()

下列关于板式楼板的说法，正确的是()。

教师职业道德的本质要求是()。

影响问题解决的心理因素有()。

percapitaincome

R1、R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表如下图A所示，当R1收到R2发送的如下图B的[V，D]报文后，R1更新的四个路由表项中距离值从上到下依次为0、4、4、3那么，①②③可能的取值依次为()。

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： 当n=7时，在最好情况下需进行多少次比较?请说明理由。

计算机408

学硕统考专业

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

标志着整风运动开始向反“右派”斗争转变的重要文件是()。

中国第一个资产阶级革命团体兴中会建立的时间是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

论述世界反法西斯联盟形成的意义。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

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

操作系统的职能有三个：管理系统硬软件资源、合理地组织计算机工作流程以及()。

说明WindowsNT内核的特点。

政府公共关系的具体工作任务是什么?

衡量中间商绩效的主要标准是()

患者，男性，6岁，开水烫伤，面积达80％，患儿口渴应给予

滤过分数是指()

下列关于板式楼板的说法，正确的是()。

教师职业道德的本质要求是()。

影响问题解决的心理因素有()。

percapitaincome

R1、R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表如下图A所示，当R1收到R2发送的如下图B的[V，D]报文后，R1更新的四个路由表项中距离值从上到下依次为0、4、4、3那么，①②③可能的取值依次为()。

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。