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

admin2019-08-15 18

问题对一个具有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世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。

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

ICMP在TCP／IP协议集中属于()。

以下叙述不正确的是()。

UDP的报文头部不包括()。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

以下关于校验码的叙述中，正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用

味型分为单一味和________。

链激酶按作用属于

由于设计深度不够等原因，对一般附属、辅助和服务工程等项目，以及住宅和文化福利工程项目或投资比较小、比较简单的工程项目，多采用()。

一艘中国远洋渔业公司的捕捞船，根据有关政府间捕捞协议，在也门共和国所属经济专属区域捕捞墨鱼，在停靠该国亚丁港时，在船上加工成墨鱼片，并在该港通过集装箱发运回我国，该鱼片的原产地应为也门共和国。

(2005年考试真题)企业核算收到短期投资的现金股利时，可能涉及的会计科目有()。

《诗经》中的诗歌，共分为“风”“雅”“颂”三类，其中属于民间歌谣的是()。

祖国大陆与台湾两岸关系和平发展的政治基础是：

设z＝，其中f(u)具有二阶连续导数f(0)＝f′(0)＝0，且求f(u)。

以下关于Linux操作系统的描述中，正确的是______。

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

计算机408

学硕统考专业

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

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

ICMP在TCP／IP协议集中属于()。

以下叙述不正确的是()。

UDP的报文头部不包括()。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

以下关于校验码的叙述中，正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用

味型分为单一味和________。

链激酶按作用属于

由于设计深度不够等原因，对一般附属、辅助和服务工程等项目，以及住宅和文化福利工程项目或投资比较小、比较简单的工程项目，多采用()。

一艘中国远洋渔业公司的捕捞船，根据有关政府间捕捞协议，在也门共和国所属经济专属区域捕捞墨鱼，在停靠该国亚丁港时，在船上加工成墨鱼片，并在该港通过集装箱发运回我国，该鱼片的原产地应为也门共和国。

(2005年考试真题)企业核算收到短期投资的现金股利时，可能涉及的会计科目有()。

《诗经》中的诗歌，共分为“风”“雅”“颂”三类，其中属于民间歌谣的是()。

祖国大陆与台湾两岸关系和平发展的政治基础是：

设z＝，其中f(u)具有二阶连续导数f(0)＝f′(0)＝0，且求f(u)。

以下关于Linux操作系统的描述中，正确的是______。

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