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

admin2012-06-26 99

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

学硕统考专业

相关试题推荐

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
在某个操作系统中，通过大量的实验，人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns，但若发生了缺页中断就需要1ms。一个程序运行了60s，期
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是()。

随机试题

全面的网络信息安全方案不仅要覆盖到数据流在网络系统中的所有环节，还应当包括信息使用者、传输介质和网络等各方面的管理措施。()
柿蒂的性味是
A．印堂、攒竹、合谷、内庭B．率谷、外关、足临泣C．天柱、后溪、申脉D．四神聪、太冲、内关阳明头痛除选主穴外还可配用
氯霉素引起的骨髓造血功能抑制属于药物的
A．髓海不足B．脾肾两虚C．痰浊蒙窍D．瘀血内阻E．肝肾阴虚
对于承包商来说，风险最大的合同计价形式为(　　)合同。
汇率政策中最基础、最核心的部分是()。
强制性规则又称为命令性规则，在民法中较多。　　　　(　　)
清朝的《理藩院则例》是()
A、March29.B、July14.C、August9.D、September11.B

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

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

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

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

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

全面的网络信息安全方案不仅要覆盖到数据流在网络系统中的所有环节，还应当包括信息使用者、传输介质和网络等各方面的管理措施。()

柿蒂的性味是

A．印堂、攒竹、合谷、内庭B．率谷、外关、足临泣C．天柱、后溪、申脉D．四神聪、太冲、内关阳明头痛除选主穴外还可配用

氯霉素引起的骨髓造血功能抑制属于药物的

A．髓海不足B．脾肾两虚C．痰浊蒙窍D．瘀血内阻E．肝肾阴虚

对于承包商来说，风险最大的合同计价形式为( )合同。

汇率政策中最基础、最核心的部分是()。

强制性规则又称为命令性规则，在民法中较多。 ( )

清朝的《理藩院则例》是()

A、March29.B、July14.C、August9.D、September11.B

对于承包商来说，风险最大的合同计价形式为(　　)合同。

强制性规则又称为命令性规则，在民法中较多。　　　　(　　)