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

admin2019-08-15 64

问题对于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://www.kaotiyun.com/show/tKCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

元朔二年(前127)，汉武帝采纳()的建议，允许诸侯王推“私恩”，把王国土地的一部分分给子弟为列候，由皇帝制定这些侯国的名号，隶属于汉郡，地位与县相当。

中山舰事件

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

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

以下关于计算机存储器件的叙述，()是不正确的。

引起对氯反应性代谢性碱中毒的常见原因有()

女，45岁。接触性阴道流血3月余。妇科检查：宫颈前唇有直径约2cm菜花状赘生物。镜下见异型细胞浸润性生长，巢状排列，可见病理核分裂象。最可能先转移到的器官是

A．庆大霉素B．苯妥英钠C．维拉帕米D．葡萄糖酸钙E．顺铂

直流设备的充电装置的交流输入宜为三相制，额定频率为50Hz，额定电压为()。

当采用匀速进展横道图比较工作实际进度与计划进度时，如果表示实际进度的横道线右端落在检查日期的右侧，则该端点与检查日期的距离表示工作(　　)。

会计人员违背了会计职业道德，就要受到法律制裁。()

债券投资组合构建中，()的选择则与投资经理对市场利率变化的预期相关。

有一架不等臂天平，两个力臂分别为L1、L2，把物体放在左盘测得m1=90g，放在右盘测得m2=160g，则物体质量实际是()。

对胎儿的基因检测在道德上是错误的。人们无权只因不接受一个潜在生命体的性别，或因其有某种生理缺陷．就将其杀死。如果以下陈述为真，哪一项对上文中的论断提供了最强的支持?

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

计算机408

学硕统考专业

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

元朔二年(前127)，汉武帝采纳()的建议，允许诸侯王推“私恩”，把王国土地的一部分分给子弟为列候，由皇帝制定这些侯国的名号，隶属于汉郡，地位与县相当。

中山舰事件

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

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

以下关于计算机存储器件的叙述，()是不正确的。

引起对氯反应性代谢性碱中毒的常见原因有()

女，45岁。接触性阴道流血3月余。妇科检查：宫颈前唇有直径约2cm菜花状赘生物。镜下见异型细胞浸润性生长，巢状排列，可见病理核分裂象。最可能先转移到的器官是

A．庆大霉素B．苯妥英钠C．维拉帕米D．葡萄糖酸钙E．顺铂

直流设备的充电装置的交流输入宜为三相制，额定频率为50Hz，额定电压为()。

当采用匀速进展横道图比较工作实际进度与计划进度时，如果表示实际进度的横道线右端落在检查日期的右侧，则该端点与检查日期的距离表示工作( )。

会计人员违背了会计职业道德，就要受到法律制裁。()

债券投资组合构建中，()的选择则与投资经理对市场利率变化的预期相关。

有一架不等臂天平，两个力臂分别为L1、L2，把物体放在左盘测得m1=90g，放在右盘测得m2=160g，则物体质量实际是()。

对胎儿的基因检测在道德上是错误的。人们无权只因不接受一个潜在生命体的性别，或因其有某种生理缺陷．就将其杀死。如果以下陈述为真，哪一项对上文中的论断提供了最强的支持?

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

当采用匀速进展横道图比较工作实际进度与计划进度时，如果表示实际进度的横道线右端落在检查日期的右侧，则该端点与检查日期的距离表示工作(　　)。