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

admin2021-08-17 72

问题对于一个长度为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请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
一个栈的入栈序列为1，2，3，…，n，其出栈序列是ρ1，ρ2，ρ3，…，ρn。若p2=3，则ρ可能取值的个数是
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
有某个操作系统对外存分配采用混合索引分配方式。在索引节点中包含了文件的物理结构数组iaddr[12]，其中前10项iaddr[O]～iaddr[9]为直接地址，iaddr[10]为一次间接地址，iaddr[11]为二次间接地址。如果系统的块的大小是4KB，
假定一个计算机系统中有一个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号帧的确认，发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习，程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3，要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问：若文件A作为共享文件，系统应采用何种目录结构?画出示意图。

随机试题

血管紧张素转化酶抑制剂不适用于
桥孔溢流水力计算是基于什么堰流：
下列工程中，不属于机电工程专业建造师执业范围的是()工程。
构件按最小配筋率配筋时，按()原则代换钢筋。
2×17年12月，经董事会批准，甲公司自2×18年1月1日起撤销某营销网点，该业务重组计划已对外公告。为实施该业务重组计划，甲公司预计发生以下支出或损失：因辞退职工将支付补偿款100万元，因撤销门店租赁合同将支付违约金20万元，因处置门店内设备将发生损失5
下列()行为，属于违反《风景名胜区管理暂行条例》。
劳务派遣单位的职责包括()。
科举考试的殿试始于()。
A、 B、 C、 D、 A
After21yearsofmarriage,mywifewantedmetotakeanotherwomanouttodinnerandamovie.Shesaid,"Iloveyou,butIknow

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

假定一个计算机系统中有一个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号帧的确认，发送方需要重传的帧的数目是()。

血管紧张素转化酶抑制剂不适用于

桥孔溢流水力计算是基于什么堰流：

下列工程中，不属于机电工程专业建造师执业范围的是()工程。

构件按最小配筋率配筋时，按()原则代换钢筋。

下列()行为，属于违反《风景名胜区管理暂行条例》。

劳务派遣单位的职责包括()。

科举考试的殿试始于()。

A、 B、 C、 D、 A

After21yearsofmarriage,mywifewantedmetotakeanotherwomanouttodinnerandamovie.Shesaid,"Iloveyou,butIknow