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

admin2019-08-15 53

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

学硕统考专业

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

为了顺利开展武装起义的准备工作，在彼得格勒苏维埃中成立了()。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

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

指令字长为12位，每个地址码为3位，采用扩展操作码的方式，设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

下列选项中，描述浮点数操作速度指标的是____。

导致慢性阻塞性肺疾病(C0PD)最重要的危险因素是

(2010年第87题)男性，57岁，胃窦部溃疡直径1．5cm，内科治疗8周无效。应采取的手术方式是

“风性善行而数变”的“善行”，是指风邪致病

A、阿卡波糖B、二甲双胍C、岁格列酮D、西格列汀E、格歹吡嗪属于促胰岛素分泌剂的是

根据中国香港联交所发布的《创业板上市规则》,就所有供公众认购或出售给公众的证券而言(不包括根据配售安排而发行的证券),()必须采纳公平准则,将上述证券分配给所有认购或申请证券的人士。

已知东方公司2008年年初所有者权益总额为1200万元(全部为普通股股东权益)，2008年的资本积累率为60%，本年增发新股20万股，筹集权益资金524万元。2008年年初的权益乘数是2.5，年末资产总额为4224万元，2008年的利息费用180万元，

马拉松全程距离为_______千米。

所谓的及时复习，应该是指()

1/16,2/13,2/5,8/7,(　　)

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

计算机408

学硕统考专业

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

为了顺利开展武装起义的准备工作，在彼得格勒苏维埃中成立了()。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

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

指令字长为12位，每个地址码为3位，采用扩展操作码的方式，设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

下列选项中，描述浮点数操作速度指标的是____。

导致慢性阻塞性肺疾病(C0PD)最重要的危险因素是

(2010年第87题)男性，57岁，胃窦部溃疡直径1．5cm，内科治疗8周无效。应采取的手术方式是

“风性善行而数变”的“善行”，是指风邪致病

A、阿卡波糖B、二甲双胍C、岁格列酮D、西格列汀E、格歹吡嗪属于促胰岛素分泌剂的是

根据中国香港联交所发布的《创业板上市规则》,就所有供公众认购或出售给公众的证券而言(不包括根据配售安排而发行的证券),()必须采纳公平准则,将上述证券分配给所有认购或申请证券的人士。

已知东方公司2008年年初所有者权益总额为1200万元(全部为普通股股东权益)，2008年的资本积累率为60%，本年增发新股20万股，筹集权益资金524万元。2008年年初的权益乘数是2.5，年末资产总额为4224万元，2008年的利息费用180万元，

马拉松全程距离为_______千米。

所谓的及时复习，应该是指()

1/16,2/13,2/5,8/7,( )

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

1/16,2/13,2/5,8/7,(　　)