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

admin2022-06-07 33

问题已知待排序的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://jikaoti.com/ti/AdDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

在windows操作系统中支持FAT32文件系统，一个文件的物理结构是用文件分配表FAT来表示的，在FAT32中，文件分配表每个表项占32位。如果某分区为FAT32磁盘文件系统，每簇8扇区，扇区的大小为512字节，则该分区最大可为多少字节?每个FAT表占用
已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。补码定点小数；
已知两个实数x=-68，y=-8．25，它们在C语言中定义为float型变量，分别存放在寄存器A和B中。另外，还有两个寄存器C和D。A、B、C、D都是32位的寄存器。　　请回答下列问题(要求用十六进制表示二进制序列)：　　(1)寄存器A
下面关于电子邮件的说法中，不正确的是()。
在存储系统管理中，采用覆盖与交换技术的目的是()。
对于下列关键序列，不能构成某二叉树排序中的一条查找路径的序列是()。
某局域网采用CSMA／CD协议实现介质访问控制，数据传输速率为10Mbit／s，主机甲和主机乙之间的距离为2km，信号传播速度为200000km／s。请回答下列问题，要求说明理由或写出计算过程。若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起
下列说法中，正确的说法有()个。Ⅰ．当进程申请CPU得不到满足时，它将处于阻塞状态。Ⅱ．当进程由执行变为就绪状态时，CPU现场信息必须被保存在PCB中。Ⅲ．一一个进程的状态发生变化总会引起其他一些进程的状态发生变化。
已知加权有向图如图3—2所示，回答下列问题：(1)画出该有向图的邻接矩阵；(2)试利用Dijkstra算法求图3—2中从顶点a到其他各顶点间的最短路径，并给出求解过程。
对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是

随机试题

男性，28岁，打篮球后淋雨，晚上突然寒战，高热，自觉全身肌肉酸痛，右胸疼痛，深呼吸时加重，吐少量铁锈色痰，患者呈急性病容，口角有疱疹，查体温39℃，脉搏88次／分，右肺触觉语颤增强，叩诊呈浊音，可闻及支气管呼吸音，实验室检查：白细胞25×109／L，中性粒
A．促胃液素B．促胰液素C．乙酰胆碱D．缩胆囊素E．血管活性肠肽能够引起胰腺分泌大量H2和HCO3-的激素是
麝香仁粉末用水合氯醛装片，显微观察，可见
对实施暴力行为的精神病人采取强制医疗措施，应当满足以下哪些条件?()
房地产投资包括的阶段有()。[2005年考试真题]
如图，△ABC和△BCD所在平面互相垂直，且AB=BC=BD=2．∠ABC=∠DBC=120°，E、F分别为AC、DC的中点．求证：EF⊥BC；
监狱人民警察的教育培训要突出培训重点，应特别重点教育培训()。
英国的面积不大，但英语在英国本土的方言如果细分，据统计多达三百种以卜。美国的面积大大超过英国本土，但在美国，英语的方言细分却比英国本土少得多。美国英语的方言大体可分出东部、中西部和南部三种。东部方言分布在以波士顿为中心的东北部地区；中西部方言从中部向西部地
[*]
Einsteinisasinger.Einsteinisverygreatbecausehehasmanyinventions.

最新回复(0)

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

计算机408

学硕统考专业

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。补码定点小数；

已知两个实数x=-68，y=-8．25，它们在C语言中定义为float型变量，分别存放在寄存器A和B中。另外，还有两个寄存器C和D。A、B、C、D都是32位的寄存器。 请回答下列问题(要求用十六进制表示二进制序列)： (1)寄存器A

下面关于电子邮件的说法中，不正确的是()。

在存储系统管理中，采用覆盖与交换技术的目的是()。

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

已知加权有向图如图3—2所示，回答下列问题：(1)画出该有向图的邻接矩阵；(2)试利用Dijkstra算法求图3—2中从顶点a到其他各顶点间的最短路径，并给出求解过程。

对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是

A．促胃液素B．促胰液素C．乙酰胆碱D．缩胆囊素E．血管活性肠肽能够引起胰腺分泌大量H2和HCO3-的激素是

麝香仁粉末用水合氯醛装片，显微观察，可见

对实施暴力行为的精神病人采取强制医疗措施，应当满足以下哪些条件?()

房地产投资包括的阶段有()。[2005年考试真题]

如图，△ABC和△BCD所在平面互相垂直，且AB=BC=BD=2．∠ABC=∠DBC=120°，E、F分别为AC、DC的中点．求证：EF⊥BC；

监狱人民警察的教育培训要突出培训重点，应特别重点教育培训()。

[*]

Einsteinisasinger.Einsteinisverygreatbecausehehasmanyinventions.

已知两个实数x=-68，y=-8．25，它们在C语言中定义为float型变量，分别存放在寄存器A和B中。另外，还有两个寄存器C和D。A、B、C、D都是32位的寄存器。　　请回答下列问题(要求用十六进制表示二进制序列)：　　(1)寄存器A