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

admin2022-06-07 41

问题已知待排序的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

学硕统考专业

相关试题推荐

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。反码定点小数；
已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。补码定点小数；
下面关于电子邮件的说法中，不正确的是()。
如果一台主机的IP地址为192．168．0．10，子网俺码为255．255．255．224，那么主机所在网络的网络号占IP地址的位数是()。
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
下列的应用层协议中，()是采用UDP传输的。
如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：(1)该网络发送一帧的发送延时和传输延时分别是多少?(2)网络的利
处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设：①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)
以下关于路由器的路由表说法正确的是()。I．路由表包含目的网络和到达该目的网络的完整路径Ⅱ．路由表必须包含子网掩码Ⅲ．目的网络和到达该目的网络路径上的下一个路由器的IP地址Ⅳ．目的网络和到达该目的
如果IOBASE2以太网中有一台工作站的网卡出现故障，它始终不停地发送帧。试分析一下，这个网络会出现什么现象?()

随机试题

既可散风解表，通窍止痛，又可消肿排脓的药物是
声环境功能区的4b类是指()。
环境问题的识别应根据开发区的性质、规模、建设内容、发展规划并结合()进行。
工程项目财务评价参数包括()。
下列关于股东财富最大化目标的表述中，正确的有()。
从前有个医生，自称擅长外科。一次，有位将领在战场上中了流箭．箭头深深扎进筋骨内，痛苦不堪，他立即请那位医生进行手术。医生来到床边，稍一察看，便掏出一把大剪刀，剪去露在外面的箭杆，就要辞去。将军拉住他问：“箭头还扎在肉里面，怎么不取出来?”医生回答：“这是内
强调心理学不应该以意识为主要研究对象的学派是()。(2008年)
关于项目经理的角色，下列描述中正确的是()。
Dreams
A、Saws,choppers,axes,tongs,hooks.B、Axes,saws,choppers,tongs,hooks.C、Choppers,axes;saws,hooks,tongs.D、Axes,saws,

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

如果一台主机的IP地址为192．168．0．10，子网俺码为255．255．255．224，那么主机所在网络的网络号占IP地址的位数是()。

某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?

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

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

如果IOBASE2以太网中有一台工作站的网卡出现故障，它始终不停地发送帧。试分析一下，这个网络会出现什么现象?()

既可散风解表，通窍止痛，又可消肿排脓的药物是

声环境功能区的4b类是指()。

环境问题的识别应根据开发区的性质、规模、建设内容、发展规划并结合()进行。

工程项目财务评价参数包括()。

下列关于股东财富最大化目标的表述中，正确的有()。

强调心理学不应该以意识为主要研究对象的学派是()。(2008年)

关于项目经理的角色，下列描述中正确的是()。

Dreams

A、Saws,choppers,axes,tongs,hooks.B、Axes,saws,choppers,tongs,hooks.C、Choppers,axes;saws,hooks,tongs.D、Axes,saws,