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

admin2021-08-17 53

问题对于一个长度为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方式和DMA方式比较的叙述中，错误的是
假没变址寄存器R的内容为1000H，指令中的形式地址为2000H；地址1000H中的内容为2000H，地址2000H中的内容为3000H，地址3000H中的内容为4000H，则变址寻址方式下访问到的操作数是
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；
数据链路层采用后退N帧方式进行流量和差错控制，发送方已经发送了编号0～7的帧。当计时器超时，只收到了对1、3和5号帧的确认，发送方需要重传的帧的数目是()。
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：在(5)的基础上，假设送出的主存地址为04011H，是否命中?
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I／O设备读取1000B的数据到主存缓冲区中，该I／O设备一旦启动即按50KB／s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种

随机试题

级数x3n的收敛域为________．
进货谈判后的签约有两种情况：第一，发行业的行规屉将加盖订购单位公章或合同章的订单视为正式合同；第二，就某项业务单独签订合同。()
企业降低风险的途径主要有哪些?
溶液型药剂乳浊液型药剂
绩效考核方法中，常用于企业中层和基础管理人员的是()。
如果某企业的营业杠杆系数是3，说明()。
按照网络分布和覆盖的地理范围，可将计算机网络分为()。
客户关系管理模块是()系统的特有功能模块。
关于公共物品的属性正确的是()。
ITU标准OC-12的传输速率为()。

最新回复(0)

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

计算机408

学硕统考专业

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

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

假没变址寄存器R的内容为1000H，指令中的形式地址为2000H；地址1000H中的内容为2000H，地址2000H中的内容为3000H，地址3000H中的内容为4000H，则变址寻址方式下访问到的操作数是

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

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

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；

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

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

级数x3n的收敛域为________．

进货谈判后的签约有两种情况：第一，发行业的行规屉将加盖订购单位公章或合同章的订单视为正式合同；第二，就某项业务单独签订合同。()

企业降低风险的途径主要有哪些?

溶液型药剂乳浊液型药剂

绩效考核方法中，常用于企业中层和基础管理人员的是()。

如果某企业的营业杠杆系数是3，说明()。

按照网络分布和覆盖的地理范围，可将计算机网络分为()。

客户关系管理模块是()系统的特有功能模块。

关于公共物品的属性正确的是()。

ITU标准OC-12的传输速率为()。