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

admin2019-08-01 57

问题对一个具有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

学硕统考专业

试述西欧城市兴起的原因、方式及其影响。

1918年美国总统威尔逊提出“十四点原则”，内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

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

计算机系统中存储器为何采用分级结构?

在几种胶结类型中，接触胶结的孔隙度()孔隙胶结。

斯巴达教育的目的是培养()

女性，62岁，乏力、易疲倦，活动后气短3个月，大、小便正常。偏吃素食。查体：面色苍白，皮肤干燥、指甲变平，心肺正常。血象：WBC4.9×109／L，RBC3.5×1012／L，Hb62g／L，PLT390×109／L，铁蛋白3μg／L，诊断为缺铁性贫血，口

患者，男，30岁。腹部砸伤5小时。查体：四肢湿冷，腹肌紧张，全腹压痛，反跳痛，有移动性浊音，肠鸣音消失。该患者目前应进行的处理不包括

(2006年)下列分子中，键角最大的是()。

采用组态方式编写程序的语言称为(　　)。

下列关于贷款的说法，正确的是()。

甲公司的经营杠杆系数为3，财务杠杆系数为2，固定的财务费用为20万元，无优先股。则甲公司的固定生产经营成本为()万元。

下列成语中，没有错别字的一项是()。

RogerRosenblatt’sbookBlackFiction,inattemptingtoapplyliteraryratherthansociopoliticalcriteriatoitssubject,succe

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

计算机408

学硕统考专业

试述西欧城市兴起的原因、方式及其影响。

1918年美国总统威尔逊提出“十四点原则”，内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

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

计算机系统中存储器为何采用分级结构?

在几种胶结类型中，接触胶结的孔隙度()孔隙胶结。

斯巴达教育的目的是培养()

女性，62岁，乏力、易疲倦，活动后气短3个月，大、小便正常。偏吃素食。查体：面色苍白，皮肤干燥、指甲变平，心肺正常。血象：WBC4.9×109／L，RBC3.5×1012／L，Hb62g／L，PLT390×109／L，铁蛋白3μg／L，诊断为缺铁性贫血，口

患者，男，30岁。腹部砸伤5小时。查体：四肢湿冷，腹肌紧张，全腹压痛，反跳痛，有移动性浊音，肠鸣音消失。该患者目前应进行的处理不包括

(2006年)下列分子中，键角最大的是()。

采用组态方式编写程序的语言称为( )。

下列关于贷款的说法，正确的是()。

甲公司的经营杠杆系数为3，财务杠杆系数为2，固定的财务费用为20万元，无优先股。则甲公司的固定生产经营成本为()万元。

下列成语中，没有错别字的一项是()。

RogerRosenblatt’sbookBlackFiction,inattemptingtoapplyliteraryratherthansociopoliticalcriteriatoitssubject,succe

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

采用组态方式编写程序的语言称为(　　)。