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

admin2017-01-04 49

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

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

答案B

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

评析郑和下西洋的历史条件和意义。

简述弭兵之会的背景、过程和结果。

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

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

洋务派创办军事工业的方式是()。

武昌起义后，全国革命形势发展的同时也潜伏着失败的危机，这主要是由于()。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

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

对于油润湿油层，反韵律油层的变化规律为()。

根据间接言语行为信息推断的情况不同，间接言语行为可以进一步分为“规约性”和_______两种类型。

Studentswillneed【21】alloftheirlanguageskillsinorder【22】understandthereadingselectionsinReader’sChoice.Thebookco

治疗血虚发热的最佳选方是

保险包括哪些种类?

下列建筑基地内设置化粪池的表述，错误的是()。

当预期股息不变时，普通股获利率与股票市价成同方向运动。(　　)

不从事生产经营活动，但依照法律、法规的规定负有纳税义务的单位和个人，除临时取得应税收入或发生应税行为以及只缴纳个人所得税、车船使用税的外，都应按规定向税务机关办理纳税登记。()

认为“个体人格的发展是由本我、自我、超我三者相互斗争，相互协调的结果”的心理学家是()

Ireallyenjoy(work)______togetherwithyou,andthankyouforyourcooperation.

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

计算机408

学硕统考专业

评析郑和下西洋的历史条件和意义。

简述弭兵之会的背景、过程和结果。

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

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

洋务派创办军事工业的方式是()。

武昌起义后，全国革命形势发展的同时也潜伏着失败的危机，这主要是由于()。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

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

对于油润湿油层，反韵律油层的变化规律为()。

根据间接言语行为信息推断的情况不同，间接言语行为可以进一步分为“规约性”和_______两种类型。

Studentswillneed【21】alloftheirlanguageskillsinorder【22】understandthereadingselectionsinReader’sChoice.Thebookco

治疗血虚发热的最佳选方是

保险包括哪些种类?

下列建筑基地内设置化粪池的表述，错误的是()。

当预期股息不变时，普通股获利率与股票市价成同方向运动。( )

不从事生产经营活动，但依照法律、法规的规定负有纳税义务的单位和个人，除临时取得应税收入或发生应税行为以及只缴纳个人所得税、车船使用税的外，都应按规定向税务机关办理纳税登记。()

认为“个体人格的发展是由本我、自我、超我三者相互斗争，相互协调的结果”的心理学家是()

Ireallyenjoy(work)______togetherwithyou,andthankyouforyourcooperation.

当预期股息不变时，普通股获利率与股票市价成同方向运动。(　　)