对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

admin2012-06-26 70

问题对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

选项 A、O(n)
B、O(n²)
C、O(logn)
D、O(nlogn)

答案D

解析在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2^t种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2^t≥n!，即t≥log₂(n!)。因为log₂(n!)≈nlog₂n，所以t≥nlog₂n。

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

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

计算机408

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

随机试题

下面关于列表框和组合框的叙述不正确的是()。
Formanywomenchoosingwhethertoworkornottoworkoutsidetheirhomeisaluxury:theymustworktosurvive.Othersfacea
大肠埃希菌的IMViC试验结果为
沥青动力黏度试验，一次试验的3支黏度计平行试验的误差应不大于平均值的(),否则需重新试验。
　　(一)　　黄河公司原有普通股10000万元、资本成本为10％，长期债券2000万元、资本成本为8．5％。现向银行借款800万元，期限为5年，年利率为5％，分次付息到期一次还本，筹资费用率为零。　　该借款拟用于投资购买价值
王芳与周红是志趣相投的好朋友，王芳对于周红提出来的下列代理要求，可以接受的有()。
把同一排6张座位编号为1，2，3，4，5，6的电影票全部分给4个人，每人至少分1张，至多分2张，且这两张票具有连续的编号，那么不同的分法种数是：
若f(x)=2nx(1-x)n，记Mn=
Germany,Europe’seconomicpowerhouse,doesnotlackcourage:itreboundedfromtwoworldwars,digestedreunificationandhasn
兼职对全日制学生很有用，他们不但能赚到钱，还可以获得职业经验。

最新回复(0)

对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

计算机408

学硕统考专业

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

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

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

下面关于列表框和组合框的叙述不正确的是()。

Formanywomenchoosingwhethertoworkornottoworkoutsidetheirhomeisaluxury:theymustworktosurvive.Othersfacea

大肠埃希菌的IMViC试验结果为

沥青动力黏度试验，一次试验的3支黏度计平行试验的误差应不大于平均值的(),否则需重新试验。

(一) 黄河公司原有普通股10000万元、资本成本为10％，长期债券2000万元、资本成本为8．5％。现向银行借款800万元，期限为5年，年利率为5％，分次付息到期一次还本，筹资费用率为零。 该借款拟用于投资购买价值

王芳与周红是志趣相投的好朋友，王芳对于周红提出来的下列代理要求，可以接受的有()。

把同一排6张座位编号为1，2，3，4，5，6的电影票全部分给4个人，每人至少分1张，至多分2张，且这两张票具有连续的编号，那么不同的分法种数是：

若f(x)=2nx(1-x)n，记Mn=

Germany,Europe’seconomicpowerhouse,doesnotlackcourage:itreboundedfromtwoworldwars,digestedreunificationandhasn

兼职对全日制学生很有用，他们不但能赚到钱，还可以获得职业经验。

　　(一)　　黄河公司原有普通股10000万元、资本成本为10％，长期债券2000万元、资本成本为8．5％。现向银行借款800万元，期限为5年，年利率为5％，分次付息到期一次还本，筹资费用率为零。　　该借款拟用于投资购买价值