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

admin2019-08-01 66

问题对于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/0NCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

斯大林时期的经济体制最本质的特点是()。

张居正改革期间，调任抗倭名将()镇守蓟门，对安定北方发挥了积极作用。

西汉初年代表黄老政治思想的著作，是陆贾的()。认为“道莫大于无为，行莫大于谨敬”。

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

新文化运动前期的指导思想是()。

两极格局结束后，世界形势发展的总态势的基本特点()

汉建武二十四年(公元48年)匈奴()被南边八部拥立为南单于，他袭用其祖父呼韩邪单于的称号，请求内附，得到东汉的允许。从此以后，匈奴分裂为南北二部。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

出现突触前抑制的关键在于()

赵某强奸案中，赵某的辩护人拿出精神病院对被告赵某所作出的关于赵某患有间歇性精神病的诊断书，来证明赵某在作案时正处于精神病发病期，不应当承担刑事责任。则该诊断书属于下列哪种证据?

下列单位属于资源税的纳税人的是(　　　)。

给出折半查找的递归算法，并给出算法时间复杂度分析。

LarryFreedattributedlowcustomersatisfactiontothefactthatMr.Magee’sattitudetowardsusingvideosinE-commerceseems

I’dbeenlivingwithmywifeforeightyearsandonenight"mom"says,"Iguessyouguysarenevergonnagetmarried．Imean,you

Lookatthestatementsbelowandthearticleabouttheworkplacestressmanagementontheoppositepage.Whichsectionofth

Lackofculture,orratheranexcessofthewrongsortofculture,isoftenconsideredtobesynonymouswithdisadvantage.Most

A、Itisquiteunexpected.B、Shehasalreadygotthenews.C、Shehasconfidenceintheman.D、Itisnotexcitingtolearnabouti

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

计算机408

学硕统考专业

斯大林时期的经济体制最本质的特点是()。

张居正改革期间，调任抗倭名将()镇守蓟门，对安定北方发挥了积极作用。

西汉初年代表黄老政治思想的著作，是陆贾的()。认为“道莫大于无为，行莫大于谨敬”。

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

新文化运动前期的指导思想是()。

两极格局结束后，世界形势发展的总态势的基本特点()

汉建武二十四年(公元48年)匈奴()被南边八部拥立为南单于，他袭用其祖父呼韩邪单于的称号，请求内附，得到东汉的允许。从此以后，匈奴分裂为南北二部。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

出现突触前抑制的关键在于()

赵某强奸案中，赵某的辩护人拿出精神病院对被告赵某所作出的关于赵某患有间歇性精神病的诊断书，来证明赵某在作案时正处于精神病发病期，不应当承担刑事责任。则该诊断书属于下列哪种证据?

下列单位属于资源税的纳税人的是( )。

给出折半查找的递归算法，并给出算法时间复杂度分析。

LarryFreedattributedlowcustomersatisfactiontothefactthatMr.Magee’sattitudetowardsusingvideosinE-commerceseems

I’dbeenlivingwithmywifeforeightyearsandonenight"mom"says,"Iguessyouguysarenevergonnagetmarried．Imean,you

Lookatthestatementsbelowandthearticleabouttheworkplacestressmanagementontheoppositepage.Whichsectionofth

Lackofculture,orratheranexcessofthewrongsortofculture,isoftenconsideredtobesynonymouswithdisadvantage.Most

A、Itisquiteunexpected.B、Shehasalreadygotthenews.C、Shehasconfidenceintheman.D、Itisnotexcitingtolearnabouti

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

下列单位属于资源税的纳税人的是(　　　)。