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

admin2022-06-07 72

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

学硕统考专业

相关试题推荐

有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是()。
请求分页管理系统中，假设某进程的页表内容，如下表所示：页面大小为4KB，一次内存盼访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用
某机的主要部件如图4—4所示。(1)请补充各部件间的主要连接线，并注明数据流动方向；(2)拟出指令SUB(R1)，-(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和目的操作数地址分别在寄存器R1和R2中，
某简单分页式存储管理中，逻辑地址空间分页为每页1KB，对应相应的物理块。设主存总容量为256KB，描述主存分配情况如表1—2所列(0表示未分配，1表示已分配)。此时，操作系统创建了一个新进程，大小为2．5KB，按首先分配低址空间的策略，那么，分配
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
下列的应用层协议中，()是采用UDP传输的。
如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：(1)该网络发送一帧的发送延时和传输延时分别是多少?(2)网络的利
某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT服务器上，并且通过NAT服务器连接到Internel：上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1
某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB(快表)采用全相联映射，有4个页表项，内容如表5-1所列。则对虚拟地址03FFF180H进行虚实地址变换的结果是()
队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作()。

随机试题

三叉神经分别由_________、_________和_________组成。
枳实对心血管系统的药理作用是
公司申请股票上市的条件之一是向社会公开发行的股份达到公司股份总数的()以上；公司股本总额超过人民币()亿元的，向社会公开发行股份的比例为10％以上。
下列各项中属于会计政策变更的是()。
“白如玉、薄如纸、明如镜、声如罄”是()的特点。
一种学习对另一种学习起干扰或抑制作用，被称为()
一、注意事项1．申论考试与一般的写作考试不同，它是对应考者阅读理解能力、分析能力、提出并解决问题能力和文字表达能力的综合测试。2．请先仔细阅读给定的资料，然后按照后面提出的“申论要求”依次作答。二、给定资料目前，我国正处在工业化进
简述牵连犯的概念和特征。
社会发展过程呈现出统一性和多样性，是由于
f(x)在[一1，1]上连续，则x=0是函数g(x)=的()．

最新回复(0)

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

计算机408

学硕统考专业

有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是()。

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

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

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT服务器上，并且通过NAT服务器连接到Internel：上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB(快表)采用全相联映射，有4个页表项，内容如表5-1所列。则对虚拟地址03FFF180H进行虚实地址变换的结果是()

队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作()。

三叉神经分别由_________、_________和_________组成。

枳实对心血管系统的药理作用是

公司申请股票上市的条件之一是向社会公开发行的股份达到公司股份总数的()以上；公司股本总额超过人民币()亿元的，向社会公开发行股份的比例为10％以上。

下列各项中属于会计政策变更的是()。

“白如玉、薄如纸、明如镜、声如罄”是()的特点。

一种学习对另一种学习起干扰或抑制作用，被称为()

简述牵连犯的概念和特征。

社会发展过程呈现出统一性和多样性，是由于

f(x)在[一1，1]上连续，则x=0是函数g(x)=的()．

三叉神经分别由_____、_和_____组成。