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

admin2012-06-26 71

问题对于一个长度为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朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
下列叙述正确的个数是()。　1)向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

随机试题

经接触疫水传播的传染病的流行特征
成人排便次数增加且大便为黏液血便，应考虑为
下列有关美国法的历史地位的何种表述是不正确的？
[2008年，第18题]下列函数中不是方程y’’-2y’+y=0的解的函数是()。
我国幼儿园的教学是()。
材料一“空谈误国。实干兴邦”是千百年来人们从历史和实践经验教训中总结出来的治国理政的深刻结论。“实干”从哲学上说可以是“实践”，也可以是“劳动”。人世间的一切幸福都要靠辛苦的劳动来创造，唯有实干方能兴业兴邦，益民、益天下。材料二15世纪末以来，葡萄牙、西
陈某看中某一套住房，应销售方要求先付款3万元，销售方出具“收定金叁万元”的收据。后陈某放弃购买，销售方认为是陈某的原因导致房屋买卖合同不能订立，故已收取的3万元不予退还。对这一纠纷的处理，下列说法正确的是()。
【长子西征】中山大学2016年历史学基础真题；南京大学2017年中国古代史基础真题
FiveCommonMistakesinConversationsandTheirSolutionsI.NotlisteningA.Problem:mostpeople【T1】______【T1】______—waite
PresidentBushandthe9/11Attacks2000ElectionA)AsClinton’spresidencycametoaclose,Democra

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

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

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

经接触疫水传播的传染病的流行特征

成人排便次数增加且大便为黏液血便，应考虑为

下列有关美国法的历史地位的何种表述是不正确的？

[2008年，第18题]下列函数中不是方程y’’-2y’+y=0的解的函数是()。

我国幼儿园的教学是()。

【长子西征】中山大学2016年历史学基础真题；南京大学2017年中国古代史基础真题

FiveCommonMistakesinConversationsandTheirSolutionsI.NotlisteningA.Problem:mostpeople【T1】______【T1】______—waite

PresidentBushandthe9/11Attacks2000ElectionA)AsClinton’spresidencycametoaclose,Democra

FiveCommonMistakesinConversationsandTheirSolutionsI.NotlisteningA.Problem:mostpeople【T1】【T1】—waite