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

admin2019-08-15 41

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

洋务运动时期，首批赴欧海军留学生派出的时间是()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：随着商业的发展，唐朝在货币和金融方面有一些重要的进步，以下表述全面的是()

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

通常通信信道的带宽越大，在数据传输中失真将会()。

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

以画虾著名的现代国画家是（）

若牙石覆盖面积占牙面的1/2，且牙颈部有连续且厚的龈下牙石，则牙石指数为

对抗醛固酮作用的药物是发挥作用最慢的利尿药是

A．呼吸道传播B．虫媒传播C．性接触传播D．消化道传播E．血液传播人乳头瘤病毒的传播方式是经

在计算机中1K字节表示的二进制位数是()。

某单位共有四个科室，第一科室20人，第二科室21人，第三科室25人，第四科室34人，随机抽取一人到外地考察学习，抽到第一科室的概率是多少?()

设A为n阶实矩阵，AT是A的转置矩阵，则对于线性方程组(Ⅰ)：Ax=0和(Ⅱ)：ATAx=0，必有

ThetransformationofjournalisminIndia—theworld’slargestdemocracyandoneofitsfastestgrowingeconomies—hasimplicati

[A]affection[B]aware[C]befriend[D]blindly[E]directly[F]drives[G]dumb[H]dwell[I]enormous[J]murder[K]

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

计算机408

学硕统考专业

洋务运动时期，首批赴欧海军留学生派出的时间是()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：随着商业的发展，唐朝在货币和金融方面有一些重要的进步，以下表述全面的是()

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

通常通信信道的带宽越大，在数据传输中失真将会()。

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

以画虾著名的现代国画家是（）

若牙石覆盖面积占牙面的1/2，且牙颈部有连续且厚的龈下牙石，则牙石指数为

对抗醛固酮作用的药物是发挥作用最慢的利尿药是

A．呼吸道传播B．虫媒传播C．性接触传播D．消化道传播E．血液传播人乳头瘤病毒的传播方式是经

在计算机中1K字节表示的二进制位数是()。

某单位共有四个科室，第一科室20人，第二科室21人，第三科室25人，第四科室34人，随机抽取一人到外地考察学习，抽到第一科室的概率是多少?()

设A为n阶实矩阵，AT是A的转置矩阵，则对于线性方程组(Ⅰ)：Ax=0和(Ⅱ)：ATAx=0，必有

ThetransformationofjournalisminIndia—theworld’slargestdemocracyandoneofitsfastestgrowingeconomies—hasimplicati

[A]affection[B]aware[C]befriend[D]blindly[E]directly[F]drives[G]dumb[H]dwell[I]enormous[J]murder[K]

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