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

admin2019-01-16 29

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

选项

答案(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[*91]的子文件，第二遍划分得到4个长度均为[*]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，后=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://jikaoti.com/ti/FufjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述梭伦改革的主要内容和历史意义。

简述格拉古兄弟改革的主要内容和历史意义。

战国时期提出“民为贵，社稷次之，君为轻”的思想家是()。

春秋战国时期，提出“祸兮福之所倚，福兮祸之所伏”的思想家是()。

最早以立法形式巩固大化改新成果的法令是()。

下列各种情况中，应采用异步通信方式的是()。

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。

某网络拓扑如图A-3所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口LO连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202．118．2．1，R2的L0接口的IP地址是202．118．2．2，L1接

患者眩晕，动则加剧，劳则即发，面色咣白，唇甲不华，心悸少寐，神疲懒言，饮食减少，舌质淡，脉细弱。其治法是

以社区为基础的病例一对照研究所选病例的优点是

某企业发行普通股正常市价为58元，估计年增长率为15%，第一年预计发放股利2元，筹资费用率为股票市价的10%，企业所得税率为33%，则发行普通股的资金成本率为(　　)。

建设工程项目施工成本管理涉及的时间范围是()。

内存按其功能，可分为()。

客户在选择保险产品时主要考虑价格和非价格因素。下列选项不属于保险产品的非价格因素的是()。

国家旅游局在全国范围内举行导游资格考试始于()年。

有领导要来单位参观电子设备，半个小时后就到，可是突然停电，而且不知道什么时候会有电，而这件事今天晚上就必须完成，你如何面对?

数据库的数据独立性是指（）。

计算机408

学硕统考专业

简述梭伦改革的主要内容和历史意义。

简述格拉古兄弟改革的主要内容和历史意义。

战国时期提出“民为贵，社稷次之，君为轻”的思想家是()。

春秋战国时期，提出“祸兮福之所倚，福兮祸之所伏”的思想家是()。

最早以立法形式巩固大化改新成果的法令是()。

下列各种情况中，应采用异步通信方式的是()。

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。

某网络拓扑如图A-3所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口LO连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202．118．2．1，R2的L0接口的IP地址是202．118．2．2，L1接

患者眩晕，动则加剧，劳则即发，面色咣白，唇甲不华，心悸少寐，神疲懒言，饮食减少，舌质淡，脉细弱。其治法是

以社区为基础的病例一对照研究所选病例的优点是

某企业发行普通股正常市价为58元，估计年增长率为15%，第一年预计发放股利2元，筹资费用率为股票市价的10%，企业所得税率为33%，则发行普通股的资金成本率为( )。

建设工程项目施工成本管理涉及的时间范围是()。

内存按其功能，可分为()。

客户在选择保险产品时主要考虑价格和非价格因素。下列选项不属于保险产品的非价格因素的是()。

国家旅游局在全国范围内举行导游资格考试始于()年。

有领导要来单位参观电子设备，半个小时后就到，可是突然停电，而且不知道什么时候会有电，而这件事今天晚上就必须完成，你如何面对?

数据库的数据独立性是指（）。

某企业发行普通股正常市价为58元，估计年增长率为15%，第一年预计发放股利2元，筹资费用率为股票市价的10%，企业所得税率为33%，则发行普通股的资金成本率为(　　)。