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

admin2012-06-26 115

问题对于一个长度为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://www.kaotiyun.com/show/qfxi777K

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

计算机408

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是()。

随机试题

A．主动脉型心B．二尖瓣型心C．双侧心界扩大D．心绝对浊音界扩大E．心底浊音区扩大主动脉瓣关闭不全
A．羌活胜湿汤B．葛根汤C．瓜蒌桂枝汤D．羚角钩藤汤E．大定风珠治疗痉证肝经热盛证，应首选()
根据所给资料，采用先进先出法登记A材料明细账。企业2006年12月l日结存A材料200公斤，每公斤实际成本12元。12月5日购入400公斤，每公斤实际成本13元；12月7日生产领用300公斤；12月16Et购入200公斤，每公斤实际成本14元
A药厂涉嫌生产假药，甲食品药品质量监督管理局对其展开调查，调查证明情况属实，拟作出吊销营业执照，罚款5000元的行政处罚，随后向A药厂送达了吊销营业执照、罚款5000元的行政处罚告知书，并告知当事人有要求听证的权利，送达当日A药厂要求听证。关于本案下列说法
贷款承诺费是指银行对()的那部分资金收取的费用。
下列不属于学校心理健康教育中常用途径的是()。
某企业在编制预算时规定，在产品销量为1000件时，预算的单位成本为2.80元；当销量达到1500件时，则以单位成本2.65元作为控制标准。此种做法是()。
y=3x-1
British_____isoneofthefourmajornewsagenciesinthewest.
A、Tostudythedailyscheduleofthesongbirds.B、Todiscovertherelationshipbetweencourtshipandfootwork.C、Toresearchhow

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

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

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

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

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

A．主动脉型心B．二尖瓣型心C．双侧心界扩大D．心绝对浊音界扩大E．心底浊音区扩大主动脉瓣关闭不全

A．羌活胜湿汤B．葛根汤C．瓜蒌桂枝汤D．羚角钩藤汤E．大定风珠治疗痉证肝经热盛证，应首选()

根据所给资料，采用先进先出法登记A材料明细账。企业2006年12月l日结存A材料200公斤，每公斤实际成本12元。12月5日购入400公斤，每公斤实际成本13元；12月7日生产领用300公斤；12月16Et购入200公斤，每公斤实际成本14元

贷款承诺费是指银行对()的那部分资金收取的费用。

下列不属于学校心理健康教育中常用途径的是()。

某企业在编制预算时规定，在产品销量为1000件时，预算的单位成本为2.80元；当销量达到1500件时，则以单位成本2.65元作为控制标准。此种做法是()。

y=3x-1

British_____isoneofthefourmajornewsagenciesinthewest.

A、Tostudythedailyscheduleofthesongbirds.B、Todiscovertherelationshipbetweencourtshipandfootwork.C、Toresearchhow