已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

admin2022-06-07 65

问题已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

选项 A、O(klog₂k)
B、O(klog₂n)
C、O(nlog₂k)
D、O(nlog₂n)

答案B

解析因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为n／k×O(klog₂k)，因此全部时间下界应为O(nlog₂k)。

转载请注明原文地址:https://kaotiyun.com/show/8k3i777K

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

计算机408

学硕统考专业

相关试题推荐

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是
操作系统为用户提供了多种接口，它们是()。I．计算机高级指令；Ⅱ．终端命令；Ⅲ．图标菜单；Ⅳ．汇编语言；V．C语言；Ⅵ．系统调用；
虚拟页式存储管理中，CPU须具备必要的物理硬件的支持，而不是必需的单元是()。
设有4台主机A、B、C和D都处在同一物理网络中，它们的IP地址分别为192．155．28．112、192．155．28．120、192．155．28．135和192．155．28．202，子网掩码都是255．255．255．224，请回答：若要使该网络
设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时问为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时间为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。
下列的应用层协议中，()是采用UDP传输的。
如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：(1)该网络发送一帧的发送延时和传输延时分别是多少?(2)网络的利
对于下列关键序列，不能构成某二叉树排序中的一条查找路径的序列是()。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E
(1)流水线的节拍时间应取各过程段所需时间的最大值，即100ns，该流水线的加速比为(80ns+100ns+60ns+90ns)／100ns=3．3(2)如四个过程段所需执行时间都为85ns，则流水线的节拍时间为85ns，流水线的

随机试题

你是某高校大学生下乡支教活动的负责人，在与某小学校长沟通支教事宜时，校长认为暑假时间短，支教起不到实际作用，还说学生都已经放假很难再次集中，人员接送以及饮食安排也存在困难。你会如何说服这位校长？请把主考官当作小学校长，进行现场模拟。
___________是指应用程序和数据库的数据结构之间相互独立，不受影响。
Morethanfortythousandreaderstoldusthattheylookedforinclosefriendships,whattheyexpected【C1】______friends,whatth
下列易并发中毒性结肠扩张的是
肾结核术后还需抗结核治疗的时间为
关于行政处罚的种类中不包括的内容为()。
欺诈发行股票、债券罪有下列()情形之一的，应予立案追诉。I．发行数额在500万元以上的Ⅱ．伪造、变造国家机关公文、有效证明文件或者相关凭证、单据的Ⅲ．利用募集的资金进行违法活动的Ⅳ．转移或隐瞒所募集资金的
企业所有者权益资金与债务资金各占50%，则企业(　　)。
项目规模评估的效益成本评比法包括()。
正则明事务所的统计员小任需要对本所外汇报告的完成情况进行统计分析，并据此计算员工奖金。按照下列要求帮助小任完成相关的统计工作并对结果进行保存：在工作表“员工个人情况统计”中，对每位员工的报告完成情况及奖金数进行计算统计并依次填入相应的单元格。

最新回复(0)

已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

计算机408

学硕统考专业

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是

操作系统为用户提供了多种接口，它们是()。I．计算机高级指令；Ⅱ．终端命令；Ⅲ．图标菜单；Ⅳ．汇编语言；V．C语言；Ⅵ．系统调用；

虚拟页式存储管理中，CPU须具备必要的物理硬件的支持，而不是必需的单元是()。

设有4台主机A、B、C和D都处在同一物理网络中，它们的IP地址分别为192．155．28．112、192．155．28．120、192．155．28．135和192．155．28．202，子网掩码都是255．255．255．224，请回答：若要使该网络

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时问为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时间为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

下列的应用层协议中，()是采用UDP传输的。

对于下列关键序列，不能构成某二叉树排序中的一条查找路径的序列是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

(1)流水线的节拍时间应取各过程段所需时间的最大值，即100ns，该流水线的加速比为(80ns+100ns+60ns+90ns)／100ns=3．3(2)如四个过程段所需执行时间都为85ns，则流水线的节拍时间为85ns，流水线的

___________是指应用程序和数据库的数据结构之间相互独立，不受影响。

Morethanfortythousandreaderstoldusthattheylookedforinclosefriendships,whattheyexpected【C1】______friends,whatth

下列易并发中毒性结肠扩张的是

肾结核术后还需抗结核治疗的时间为

关于行政处罚的种类中不包括的内容为()。

欺诈发行股票、债券罪有下列()情形之一的，应予立案追诉。I．发行数额在500万元以上的Ⅱ．伪造、变造国家机关公文、有效证明文件或者相关凭证、单据的Ⅲ．利用募集的资金进行违法活动的Ⅳ．转移或隐瞒所募集资金的

企业所有者权益资金与债务资金各占50%，则企业( )。

项目规模评估的效益成本评比法包括()。

企业所有者权益资金与债务资金各占50%，则企业(　　)。