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

admin2019-01-30 53

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

选项 A、O(nlog₂n)
B、O(nlog₂n)
C、O(klog₂n)
D、O(klog₂k)

答案B

解析此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog₂k)。可以用二叉树分治形式描述，最好的情况是树的高度为log₂k。全部时间下界为O(nlog₂k)。应选B。

转载请注明原文地址:https://kaotiyun.com/show/7KRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

试析巴以冲突的历史根源。

民国时期，新旧思潮流派的争鸣中，一个中心的议题就是体制，下列选项中，代表无政府主义的是()。

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

周王室的两大官僚系统是()。

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

下图所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令，但图中未标出。

m阶B一树是一棵()。

进程P1、P2和P3单独执行时间分别为10min、15min和20min，其中处理机占用时间分别为2min、3min和12min。如果采用多道程序设计技术使其并发，并假设处理机的利用率可以达到60％，加上系统开销5min，则并发使得计算机系统

布袋除尘器为二级回收装置，回收后的粉末较细，一般仍可重复使用。

A．红色至褐红色B．橘红色C．绿黑色或棕红色D．樱红色或红棕色E．白色赭石的条痕色是()。

房地产经纪机构的义务不包括()。[2010年考试真题]

应急预案的培训应当做到()。

资产负债表由()系统完成。

发行债券是金融机构的非主动负债，金融机构没有较大的主动权和灵活性。(　　)

“提笔忘字”属于()。

中国的传统音乐可以分为()。

【B1】【B12】

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

计算机408

学硕统考专业

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

试析巴以冲突的历史根源。

民国时期，新旧思潮流派的争鸣中，一个中心的议题就是体制，下列选项中，代表无政府主义的是()。

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

周王室的两大官僚系统是()。

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

下图所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令，但图中未标出。

m阶B一树是一棵()。

进程P1、P2和P3单独执行时间分别为10min、15min和20min，其中处理机占用时间分别为2min、3min和12min。如果采用多道程序设计技术使其并发，并假设处理机的利用率可以达到60％，加上系统开销5min，则并发使得计算机系统

布袋除尘器为二级回收装置，回收后的粉末较细，一般仍可重复使用。

A．红色至褐红色B．橘红色C．绿黑色或棕红色D．樱红色或红棕色E．白色赭石的条痕色是()。

房地产经纪机构的义务不包括()。[2010年考试真题]

应急预案的培训应当做到()。

资产负债表由()系统完成。

发行债券是金融机构的非主动负债，金融机构没有较大的主动权和灵活性。( )

“提笔忘字”属于()。

中国的传统音乐可以分为()。

【B1】【B12】

发行债券是金融机构的非主动负债，金融机构没有较大的主动权和灵活性。(　　)