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

admin2021-08-17 70

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

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

计算机408

学硕统考专业

相关试题推荐

若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是
用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为
在一棵高度为2的5阶B树中，所含关键字的个数最少是
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
数据链路层采用后退N帧方式进行流量和差错控制，发送方已经发送了编号0～7的帧。当计时器超时，只收到了对1、3和5号帧的确认，发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I／O设备读取1000B的数据到主存缓冲区中，该I／O设备一旦启动即按50KB／s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种

随机试题

Womenearnlessthanmendo.Forexample,in1998thehourlywagesofwomenintheU.S.were26%lessthanthoseofmen.Thega
患者头晕目花，少气倦怠，腹部有坠胀感，脱肛，舌淡苔白，脉弱。其证候是
长期趋势法多用于比较法中对可比实例价格进行交易日期修正,而不能用来比较、分析两宗(或两类)以上房地产价格的发展趋势或潜力。()
施工合同示范文本通用条款规定，承包人对(　　)的保修期限为2年。
下列工序中，不属于涂装工艺的是()。
下列不属于担保种类的是()。
每到深秋时节，张老师班上的清洁区总有扫不完的落叶。刚开始很多同学不愿意干活，张老师就带头干。在老师的带动下，班里很多同学都加入了扫树叶的行列，张老师的班级因此经常受到校领导的表扬，同学们也从中体会到了劳动的乐趣。张老师采用的德育方法是(
下列成语中，源于赵匡胤陈桥事变故事的是()。
有一次，苏格拉底淌水过河，脚一划，落水了。他拼命挣扎，大喊救命，不远处有个钓鱼者不但不救他，反而转身就走。最后是他的学生救了他。后来那个钓鱼者淌水过河，也落水了，苏格拉底和他的学生正巧在河边散步，便用竹竿把他救了上来。当学生们知道救上来的就是那个钓鱼者时，
Er______gernSuppevordemHauptgericht.

最新回复(0)

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

计算机408

学硕统考专业

若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是

用户程序发出磁盘I／O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是

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

在一棵高度为2的5阶B树中，所含关键字的个数最少是

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

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

Womenearnlessthanmendo.Forexample,in1998thehourlywagesofwomenintheU.S.were26%lessthanthoseofmen.Thega

患者头晕目花，少气倦怠，腹部有坠胀感，脱肛，舌淡苔白，脉弱。其证候是

长期趋势法多用于比较法中对可比实例价格进行交易日期修正,而不能用来比较、分析两宗(或两类)以上房地产价格的发展趋势或潜力。()

施工合同示范文本通用条款规定，承包人对( )的保修期限为2年。

下列工序中，不属于涂装工艺的是()。

下列不属于担保种类的是()。

下列成语中，源于赵匡胤陈桥事变故事的是()。

Er______gernSuppevordemHauptgericht.

施工合同示范文本通用条款规定，承包人对(　　)的保修期限为2年。