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

admin2021-08-17 32

问题对于一个长度为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://jikaoti.com/ti/SiDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是
下列关于中断I／O方式和DMA方式比较的叙述中，错误的是
假没变址寄存器R的内容为1000H，指令中的形式地址为2000H；地址1000H中的内容为2000H，地址2000H中的内容为3000H，地址3000H中的内容为4000H，则变址寻址方式下访问到的操作数是
用海明码对长度为8位的数据进行检／纠错时，若能纠正一位错，则校验位数至少为
一个栈的入栈序列为1，2，3，…，n，其出栈序列是ρ1，ρ2，ρ3，…，ρn。若p2=3，则ρ可能取值的个数是
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少?计算在等概率
有某个操作系统对外存分配采用混合索引分配方式。在索引节点中包含了文件的物理结构数组iaddr[12]，其中前10项iaddr[O]～iaddr[9]为直接地址，iaddr[10]为一次间接地址，iaddr[11]为二次间接地址。如果系统的块的大小是4KB，

随机试题

当气体溶解度很大时，可以采用提高气相湍流强度来降低吸收阻力。()
绩效
某患者血氧检查为：血氧容量120ml/L，动脉血氧含量114ml/L，氧分压13.3kPa(100mmHg)，动静脉氧差35ml/L，该患者可能性最大的疾病
X线球管阳极靶面的作用是
地籍调查过程中，土地登记代理人应依照规定的格式填写()作为申请土地登记的权属依据。
外商投资企业计算应纳税所得额时，下列各项支出不准予扣除的有()。
根据现行税法规定，下列应当征收消费税的有()。
现在，很多保健品的广告做得很好，但消费者并不知道自己有没有必要吃这些东西。其实很多保健品在研发时并未做过__________调查，并不知道哪种营养素是大家普遍缺乏的，服用未经这样的调查就开发出的保健品，对消费者来说完全是一种__________。依次填入画
在TCP/IP网络的传输层有两种传输协议，其中TCP是一个面向连接的协议，它提供(253)的连接功能，采用(254)技术来实现可靠数据流的传送。为了提高效率，又引入了滑动窗口协议，协议规定重传(255)的分组，这种分组的数量最多可以(256)，TCP协议采
GoodWritingEducatorsinEnglish-speakingcountrieshavedevelopedasetofbasiccharacteristicsofgoodEnglishwriting—

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

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

一个栈的入栈序列为1，2，3，…，n，其出栈序列是ρ1，ρ2，ρ3，…，ρn。若p2=3，则ρ可能取值的个数是

有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少?计算在等概率

有某个操作系统对外存分配采用混合索引分配方式。在索引节点中包含了文件的物理结构数组iaddr[12]，其中前10项iaddr[O]～iaddr[9]为直接地址，iaddr[10]为一次间接地址，iaddr[11]为二次间接地址。如果系统的块的大小是4KB，

当气体溶解度很大时，可以采用提高气相湍流强度来降低吸收阻力。()

绩效

某患者血氧检查为：血氧容量120ml/L，动脉血氧含量114ml/L，氧分压13.3kPa(100mmHg)，动静脉氧差35ml/L，该患者可能性最大的疾病

X线球管阳极靶面的作用是

地籍调查过程中，土地登记代理人应依照规定的格式填写()作为申请土地登记的权属依据。

外商投资企业计算应纳税所得额时，下列各项支出不准予扣除的有()。

根据现行税法规定，下列应当征收消费税的有()。

GoodWritingEducatorsinEnglish-speakingcountrieshavedevelopedasetofbasiccharacteristicsofgoodEnglishwriting—