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

admin2022-06-07 54

问题已知待排序的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语言；Ⅵ．系统调用；
如果下表是路由器R1的路由表，仔细分析各个表项的特点，并回答如下问题。(1)给出m0和m1所在的网络号，以及可连接的最大主机数目。(2)给出接口m0，m1和m2的合理的IP地址。(3)试给出网络的拓扑。
在虚拟地址和物理地址均为32位、页大小为4KB的某种体系结构中，假定存在下表所示的地址映像关系，问：对应于下列虚拟地址的物理地址分别是什么?(1)22433007H(2)13385ABCH(3)ABC89011H
设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0．5MB／s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请
某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下表6—3所列，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节计址，每页的大小为1024字节。　　(1)将下列逻辑地址转换为物理地址，并说明理
(1)流水线的节拍时间应取各过程段所需时间的最大值，即100ns，该流水线的加速比为(80ns+100ns+60ns+90ns)／100ns=3．3(2)如四个过程段所需执行时间都为85ns，则流水线的节拍时间为85ns，流水线的
已知数组A[1．．n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。(1)给出算法的基本设计思想；(2)根据设计思想，采用C或C++
以下关于路由器的路由表说法正确的是()。I．路由表包含目的网络和到达该目的网络的完整路径Ⅱ．路由表必须包含子网掩码Ⅲ．目的网络和到达该目的网络路径上的下一个路由器的IP地址Ⅳ．目的网络和到达该目的
已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?(1)关键字自小到大有序(key1(key2……>keyn)；(3)奇数关键字顺序有序，偶数关键字

随机试题

当向草图添加几何时，可以像创建草图那样自动添加约束。
质量控制
有关神经上皮性肿瘤，下列哪项说法不恰当
水泥砂浆、现浇水磨石整体楼地面层工程量计算()。
在采用实测法进行施工现场的质量检查中，“套”是指以方尺套方，辅以塞尺检查，通常用“套”的方法进行检查的项目有()。
可参与证券投资的金融机构包括()。Ⅰ．证券经营机构Ⅱ．银行业金融机构Ⅲ．保险经营机构Ⅳ．企业集团财务公司
()青年婚前社交自由。晚上吹芦笙串姑娘，“串寨子”、“丢包”等都是选择对象和表达爱情的方式。
兴旺中学学生排练一个大型节目，需要排成一个若干层的中空方阵，外层需要学生：120人，中间一层需要学生88人，该方阵共需要学生多少人?()
(2011年上半年)有关风险识别，以下说法不正确的是(67)。
舞龙体现了中国人团结、奋进的精神，是中华民族宝贵的文化遗产，中国文化的标志之一。

最新回复(0)

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

计算机408

学硕统考专业

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

如果下表是路由器R1的路由表，仔细分析各个表项的特点，并回答如下问题。(1)给出m0和m1所在的网络号，以及可连接的最大主机数目。(2)给出接口m0，m1和m2的合理的IP地址。(3)试给出网络的拓扑。

在虚拟地址和物理地址均为32位、页大小为4KB的某种体系结构中，假定存在下表所示的地址映像关系，问：对应于下列虚拟地址的物理地址分别是什么?(1)22433007H(2)13385ABCH(3)ABC89011H

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

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

以下关于路由器的路由表说法正确的是()。I．路由表包含目的网络和到达该目的网络的完整路径Ⅱ．路由表必须包含子网掩码Ⅲ．目的网络和到达该目的网络路径上的下一个路由器的IP地址Ⅳ．目的网络和到达该目的

已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?(1)关键字自小到大有序(key1(key2……>keyn)；(3)奇数关键字顺序有序，偶数关键字

当向草图添加几何时，可以像创建草图那样自动添加约束。

质量控制

有关神经上皮性肿瘤，下列哪项说法不恰当

水泥砂浆、现浇水磨石整体楼地面层工程量计算()。

在采用实测法进行施工现场的质量检查中，“套”是指以方尺套方，辅以塞尺检查，通常用“套”的方法进行检查的项目有()。

可参与证券投资的金融机构包括()。Ⅰ．证券经营机构Ⅱ．银行业金融机构Ⅲ．保险经营机构Ⅳ．企业集团财务公司

()青年婚前社交自由。晚上吹芦笙串姑娘，“串寨子”、“丢包”等都是选择对象和表达爱情的方式。

兴旺中学学生排练一个大型节目，需要排成一个若干层的中空方阵，外层需要学生：120人，中间一层需要学生88人，该方阵共需要学生多少人?()

(2011年上半年)有关风险识别，以下说法不正确的是(67)。

舞龙体现了中国人团结、奋进的精神，是中华民族宝贵的文化遗产，中国文化的标志之一。