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

admin2019-08-15 49

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

选项

答案在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[n／2]的子文件，第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，备需2次，共10次即可。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：金文是指()

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

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

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

下图中有3个进程P0、P1、P2和3个缓冲区B0、B1、B2。进程间借助于相邻缓冲区传递消息，即Pi每次从Bi取一条消息，经加工送入B(i+1)mod3中，B0、B1、B2分别可存放3、2、2个消息，初始时，仅B0有一条消息，利用信号量机制解决P0、P1、

_____、、、_、______此类情况符合追索权的行使。

Thisistheonestudent______Iknowwillpasstheexam.

关于子宫脱垂的术式选择：Ⅱ、Ⅲ度子宫脱垂并发阴道前后壁膨出Ⅱ、Ⅲ度子宫脱垂，年轻、宫颈较长，需保留生育功能者

根据《药品说明书和标签管理规定》，制定药品包装、标签、说明书印制规定的部门是()。

滴虫性阴道炎直接传染的方式是()

我国的基金管理公司已经推出了如定期定额投资计划、红利再投资等在成熟市场较为普遍的服务项目。()

当月委托加工B种烟丝用于连续生产B牌卷烟，准予扣除的已纳消费税额为(　　)。当月准予从销项税额中抵扣的进项税额为(　　)。

上海近代建筑中拜占庭式建筑艺术的一个实例是()。

下列关于我国能源发展现状的叙述不正确的是()。

1000Base-LX标准支持的传输介质是()。

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：金文是指()

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

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

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

下图中有3个进程P0、P1、P2和3个缓冲区B0、B1、B2。进程间借助于相邻缓冲区传递消息，即Pi每次从Bi取一条消息，经加工送入B(i+1)mod3中，B0、B1、B2分别可存放3、2、2个消息，初始时，仅B0有一条消息，利用信号量机制解决P0、P1、

___________、__________、__________、___________、__________此类情况符合追索权的行使。

Thisistheonestudent______Iknowwillpasstheexam.

关于子宫脱垂的术式选择：Ⅱ、Ⅲ度子宫脱垂并发阴道前后壁膨出Ⅱ、Ⅲ度子宫脱垂，年轻、宫颈较长，需保留生育功能者

根据《药品说明书和标签管理规定》，制定药品包装、标签、说明书印制规定的部门是()。

滴虫性阴道炎直接传染的方式是()

我国的基金管理公司已经推出了如定期定额投资计划、红利再投资等在成熟市场较为普遍的服务项目。()

当月委托加工B种烟丝用于连续生产B牌卷烟，准予扣除的已纳消费税额为( )。当月准予从销项税额中抵扣的进项税额为( )。

上海近代建筑中拜占庭式建筑艺术的一个实例是()。

下列关于我国能源发展现状的叙述不正确的是()。

1000Base-LX标准支持的传输介质是()。

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

_____、、、_、______此类情况符合追索权的行使。

当月委托加工B种烟丝用于连续生产B牌卷烟，准予扣除的已纳消费税额为(　　)。当月准予从销项税额中抵扣的进项税额为(　　)。