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

admin2017-11-14 66

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

学硕统考专业

克里特文明的文字类型是()。

宁夏回族自治区的设立时间是()。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

乾隆时期，明确规定了驻藏大臣的地位与达赖班禅同等，并实行“金瓶掣签”制度的文件是()。

西汉初年，反驳刘邦“马上治天下”的说法，并向汉帝国治国献策的是()。

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

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

假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

简述在哪些情形下，法定代理或者指定代理终止。

处方调配的基本程序：

悬臂梁AB由三根相同的矩形截面直杆胶合而成，材料的许可应力为[σ]。承载时若胶合面完全开裂，接触面之间无摩擦力，假设开裂后三根杆的挠曲线相同，则开裂后的梁强度条件的承载能力是原来的()。

柱截面强度验算的应力为。柱截面整体稳定性验算中应力为。

无权代理人以被代理人的名义订立的合同，相对人有理由相信行为人有代理权的，该代理行为(　　)。

排出管有室外排水管连接处的检查井，井中心距建筑物外墙不小于()m。

某项目固定资产投资是3850万元，流动资金为462万元，铺底流动资金为139万元，投产后正常生产年份的利润总额为578万元，销售税金及附加为200万元，则正常生产年份的投资利润率为()%。

进口口岸栏应填。成交方式栏目应填。

水池的四周栽了一些树，小贾和小范一前一后朝同一个方向走，他们都边走边数树的棵数，小贾数的第21棵在小范那里是第6棵；小贾数的第8棵在小范那里是第95棵。则水池四周栽了多少棵树?

Stocksarenotgoods--theymerelyare______,exchangingcurrentcashflowsforfutureones.

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

计算机408

学硕统考专业

克里特文明的文字类型是()。

宁夏回族自治区的设立时间是()。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

乾隆时期，明确规定了驻藏大臣的地位与达赖班禅同等，并实行“金瓶掣签”制度的文件是()。

西汉初年，反驳刘邦“马上治天下”的说法，并向汉帝国治国献策的是()。

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

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

假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

简述在哪些情形下，法定代理或者指定代理终止。

处方调配的基本程序：

悬臂梁AB由三根相同的矩形截面直杆胶合而成，材料的许可应力为[σ]。承载时若胶合面完全开裂，接触面之间无摩擦力，假设开裂后三根杆的挠曲线相同，则开裂后的梁强度条件的承载能力是原来的()。

柱截面强度验算的应力为______。柱截面整体稳定性验算中应力为______。

无权代理人以被代理人的名义订立的合同，相对人有理由相信行为人有代理权的，该代理行为( )。

排出管有室外排水管连接处的检查井，井中心距建筑物外墙不小于()m。

某项目固定资产投资是3850万元，流动资金为462万元，铺底流动资金为139万元，投产后正常生产年份的利润总额为578万元，销售税金及附加为200万元，则正常生产年份的投资利润率为()%。

进口口岸栏应填______。成交方式栏目应填______。

水池的四周栽了一些树，小贾和小范一前一后朝同一个方向走，他们都边走边数树的棵数，小贾数的第21棵在小范那里是第6棵；小贾数的第8棵在小范那里是第95棵。则水池四周栽了多少棵树?

Stocksarenotgoods--theymerelyare______,exchangingcurrentcashflowsforfutureones.

柱截面强度验算的应力为。柱截面整体稳定性验算中应力为。

无权代理人以被代理人的名义订立的合同，相对人有理由相信行为人有代理权的，该代理行为(　　)。

进口口岸栏应填。成交方式栏目应填。