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

admin2019-08-15 41

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

“两个凡是”

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

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

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

丑和荒诞的共同特征是_、、__。

青年脑栓塞，栓子来源多见于

患者，女，30岁。口眼斜2天。前天晨起感觉面部麻木，不能鼓腮，左眼不能闭合，口角歪向右侧，左侧额纹消失，饮食、二便正常，舌苔黄，脉弦。治疗应首选

下列不属于保税区进出口许可证方面的管理规定为()。

下列属于风险管理策略的组成部分的有()。

“社会一旦有技术上的需要，则这种需要比十所大学更能把科学推向前进。”这表明()。

下列选项中，属于因果联系的有()

数据段中有以下定义：　　　ARRAY1　　　　EQU　　　　16H　　　ARRAY2　　　　DW　　　　16H指出下面两条指令的寻址方式：　　　MOV　AX，ARRAY1　；寻址方式：____；　　　MOV　AX，ARRAY2　；寻址方式：

StrategiesforWritingaLiteratureReviewAliteraturereviewdiscussespublishedinformationinaparticularsubjectarea.

U.S.EarlyChildhoodEducationFiftyyearsago,【T1】attendedearlyeducationprograms.Today,【T2】thechildrenof

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

计算机408

学硕统考专业

“两个凡是”

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

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

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

丑和荒诞的共同特征是_______、________、________。

青年脑栓塞，栓子来源多见于

患者，女，30岁。口眼斜2天。前天晨起感觉面部麻木，不能鼓腮，左眼不能闭合，口角歪向右侧，左侧额纹消失，饮食、二便正常，舌苔黄，脉弦。治疗应首选

下列不属于保税区进出口许可证方面的管理规定为()。

下列属于风险管理策略的组成部分的有()。

“社会一旦有技术上的需要，则这种需要比十所大学更能把科学推向前进。”这表明()。

下列选项中，属于因果联系的有()

数据段中有以下定义： ARRAY1 EQU 16H ARRAY2 DW 16H指出下面两条指令的寻址方式： MOV AX，ARRAY1 ；寻址方式：______； MOV AX，ARRAY2 ；寻址方式：__

StrategiesforWritingaLiteratureReviewAliteraturereviewdiscussespublishedinformationinaparticularsubjectarea.

U.S.EarlyChildhoodEducationFiftyyearsago,【T1】______attendedearlyeducationprograms.Today,【T2】______thechildrenof

丑和荒诞的共同特征是_、、__。

数据段中有以下定义：　　　ARRAY1　　　　EQU　　　　16H　　　ARRAY2　　　　DW　　　　16H指出下面两条指令的寻址方式：　　　MOV　AX，ARRAY1　；寻址方式：____；　　　MOV　AX，ARRAY2　；寻址方式：

U.S.EarlyChildhoodEducationFiftyyearsago,【T1】attendedearlyeducationprograms.Today,【T2】thechildrenof