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

admin2022-06-07 35

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

学硕统考专业

相关试题推荐

请求分页管理系统中，假设某进程的页表内容，如下表所示：页面大小为4KB，一次内存盼访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用
在一个根目录常驻内存的文件系统中，目录文件采用链接结构，每个目录下最多存放80个文件或目录(称为下级文件)。每个磁盘块最多可存放10个文件目录项，且满足下列要求：如果下级文件是目录文件，则上级目录项指向该目录文件的第一块地址。假设目录结构中文件或子目录按自
如果一台主机的IP地址为192．168．0．10，子网俺码为255．255．255．224，那么主机所在网络的网络号占IP地址的位数是()。
已知加权有向图如图3—2所示，回答下列问题：(1)画出该有向图的邻接矩阵；(2)试利用Dijkstra算法求图3—2中从顶点a到其他各顶点间的最短路径，并给出求解过程。
对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。
某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。
以下关于路由器的路由表说法正确的是()。I．路由表包含目的网络和到达该目的网络的完整路径Ⅱ．路由表必须包含子网掩码Ⅲ．目的网络和到达该目的网络路径上的下一个路由器的IP地址Ⅳ．目的网络和到达该目的

随机试题

某工业企业为增值税一般纳税人。2019年8月，以每台1500元(不含税)的价格将自己生产的冰箱卖给某贸易公司100台。本月企业购进原材料支出8万元，增值税专用发票注明税额1．04万元；购入低值易耗品支出2万元，增值税专用发票注明税额2600元。问
吸收合并
简述斯金纳强化理论的基本观点。
(非英语类学生必做)IarrivedintheUnitedStates【61】February6,1986,butIremembermyfirstdayherevery【62】Myfriendwaswa
抗休克治疗的关键措施是去除致休克的病因和下列哪项
A．第一代头孢菌素B．第二代头孢菌素C．第三代头孢菌素D．第四代头孢菌素E．第五代头孢菌素(头孢菌素类抗生素的典型品种)头孢吡肟(注射)
物业管理企业与新闻媒体协调沟通的方式不包括()。
社会主义市场经济运行的根本目标是实现()。
实践是检验真理的唯一标准，并不排斥逻辑证明的作用。逻辑证明()
(a)根据《公司条例》注册的商业组织与自然人之间的异同是什么?(b)用已经判决的案例解释超越公司能力和董事权力的交易的后果。(1992年6月)

最新回复(0)

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

计算机408

学硕统考专业

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

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

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

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。

某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。

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

吸收合并

简述斯金纳强化理论的基本观点。

(非英语类学生必做)IarrivedintheUnitedStates【61】February6,1986,butIremembermyfirstdayherevery【62】Myfriendwaswa

抗休克治疗的关键措施是去除致休克的病因和下列哪项

A．第一代头孢菌素B．第二代头孢菌素C．第三代头孢菌素D．第四代头孢菌素E．第五代头孢菌素(头孢菌素类抗生素的典型品种)头孢吡肟(注射)

物业管理企业与新闻媒体协调沟通的方式不包括()。

社会主义市场经济运行的根本目标是实现()。

实践是检验真理的唯一标准，并不排斥逻辑证明的作用。逻辑证明()

(a)根据《公司条例》注册的商业组织与自然人之间的异同是什么?(b)用已经判决的案例解释超越公司能力和董事权力的交易的后果。(1992年6月)