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

admin2018-08-12 33

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

陈云作《目前财政经济的情况和克服困难的若干办法》的重要讲话，分析当前财政经济方面的主要困难，提出克服困难的六点意见的会议是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

简述北宋与辽的关系。

北约和华约两个组织对峙近半个世纪，其影响是()。

鉴于汉匈关系的状况，汉初向汉高祖提出和亲政策的是()。

中华人民共和国恢复在联合国合法席位的时间是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

下图是校园网某台主机在命令行模式执行某个命令时用sniffer捕获的数据包。请根据图中信息回答下列问题。图中的①～④删除了部分显示信息，其中②处应该是_【18】_，③处应该是_【19】_。

常规血清铁测定多采用的分析方法是

下列关于风险损失控制系统的表述中，正确的有(　　)。

根据轮系中各齿轮的轴线在空间的位置是否固定，将基本轮系分为定轴轮系和()。

下列情况中免征房产税的是()。

对以下一些与生活相关的物理现象的说法，你认为正确的是()。

【2015年重庆开县.单选】德育目标是德育工作的()。

南京：江苏

网络的安全策略包括技术和制度两个方面。它的制定涉及网络使用与管理制定和【　　】两方面的内容。

R1、R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表如左图所示，当R1收到R2发送的如右图的(V，D)报文后，R1更新的四个路由表项中距离值从上到下依次为()。

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

计算机408

学硕统考专业

陈云作《目前财政经济的情况和克服困难的若干办法》的重要讲话，分析当前财政经济方面的主要困难，提出克服困难的六点意见的会议是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

简述北宋与辽的关系。

北约和华约两个组织对峙近半个世纪，其影响是()。

鉴于汉匈关系的状况，汉初向汉高祖提出和亲政策的是()。

中华人民共和国恢复在联合国合法席位的时间是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

下图是校园网某台主机在命令行模式执行某个命令时用sniffer捕获的数据包。请根据图中信息回答下列问题。图中的①～④删除了部分显示信息，其中②处应该是_【18】_，③处应该是_【19】_。

常规血清铁测定多采用的分析方法是

下列关于风险损失控制系统的表述中，正确的有( )。

根据轮系中各齿轮的轴线在空间的位置是否固定，将基本轮系分为定轴轮系和()。

下列情况中免征房产税的是()。

对以下一些与生活相关的物理现象的说法，你认为正确的是()。

【2015年重庆开县.单选】德育目标是德育工作的()。

南京：江苏

网络的安全策略包括技术和制度两个方面。它的制定涉及网络使用与管理制定和【 】两方面的内容。

R1、R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表如左图所示，当R1收到R2发送的如右图的(V，D)报文后，R1更新的四个路由表项中距离值从上到下依次为()。

下列关于风险损失控制系统的表述中，正确的有(　　)。

网络的安全策略包括技术和制度两个方面。它的制定涉及网络使用与管理制定和【　　】两方面的内容。