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

admin2017-11-14 57

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

选项

答案(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[n／2]的子文件，第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，各需2次，共10次即可。 (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。 (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右) 子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n²)。所以当n=7时，最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。提示：此题考查的知识点是快速排序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

《加施泰因协定》

蒙古军西征之后，罗斯处于()的控制之下。

希腊化时代控制希腊半岛的是()。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

下列哪个文件标志着“文化大革命”的发起?()

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

以海地和巴西为例，论述19世纪拉丁美洲民族独立运动类型多样化的历史依据。

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

高调金属音的肠鸣音亢进最常见于()

蛋白质四级结构是指

下列选项中，对脑血管具有较强扩张作用的钙通道阻滞药是

游离皮片移植可按皮肤厚度分为()。

企业通过加强广告宣传、销售促进、变革流通渠道等手段，扩大现有产品在现有市场上的份额，从而提高企业的市场占有率的成长战略是()。

2，3，0，-7，-18，()

开我国公立大学招收女生之先例的大学是

科举制度与传奇创作存在内在的联系是不容否定的，本文试图厘清二者联系的内在逻辑：科举制度造成唐人生活的自主性，进而促成了传奇表现内容的世俗性。(语料来源：《江海学刊》，2009．3)

在资源要素管理中，工具管理是其一项主要管理内容，其中工具的基本运营管理中不包括下面选项中的______。