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

admin2019-01-30 35

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

到1869年为止，人类已发现了多少种化学元素()。

系统阐明社会主义初级阶段理论是在()。

在操作系统中，P，V操作是一种()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

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

当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树做删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

试述成就需要理论。

与胰腺MRI扫描参数不符的是

3岁女孩，反复咳嗽2个月。查体：体温正常，浅表淋巴结(一)，咽(一)，两肺多哮鸣音，无水泡音，反复抗生素治疗不愈，以往无呛咳病史，有过敏性鼻炎。此患儿可能诊断是

在工程网络计划的执行过程中，如果需要判断某项工作的进度偏差是否影响总工期，应重点分析该工作的进度偏差与其相应(　　)的关系。

我国出国工人工资单价组成费用中不包括()。

在业务开拓与客户利益存在潜在冲突的情形下，银行业从业人员应当向()主动说明利益冲突的情况，以及处理利益冲突的建议。

某中外合资生产性企业自1997年10月投产后，选择次年为减免税第1年，其7年经营情况如下：该企业()减、免税期满。

群体凝聚力的正性力量包括以下含义()。

某学生由于进步明显，老师取消了对他的处分，这种强化方式是()。

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

计算机408

学硕统考专业

隋统一全国时，与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

到1869年为止，人类已发现了多少种化学元素()。

系统阐明社会主义初级阶段理论是在()。

在操作系统中，P，V操作是一种()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

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

当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树做删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

试述成就需要理论。

与胰腺MRI扫描参数不符的是

3岁女孩，反复咳嗽2个月。查体：体温正常，浅表淋巴结(一)，咽(一)，两肺多哮鸣音，无水泡音，反复抗生素治疗不愈，以往无呛咳病史，有过敏性鼻炎。此患儿可能诊断是

在工程网络计划的执行过程中，如果需要判断某项工作的进度偏差是否影响总工期，应重点分析该工作的进度偏差与其相应( )的关系。

我国出国工人工资单价组成费用中不包括()。

在业务开拓与客户利益存在潜在冲突的情形下，银行业从业人员应当向()主动说明利益冲突的情况，以及处理利益冲突的建议。

某中外合资生产性企业自1997年10月投产后，选择次年为减免税第1年，其7年经营情况如下：该企业()减、免税期满。

群体凝聚力的正性力量包括以下含义()。

某学生由于进步明显，老师取消了对他的处分，这种强化方式是()。

在工程网络计划的执行过程中，如果需要判断某项工作的进度偏差是否影响总工期，应重点分析该工作的进度偏差与其相应(　　)的关系。