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

admin2021-08-17 71

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

学硕统考专业

相关试题推荐

下列关于中断I／O方式和DMA方式比较的叙述中，错误的是
用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
输入一整数数组{5，7，6，9，11，10，8}，该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两
数据链路层采用后退N帧方式进行流量和差错控制，发送方已经发送了编号0～7的帧。当计时器超时，只收到了对1、3和5号帧的确认，发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：若文件A作为共享文件，系统应采用何种目录结构?画出示意图。
假定磁盘传输数据以32bit的字为单位，传输速率为1MB／s。CPU的时钟频率为50MHz。采用DMA控制进行输入输出操作，假定DMA的启动操作需要1000个时钟周期，DMA完成时处理中断需要500个时钟周期，如果平均传输的数据长度为4KB，问在磁盘工
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I／O设备读取1000B的数据到主存缓冲区中，该I／O设备一旦启动即按50KB／s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种

随机试题

睾丸病理改变的TM1分类法中，以下哪项不是生精小管的观察指标?
将活塞环放在环槽内，围绕环槽滚动一圈，环在槽内应滚动自如，既不松动，又无阻滞现象。()
A．灵芝B．朱砂C．琥珀D．远志有补气安神功效的药物是
二尖瓣狭窄肥厚型梗阻性心肌病
A．沉而有力B．数而无力C．数而有力D．浮而无力E．迟而有力小儿实热证的脉象是
尿路感染最常见的致病菌是()。
秘书在选择办公用品供应商时应注意其可靠性，包括对()的考虑。
下列关于初级市场与二级市场关系的论述正确的是()。
SpareaKidney?Itisnolongerunusualforaspouseorrelativetodonateakidneytoalovedone,butthenumberofAmerica
A、Shedoesn’tlikeanenergetictype.B、Shedoesn’tlikeaquiettype.C、Shedoesn’tlikeahumoroustype.D、Shedoesn’tlikea

最新回复(0)

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

计算机408

学硕统考专业

下列关于中断I／O方式和DMA方式比较的叙述中，错误的是

用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为

若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是

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

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

睾丸病理改变的TM1分类法中，以下哪项不是生精小管的观察指标?

将活塞环放在环槽内，围绕环槽滚动一圈，环在槽内应滚动自如，既不松动，又无阻滞现象。()

A．灵芝B．朱砂C．琥珀D．远志有补气安神功效的药物是

二尖瓣狭窄肥厚型梗阻性心肌病

A．沉而有力B．数而无力C．数而有力D．浮而无力E．迟而有力小儿实热证的脉象是

尿路感染最常见的致病菌是()。

秘书在选择办公用品供应商时应注意其可靠性，包括对()的考虑。

下列关于初级市场与二级市场关系的论述正确的是()。

SpareaKidney?Itisnolongerunusualforaspouseorrelativetodonateakidneytoalovedone,butthenumberofAmerica

A、Shedoesn’tlikeanenergetictype.B、Shedoesn’tlikeaquiettype.C、Shedoesn’tlikeahumoroustype.D、Shedoesn’tlikea