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

admin2019-08-15 55

问题对于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

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

重庆谈判签署的文件是()。

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

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

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

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

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

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

分泌HCO3-的是

患儿女，13个月。生后3个月起青紫逐渐加重，活动后气急，查体:生长发育明显落后，青紫明显，伴杵状指，胸骨左缘3～4肋间闻及Ⅲ级收缩期杂音。对该患儿的治疗最终应采取

小蓟饮子的功用是五苓散的功用是

A．乌头B．麻黄C．山药D．桂枝E．西红花因外观性状相似不适宜与天花粉装于一斗或上下斗的中药是()。

采用修约值比较法，应将测定值或计算值进行修约，修约数位与规定的极限数值数位一致。()

开放式基金公开说明书的报告截止日为()。

Supposeyouaregoingtoresignfromyourcompanyforpersonalreasons.Writealetterofresignationtoyourmanagerto1)

下列关于数据库性能优化的说法，错误的是()。

AftertheArabconquestofEgyptinA.D640,ArabicbecamethedominantlanguageoftheEgyptians,replacingolderlanguagesand

Historianswishtheycouldwitnesstherealscenesofhistoriceventsbecausetherearesomanymysteriesaboutthem.Theteam

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

计算机408

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

重庆谈判签署的文件是()。

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

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

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

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

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

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

分泌HCO3-的是

患儿女，13个月。生后3个月起青紫逐渐加重，活动后气急，查体:生长发育明显落后，青紫明显，伴杵状指，胸骨左缘3～4肋间闻及Ⅲ级收缩期杂音。对该患儿的治疗最终应采取

小蓟饮子的功用是五苓散的功用是

A．乌头B．麻黄C．山药D．桂枝E．西红花因外观性状相似不适宜与天花粉装于一斗或上下斗的中药是()。

采用修约值比较法，应将测定值或计算值进行修约，修约数位与规定的极限数值数位一致。()

开放式基金公开说明书的报告截止日为()。

Supposeyouaregoingtoresignfromyourcompanyforpersonalreasons.Writealetterofresignationtoyourmanagerto1)

下列关于数据库性能优化的说法，错误的是()。

AftertheArabconquestofEgyptinA.D640,ArabicbecamethedominantlanguageoftheEgyptians,replacingolderlanguagesand

Historianswishtheycouldwitnesstherealscenesofhistoriceventsbecausetherearesomanymysteriesaboutthem.Theteam

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