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

admin2019-08-01 69

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

选项

答案在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行后=log₂(n+1)遍划分，各文件的长度均为1，此时排序结束。由于n=7，k=3，在最好情况下，第一遍经过6次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为3)进行排序，各需要2次，这样就可将整个文件排序完毕，从而知n=7的最好情况下需进行10次比较。例如：4，7，5，6，3，1，2。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

下列哪一个不是罗马王政时代的管理机构?()

唐朝对外关系呈现出前所未有的盛况，其原因不包括()

太平天国作为几千年来农民运动的高峰，所遇到的历次农民运动中不曾有过的新情况是(

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

下列水泥中不宜用于大体积混凝土工程、化学侵蚀及海水侵蚀工程的有（）。

【2001年第112题】根据砌体结构的空阆工作性能，其静力计算时，可分为刚性方案、弹性方案和刚弹性方案。其划分与下列何组因素有关?

下列有关虚工作的错误说法是()。

判断一家公司是否具有成长性，这家公司的产品或服务有没有市场至关重要。有些公司可能有几年时间保持了较快的增长，但是如果所从事的行业空间有限，就注定了高增长只是。填入画横线部分最恰当的一项是()。

论述两税法实行的主要原因、内容和意义。

初中生人格发展具有的特点有

sight

Argumentation:FunctionsandStrategiesⅠ.Functionsofargumentation:Youcanuseargumentationto1)makeapoint

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

计算机408

学硕统考专业

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

下列哪一个不是罗马王政时代的管理机构?()

唐朝对外关系呈现出前所未有的盛况，其原因不包括()

太平天国作为几千年来农民运动的高峰，所遇到的历次农民运动中不曾有过的新情况是(

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

下列水泥中不宜用于大体积混凝土工程、化学侵蚀及海水侵蚀工程的有（）。

【2001年第112题】根据砌体结构的空阆工作性能，其静力计算时，可分为刚性方案、弹性方案和刚弹性方案。其划分与下列何组因素有关?

下列有关虚工作的错误说法是()。

判断一家公司是否具有成长性，这家公司的产品或服务有没有市场______至关重要。有些公司可能有几年时间保持了较快的增长，但是如果所从事的行业空间有限，就注定了高增长只是______。填入画横线部分最恰当的一项是()。

论述两税法实行的主要原因、内容和意义。

初中生人格发展具有的特点有

sight

Argumentation:FunctionsandStrategiesⅠ.Functionsofargumentation:Youcanuseargumentationto1)makeapoint

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

判断一家公司是否具有成长性，这家公司的产品或服务有没有市场至关重要。有些公司可能有几年时间保持了较快的增长，但是如果所从事的行业空间有限，就注定了高增长只是。填入画横线部分最恰当的一项是()。