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

admin2021-08-17 30

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

选项 A、O(n)
B、O(n²)
C、O(logD、O(nlogn)

答案D

解析在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2^t种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2^t≥n!，即t≥log₂(n!)。因为log₂(n!)≈nlog₂n，所以t≥nlog2n。

转载请注明原文地址:https://kaotiyun.com/show/HD3i777K

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

计算机408

学硕统考专业

相关试题推荐

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为
已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小是
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
下面的地址中，属于单播地址的是()。
在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*dataⅡ．表中元素个数nⅢ．表的大小maxSizeⅣ．数组基址base
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
数据链路层采用后退N帧方式进行流量和差错控制，发送方已经发送了编号0～7的帧。当计时器超时，只收到了对1、3和5号帧的确认，发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：在(5)的基础上，假设送出的主存地址为04011H，是否命中?

随机试题

①这将使工厂彻底告别车床、冲压机、制模机等传统工具，从而转变为一种以3D打印为基础的成本更低、研发周期更短的生产方式②英国《经济学家》杂志曾刊发题为《第三次工业革命》的文章，称3D打印标志着第三次工业革命的到来③以目前的发展情况判断，3D打印之后，必将
Ipassedthetest.I______itwithoutyourhelp.
甲先于其父死亡。甲父死亡后，甲的女儿继承了甲应继承其父的遗产份额。该继承方式是()。A．转继承B．代位继承C．遗赠D．遗嘱继承
牙釉质牙骨质界正确的是
以下哪些情形属于法院再审时，应裁定将生效判决发回作出生效判决的法院重新审理的?()
任何结果都不可能凭空出现，它们的背后都是有原因的，任何背后有原因的事物都可以被人认识，而可以被人认识的事物都必然不是毫无规律的。根据以上描述，不能得出以下哪项结论?
【F1】Manyobjectsindailyusehaveclearlybeeninfluencedbyscience,buttheirformandfunction,theirdimensionsandappeara
以下函数按每行8个输出数组中的数据：voidfun(int*w，intn){inti；for(i=0；i＜n；i++){________printf("％d"，w[i]
若有定义：floatx=1．5；inta=1，b=3，c=2；则正确的switch语句是()。
WarmerClimateWillBakeTropicalBugsGlobalwarmingcouldcooktropicalinsects,withunpredictableknock-oneffects,say

最新回复(0)

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

计算机408

学硕统考专业

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小是

下面的地址中，属于单播地址的是()。

在顺序表的动态存储定义中需要包含的数据成员是()。Ⅰ．数组指针*dataⅡ．表中元素个数nⅢ．表的大小maxSizeⅣ．数组基址base

数据链路层采用后退N帧方式进行流量和差错控制，发送方已经发送了编号0～7的帧。当计时器超时，只收到了对1、3和5号帧的确认，发送方需要重传的帧的数目是()。

设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：在(5)的基础上，假设送出的主存地址为04011H，是否命中?

Ipassedthetest.I______itwithoutyourhelp.

甲先于其父死亡。甲父死亡后，甲的女儿继承了甲应继承其父的遗产份额。该继承方式是()。A．转继承B．代位继承C．遗赠D．遗嘱继承

牙釉质牙骨质界正确的是

以下哪些情形属于法院再审时，应裁定将生效判决发回作出生效判决的法院重新审理的?()

任何结果都不可能凭空出现，它们的背后都是有原因的，任何背后有原因的事物都可以被人认识，而可以被人认识的事物都必然不是毫无规律的。根据以上描述，不能得出以下哪项结论?

【F1】Manyobjectsindailyusehaveclearlybeeninfluencedbyscience,buttheirformandfunction,theirdimensionsandappeara

以下函数按每行8个输出数组中的数据：voidfun(int*w，intn){inti；for(i=0；i＜n；i++){________printf("％d"，w[i]

若有定义：floatx=1．5；inta=1，b=3，c=2；则正确的switch语句是()。

WarmerClimateWillBakeTropicalBugsGlobalwarmingcouldcooktropicalinsects,withunpredictableknock-oneffects,say