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

admin2017-11-14 26

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

《洛桑协定》

下列对春秋时期各国称霸的顺序描述错误的选项是()

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

西汉末年，()对太初历作了系统的解释，并调整为三统历。这是中国第一部记载完整的历法。

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

分析论述斯大林社会主义工业化。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

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

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

在散列表中，当装填因子非常接近1时，线性探测类似于()查找。

火花塞有哪些类型?各有什么特点?

患者，男25岁。因上前牙有黄黑斑块要求治疗。检查：双侧上前牙唇面有黄褐色斑块，无缺损，表面光滑，质硬，探(一)，叩(一)，无松动，冷测反应正常，诉当地乡亲中亦有相似情况。最可能的诊断是

昼夜分阴阳，则上午为

乙脑的主要致死原因是

房地产置业投资的效果主要表现为()等。

按规定退税时应当同时退还多征税款部分所产生的利息的，应退利息按照海关填发税款缴款书之日中国人民银行规定的活期储蓄存款利息率计算。

2007年末全国就业人员76990万人，比上年末增加590万人，其中，第一产业就业人员31444万人，占全国就业人员的40．8％；第二产业20629万人，占26．8％；第三产业24917万人，占32．4％。年末城镇就业人员29350万人，比上年末净增加10

有下列程序：#include＜stdio.h＞voidfun(inta,intn)/fun函数的功能是将a所指数组元素从大到小排序*/{intt,i,j;for(i=0;i＜n-1;j++)for(j=i+1;j＜n;j++)

利用对话框提示用户输入参数的查询过程称为()。

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

计算机408

学硕统考专业

《洛桑协定》

下列对春秋时期各国称霸的顺序描述错误的选项是()

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

西汉末年，()对太初历作了系统的解释，并调整为三统历。这是中国第一部记载完整的历法。

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

分析论述斯大林社会主义工业化。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

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

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

在散列表中，当装填因子非常接近1时，线性探测类似于()查找。

火花塞有哪些类型?各有什么特点?

患者，男25岁。因上前牙有黄黑斑块要求治疗。检查：双侧上前牙唇面有黄褐色斑块，无缺损，表面光滑，质硬，探(一)，叩(一)，无松动，冷测反应正常，诉当地乡亲中亦有相似情况。最可能的诊断是

昼夜分阴阳，则上午为

乙脑的主要致死原因是

房地产置业投资的效果主要表现为()等。

按规定退税时应当同时退还多征税款部分所产生的利息的，应退利息按照海关填发税款缴款书之日中国人民银行规定的活期储蓄存款利息率计算。

2007年末全国就业人员76990万人，比上年末增加590万人，其中，第一产业就业人员31444万人，占全国就业人员的40．8％；第二产业20629万人，占26．8％；第三产业24917万人，占32．4％。年末城镇就业人员29350万人，比上年末净增加10

有下列程序：#include＜stdio.h＞voidfun(int*a,intn)/*fun函数的功能是将a所指数组元素从大到小排序*/{intt,i,j;for(i=0;i＜n-1;j++)for(j=i+1;j＜n;j++)

利用对话框提示用户输入参数的查询过程称为()。

有下列程序：#include＜stdio.h＞voidfun(inta,intn)/fun函数的功能是将a所指数组元素从大到小排序*/{intt,i,j;for(i=0;i＜n-1;j++)for(j=i+1;j＜n;j++)