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

admin2017-01-04 28

问题已知待排序的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://jikaoti.com/ti/J6fjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述士族的源流和在西晋的发展过程。

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

关于希腊古风时代和古典时代的叙述不正确的是()。

中共十二届六中全会确定的我国社会主义现代化建设的总体布局是()。

下列不是苏俄实行战时共产主义政策原因的是()。

晚清时期清帝年号的正确排序是

在一个双链表中，在p结点之前插入q结点的操作是()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，…，en)；i=1：while(所剩边数＞=顶点数){从图中删去ei；若图不再连通，则恢复ei；i=

氢冷发电机在哪些情况下，必须保证密封油的供给?

某男，20岁，因饮食不洁导致痢疾，症见大便脓血里急后重，发热腹痛，舌淡红，苔黄腻，脉滑数。医师诊为大肠湿热，处方为黄连、木香，水煎服。医师在方中选用黄连，是因其除清热燥湿外，又能()。

设立一个以生产经营为主的有限责任公司,股东出资可用()方式。

辩证法既可以和唯物主义结合，也可以与唯心主义同流。()

简述冯特对实验心理学的贡献。

Dr.Smith

TheWriterofthispassagehadactedasasecretaryandanactorinhisorhercareer.Accordingtothepassage,theunsuccessf

Facebook’sSystemofDisablingFakeAccountsA)AliciaIstanbulwokeuponerecentWednesdaytofindherselflockedoutof

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

计算机408

学硕统考专业

简述士族的源流和在西晋的发展过程。

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

关于希腊古风时代和古典时代的叙述不正确的是()。

中共十二届六中全会确定的我国社会主义现代化建设的总体布局是()。

下列不是苏俄实行战时共产主义政策原因的是()。

晚清时期清帝年号的正确排序是

在一个双链表中，在*p结点之前插入*q结点的操作是()。

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，…，en)；i=1：while(所剩边数＞=顶点数){从图中删去ei；若图不再连通，则恢复ei；i=

氢冷发电机在哪些情况下，必须保证密封油的供给?

某男，20岁，因饮食不洁导致痢疾，症见大便脓血里急后重，发热腹痛，舌淡红，苔黄腻，脉滑数。医师诊为大肠湿热，处方为黄连、木香，水煎服。医师在方中选用黄连，是因其除清热燥湿外，又能()。

设立一个以生产经营为主的有限责任公司,股东出资可用()方式。

辩证法既可以和唯物主义结合，也可以与唯心主义同流。()

简述冯特对实验心理学的贡献。

Dr.Smith

TheWriterofthispassagehadactedasasecretaryandanactorinhisorhercareer.Accordingtothepassage,theunsuccessf

Facebook’sSystemofDisablingFakeAccountsA)AliciaIstanbulwokeuponerecentWednesdaytofindherselflockedoutof

在一个双链表中，在p结点之前插入q结点的操作是()。