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

admin2012-06-26 127

问题对于一个长度为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朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

随机试题

AThirstyWorldTheworldisnotonlyhungry；itisalsothirstyforwater．Thismayseemstrangetoyousincenearly75％oft
患者，男，40岁。6小时前大量饮酒后出现持续性上腹疼痛，阵发性加重，向腰背部放射，弯腰抱膝位可减轻。查体：上腹有压痛，轻度肌紧张。最不可能出现的实验室检杏结果是
马斯洛需要层次论中的最低层需要是（　　）。【2004、2005年考试真题】
某工程在浇筑楼板混凝土时，发生支模架坍塌，造成3人死亡，6人重伤，经调查，系现场技术管理人员未进行技术交底所致。该工程质量事故应判定为()。
首先提供一组描述人的个性或特质的词或句子，然后让其他人通过对被测试者的观察，对被测试者的人格或特质做出评价，这种方法叫做()。
态度的特点包括（）。
在安德森提出的心智技能三阶段中，()阶段的任务是把某一领域的描述性知识转化为程序性知识的过程。
___________，江州司马青衫湿。(白居易《琵琶行》)
两条向远方延伸的平行线看起来趋于接近，这是()。
GIF图像在压缩过程中，像素资料不会丢失，但颜色深度有限，最多只能储存(5)色。

最新回复(0)

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

计算机408

学硕统考专业

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

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()

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

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

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

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

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

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

AThirstyWorldTheworldisnotonlyhungry；itisalsothirstyforwater．Thismayseemstrangetoyousincenearly75％oft

患者，男，40岁。6小时前大量饮酒后出现持续性上腹疼痛，阵发性加重，向腰背部放射，弯腰抱膝位可减轻。查体：上腹有压痛，轻度肌紧张。最不可能出现的实验室检杏结果是

马斯洛需要层次论中的最低层需要是（ ）。【2004、2005年考试真题】

某工程在浇筑楼板混凝土时，发生支模架坍塌，造成3人死亡，6人重伤，经调查，系现场技术管理人员未进行技术交底所致。该工程质量事故应判定为()。

首先提供一组描述人的个性或特质的词或句子，然后让其他人通过对被测试者的观察，对被测试者的人格或特质做出评价，这种方法叫做()。

态度的特点包括（）。

在安德森提出的心智技能三阶段中，()阶段的任务是把某一领域的描述性知识转化为程序性知识的过程。

___________，江州司马青衫湿。(白居易《琵琶行》)

两条向远方延伸的平行线看起来趋于接近，这是()。

GIF图像在压缩过程中，像素资料不会丢失，但颜色深度有限，最多只能储存(5)色。

马斯洛需要层次论中的最低层需要是（　　）。【2004、2005年考试真题】