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

admin2017-11-14 30

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

1824～1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素，证明了化学定律对有机物和无机物是同样适用的科学家是()。

“国际工人协会”宣布成立后，10月协会选出了第一任主席，他是()。

1936年，德奥双方通过()，德国基本上控制了奥地利的内政和外交。

1543年，发表了解剖学专著《人体结构》的是()。

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

1922年2月，美、英、法、意、日五国通过了《五国海军条约》，规定了各国海军主力舰和航空母舰的限额，以及在东亚设置海军基地的要求等内容。该条约的缔结表明()

Thecommittee______ninemembers.

若业主方不具备条件自选管理项目建设则可以考虑以下何种模式()。

()操作可实现不同窗口(任务)之间的切换。

保本浮动收益理财计划是指商业银行按照约定条件向客户保证本金支付．本金以外的投资风险由客户与银行共同承担，并依据实际投资收益情况确定客户实际收益水平的理财计划。()

下列各项中，不属于增量预算基本假定的是()。

《二泉映月》是用下列哪一种乐器演奏的?()

双杠项目的动作从分类学角度来看，可分为___动作、_动作、_____动作。

在SQL中，删除表的语句是

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

计算机408

学硕统考专业

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

1824～1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素，证明了化学定律对有机物和无机物是同样适用的科学家是()。

“国际工人协会”宣布成立后，10月协会选出了第一任主席，他是()。

1936年，德奥双方通过()，德国基本上控制了奥地利的内政和外交。

1543年，发表了解剖学专著《人体结构》的是()。

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

1922年2月，美、英、法、意、日五国通过了《五国海军条约》，规定了各国海军主力舰和航空母舰的限额，以及在东亚设置海军基地的要求等内容。该条约的缔结表明()

Thecommittee______ninemembers.

若业主方不具备条件自选管理项目建设则可以考虑以下何种模式()。

()操作可实现不同窗口(任务)之间的切换。

保本浮动收益理财计划是指商业银行按照约定条件向客户保证本金支付．本金以外的投资风险由客户与银行共同承担，并依据实际投资收益情况确定客户实际收益水平的理财计划。()

下列各项中，不属于增量预算基本假定的是()。

《二泉映月》是用下列哪一种乐器演奏的?()

双杠项目的动作从分类学角度来看，可分为_______动作、_______动作、_______动作。

在SQL中，删除表的语句是

双杠项目的动作从分类学角度来看，可分为___动作、_动作、_____动作。