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

admin2012-06-26 75

问题对于一个长度为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

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
高度为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)如果设计字

随机试题

格式化后的软盘产生的四个区中，用于描述文件在磁盘上存放的位置以及整个软盘扇区的使用情况的是
女，41岁，2小时前跌倒后手掌着地，右腕部肿痛。根据右腕关节正侧位片，应诊断为
八会穴中的脉会穴是
对中长期内处于不同职务或工作类型的人员分布情况的规划是(　　)。
下列哪些因素是影响人的全面发展的社会历史条件?()
教师职业最重要的本质特征是()。
新时代要求公务员遵纪守法，依法办事。请结合报考岗位谈谈你的看法。
设向量α1，α2，...，αt是齐次方程组Ax=0的一个基础解系，向量β不是方程组Ax=0的解即Aβ≠0．试证明：向量组β，β+α1，β+α2，…，β+αt线性无关．
Whydoesthemanfeeldumb?
Withinhoursofappearingontelevisiontoannouncetheendofconscription,PresidentJacquesChiracmovedquicklytopreventa

最新回复(0)

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

计算机408

学硕统考专业

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

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

高度为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)如果设计字

格式化后的软盘产生的四个区中，用于描述文件在磁盘上存放的位置以及整个软盘扇区的使用情况的是

女，41岁，2小时前跌倒后手掌着地，右腕部肿痛。根据右腕关节正侧位片，应诊断为

八会穴中的脉会穴是

对中长期内处于不同职务或工作类型的人员分布情况的规划是( )。

下列哪些因素是影响人的全面发展的社会历史条件?()

教师职业最重要的本质特征是()。

新时代要求公务员遵纪守法，依法办事。请结合报考岗位谈谈你的看法。

设向量α1，α2，...，αt是齐次方程组Ax=0的一个基础解系，向量β不是方程组Ax=0的解即Aβ≠0．试证明：向量组β，β+α1，β+α2，…，β+αt线性无关．

Whydoesthemanfeeldumb?

Withinhoursofappearingontelevisiontoannouncetheendofconscription,PresidentJacquesChiracmovedquicklytopreventa

对中长期内处于不同职务或工作类型的人员分布情况的规划是(　　)。