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

admin2012-06-26 68

问题对于一个长度为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://jikaoti.com/ti/4hajFFFM

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

计算机408

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

随机试题

关于申诉书，错误的是
对痤疮瘢痕治疗无效的是
A．制造蓄电池B．制造仪表C．喷漆D．制造电池E．制造火柴
下列确定垂直距离的方法中最准确的是
脑膜刺激征见于脑膜炎、蛛网膜下腔出血等。()
根据我国《合伙企业法》，下列对合伙企业“入伙、退伙”事项的表述，错误的是(　　)。
取得试点经营出境旅游业务资格的中外合资经营旅行社(以下简称试点旅行社)，应当自换领《旅行社业务经营许可证》之日起3个工作日内，增存质量保证金()人民币，并向国务院旅游行政主管部门提交相关证明文件。
()承担政府在社区的相关公共服务，协助社区居民委员会做好社区公共事务和公益性工作。
内部关系，是指公安机关内部上下级之间、同级与同级之间、警种与警种之间，按照()构成的关系。
在上个打猎季节，在人行道上行走时被汽车撞伤的人数是在树林中的打猎事故中受伤的人数的2倍。因此，在上个打猎季节，人们在树林里行走比在人行道上行走安全。为了评价上述论证，以下哪项是必须知道的?()。

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

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

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

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

关于申诉书，错误的是

对痤疮瘢痕治疗无效的是

A．制造蓄电池B．制造仪表C．喷漆D．制造电池E．制造火柴

下列确定垂直距离的方法中最准确的是

脑膜刺激征见于脑膜炎、蛛网膜下腔出血等。()

根据我国《合伙企业法》，下列对合伙企业“入伙、退伙”事项的表述，错误的是( )。

取得试点经营出境旅游业务资格的中外合资经营旅行社(以下简称试点旅行社)，应当自换领《旅行社业务经营许可证》之日起3个工作日内，增存质量保证金()人民币，并向国务院旅游行政主管部门提交相关证明文件。

()承担政府在社区的相关公共服务，协助社区居民委员会做好社区公共事务和公益性工作。

内部关系，是指公安机关内部上下级之间、同级与同级之间、警种与警种之间，按照()构成的关系。

在上个打猎季节，在人行道上行走时被汽车撞伤的人数是在树林中的打猎事故中受伤的人数的2倍。因此，在上个打猎季节，人们在树林里行走比在人行道上行走安全。为了评价上述论证，以下哪项是必须知道的?()。

根据我国《合伙企业法》，下列对合伙企业“入伙、退伙”事项的表述，错误的是(　　)。