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

admin2017-11-14 63

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

【朱熹】山西大学2012年中国古代史复试真题；西北大学2013年专门史真题；南开大学2014年日本史真题

【迈镊尼文明】东北师范大学1999年世界上古史真题

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

在“冷战”形成的过程中，影响苏联领导人对美政策变化的关键性事件是()。

分析论述斯大林社会主义工业化。

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

桂林市位于广西东北部、湘桂走廊南端、扼广西北大门，湘桂铁路与漓江纵贯全市，为广西通往北方的交通要道。()

企业为获得与自身生产同类产品的竞争对手的所有权或加强对他们的控制而选择的战略是()

某工程监理单位在实施监理过程中，发现施工单位未按照经审查批准的专项施工方案组织施工，存在严重的安全事故隐患。对此，该监理单位应当(　　)。

()不是影响股票投资价值的外部因素。

城市维护建设税的计税依据包括()。

按利率之间的变动关系，利率可以分为()。

关于教育目的制定的依据，有两种对立的观点，它们是个体本位论和社会本位论，其中个体本位论的代表人物有()。

下列文学常识的表述不正确的一项是()。

中小企业是我国最具活力的企业群体，在GDP中比重约为60％，提供了约70％的城镇就业岗位，但受需求不足、成本上升等不利因素的影响，中小企业的发展遇到较大困难，为此国家加大了对中小企业的扶持力度，这有利于：

Youshouldspendabout40minutesonthistask.Writeaboutthefollowingtopic:Therearemanyadvertisementsdirectedatchild

计算机408

学硕统考专业

【朱熹】山西大学2012年中国古代史复试真题；西北大学2013年专门史真题；南开大学2014年日本史真题

【迈镊尼文明】东北师范大学1999年世界上古史真题

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

在“冷战”形成的过程中，影响苏联领导人对美政策变化的关键性事件是()。

分析论述斯大林社会主义工业化。

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

桂林市位于广西东北部、湘桂走廊南端、扼广西北大门，湘桂铁路与漓江纵贯全市，为广西通往北方的交通要道。()

企业为获得与自身生产同类产品的竞争对手的所有权或加强对他们的控制而选择的战略是()

某工程监理单位在实施监理过程中，发现施工单位未按照经审查批准的专项施工方案组织施工，存在严重的安全事故隐患。对此，该监理单位应当( )。

()不是影响股票投资价值的外部因素。

城市维护建设税的计税依据包括()。

按利率之间的变动关系，利率可以分为()。

关于教育目的制定的依据，有两种对立的观点，它们是个体本位论和社会本位论，其中个体本位论的代表人物有()。

下列文学常识的表述不正确的一项是()。

中小企业是我国最具活力的企业群体，在GDP中比重约为60％，提供了约70％的城镇就业岗位，但受需求不足、成本上升等不利因素的影响，中小企业的发展遇到较大困难，为此国家加大了对中小企业的扶持力度，这有利于：

Youshouldspendabout40minutesonthistask.Writeaboutthefollowingtopic:Therearemanyadvertisementsdirectedatchild

某工程监理单位在实施监理过程中，发现施工单位未按照经审查批准的专项施工方案组织施工，存在严重的安全事故隐患。对此，该监理单位应当(　　)。