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

admin2017-11-14 47

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

学硕统考专业

【辉格派】南京大学2005年世界史真题

《颜氏家训》

文艺复兴运动兴起的时间是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

中国第一条自行设计修建的铁路是在（）。

在集中式总线仲裁中，()方式响应时间最快。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

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

设有带头结点的循环双链表表示的线性表L＝＝＝(a1，a2，……，an－1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L＝(a1，a3，……，an……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用

A、Coalburntdailyforthecomfortofourhomes.B、Anythingthatcanbeusedtoproducepower.C、Fuelrefinedfromoilextracted

依据《企业所得税法》规定，符合条件的小型微利企业计征企业所得税的适用税率是()

AttheUniversityofKansasartmuseum,scientiststestedtheeffectofdifferentcoloredwallsontwogroupsofvisitorstoan

小儿6个月前的睡眠时间是小儿4～6岁的睡眠时间是

当由单独或合并持有公司表决权股份总数的10%以上的股东书面请求时，应于该情形出现2个月后召开临时股东大会。(　　)

有一池水，池底有泉水不断涌出，要想把水池的水抽干，10台抽水机需抽8小时，8台抽水机需抽12小时，如果用6台抽水机需抽多少小时?

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

计算机408

学硕统考专业

【辉格派】南京大学2005年世界史真题

《颜氏家训》

文艺复兴运动兴起的时间是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

中国第一条自行设计修建的铁路是在（）。

在集中式总线仲裁中，()方式响应时间最快。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

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

设有带头结点的循环双链表表示的线性表L＝＝＝(a1，a2，……，an－1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L＝(a1，a3，……，an……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用

A、Coalburntdailyforthecomfortofourhomes.B、Anythingthatcanbeusedtoproducepower.C、Fuelrefinedfromoilextracted

依据《企业所得税法》规定，符合条件的小型微利企业计征企业所得税的适用税率是()

AttheUniversityofKansasartmuseum,scientiststestedtheeffectofdifferentcoloredwallsontwogroupsofvisitorstoan

小儿6个月前的睡眠时间是小儿4～6岁的睡眠时间是

当由单独或合并持有公司表决权股份总数的10%以上的股东书面请求时，应于该情形出现2个月后召开临时股东大会。( )

有一池水，池底有泉水不断涌出，要想把水池的水抽干，10台抽水机需抽8小时，8台抽水机需抽12小时，如果用6台抽水机需抽多少小时?

当由单独或合并持有公司表决权股份总数的10%以上的股东书面请求时，应于该情形出现2个月后召开临时股东大会。(　　)