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

admin2017-01-04 43

问题已知待排序的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://www.kaotiyun.com/show/LQRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

西汉初年，在刘邦翦灭异姓诸侯王的过程中，被保留下来的异姓诸侯王是()

评述抗战的三个阶段。

简述西欧城市兴起的原因、方式及其影响。

简述雅典民主政治的形成过程。

简述工农武装割据存在与发展的原因和条件。

为了防止谷贱伤农的现象，()向汉文帝提出了人粟拜爵的建议，准许富人买粟输边，按所输多少授予爵位。这一办法的实行，使农民的处境有所改善。

拉美独立后，各国政治上的一种普遍现象是()，实质上它是拉美各国大地主专政的一种特殊形式。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。

三面刃铣刀圆柱面齿槽铣削后前刀面不平整，呈凹弧的原因是___________。

常用的平均数指标分三类，选用时必须遵循下列原则，除了

小额投资积累经验一般是(　　)的理财需求。

商用房贷款的贷前调查内容包括()。

劳动力需求是一种()需求。

中国古代园林理水之法一般有掩、隔、破三种。()

中国特色社会主义文化的特征不包括()。

Overthepastyears,wehavewitnesseddestructionsofvariouskindscausedbyhumanactions.Asauniversitystudent,writeal

以下对于主流嵌入式操作系统的叙述，错误的是()。

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

计算机408

学硕统考专业

西汉初年，在刘邦翦灭异姓诸侯王的过程中，被保留下来的异姓诸侯王是()

评述抗战的三个阶段。

简述西欧城市兴起的原因、方式及其影响。

简述雅典民主政治的形成过程。

简述工农武装割据存在与发展的原因和条件。

为了防止谷贱伤农的现象，()向汉文帝提出了人粟拜爵的建议，准许富人买粟输边，按所输多少授予爵位。这一办法的实行，使农民的处境有所改善。

拉美独立后，各国政治上的一种普遍现象是()，实质上它是拉美各国大地主专政的一种特殊形式。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。

三面刃铣刀圆柱面齿槽铣削后前刀面不平整，呈凹弧的原因是___________。

常用的平均数指标分三类，选用时必须遵循下列原则，除了

小额投资积累经验一般是( )的理财需求。

商用房贷款的贷前调查内容包括()。

劳动力需求是一种()需求。

中国古代园林理水之法一般有掩、隔、破三种。()

中国特色社会主义文化的特征不包括()。

Overthepastyears,wehavewitnesseddestructionsofvariouskindscausedbyhumanactions.Asauniversitystudent,writeal

以下对于主流嵌入式操作系统的叙述，错误的是()。

小额投资积累经验一般是(　　)的理财需求。