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

admin2019-08-15 55

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

学硕统考专业

19世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。

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

文件系统的主要目的是()。

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

马蹄肾属于

关于异位妊娠患者的妇科检查。叙述错误的盆腔体征是

A．辐射散热B．传导散热C．对流散热D．蒸发散热E．以上均正确穿棉衣御寒主要是降低

宽免和费用扣除的内容不包括(　　)。

贷款价格的构成包括()。

微商，一般是指以个人为单位的、利用web3．0时代所衍生的载体渠道，将传统方式与互联网结合，不存在区域限制，且可移动地实现销售渠道新突破的小型个体行为。根据上述定义，以下属于微商的是：

MEXICANMURALART(1)ThefirstmajormodernartmovementinLatinAmericawasMexicanmuralism,whichfeaturedlarge-scale

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

计算机408

学硕统考专业

19世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。

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

文件系统的主要目的是()。

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

马蹄肾属于

关于异位妊娠患者的妇科检查。叙述错误的盆腔体征是

A．辐射散热B．传导散热C．对流散热D．蒸发散热E．以上均正确穿棉衣御寒主要是降低

宽免和费用扣除的内容不包括( )。

贷款价格的构成包括()。

微商，一般是指以个人为单位的、利用web3．0时代所衍生的载体渠道，将传统方式与互联网结合，不存在区域限制，且可移动地实现销售渠道新突破的小型个体行为。根据上述定义，以下属于微商的是：

MEXICANMURALART(1)ThefirstmajormodernartmovementinLatinAmericawasMexicanmuralism,whichfeaturedlarge-scale

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

宽免和费用扣除的内容不包括(　　)。