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

admin2022-06-07 45

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

选项 A、O(klog₂k)
B、O(klog₂n)
C、O(nlog₂k)
D、O(nlog₂n)

答案B

解析因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为n／k×O(klog₂k)，因此全部时间下界应为O(nlog₂k)。

转载请注明原文地址:https://kaotiyun.com/show/8k3i777K

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

计算机408

学硕统考专业

相关试题推荐

在操作系统中，要对并发进程进行同步的原因是()。
虚拟页式存储管理中，CPU须具备必要的物理硬件的支持，而不是必需的单元是()。
下列有关I／O编址方式的描述中，正确的是()。
某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配(BestFit)算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是____。
某局域网采用CSMA／CD协议实现介质访问控制，数据传输速率为10Mbit／s，主机甲和主机乙之间的距离为2km，信号传播速度为200000km／s。请回答下列问题，要求说明理由或写出计算过程。若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E
一台主机申请了一个到WWW．Abcedu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：由个人主机到本地DNS服务器查询是采用了什么方式?
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨称
关于DMA方式和通道方式，下列说法中错误的是()。
处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设：①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)

随机试题

舍审公廨
网上支付以_______为基础，利用银行所支持的某种_______工具，实现从_______到_______、_______之间的在线_______、_______、_______、_______等过程，由此为电子商务和其他服务提供金融支持。
外源性感染是可以预防的。
患者男，60岁，左上、下后牙全部缺失，下颌缺牙区的牙槽嵴吸收严重成窄条状，拟可摘局部义齿修复。根据该患者下颌缺牙区的牙槽嵴情况排列人工牙，下列各项中不正确的是
()适用原产于世贸组织成员的进口货物，或原产于与我国签订有双边贸易协定的国家或地区的进口货物。
有下列()情形的人员，不得注册为投资主办人。I．被监管机构采取重大行政监管措施未满2年Ⅱ．未通过证券从业人员年检Ⅲ．尚处于法律法规规定或劳动合同约定的竞业禁止期内Ⅳ．已取得证券从业资格
以下关于文献法的观点哪一种是错误的?()
关于认知心理学的描述，以下哪项是不正确的?（）
无产阶级及其政党在统一战线中必须坚持的原则是
在表达式中，为了和数一般的数值数据区分，Access将文本型的数据用号括起来，在日期／时间型数据两端各加了一个()。

最新回复(0)

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

计算机408

学硕统考专业

在操作系统中，要对并发进程进行同步的原因是()。

虚拟页式存储管理中，CPU须具备必要的物理硬件的支持，而不是必需的单元是()。

下列有关I／O编址方式的描述中，正确的是()。

某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配(BestFit)算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是____。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

一台主机申请了一个到WWW．Abcedu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：由个人主机到本地DNS服务器查询是采用了什么方式?

关于DMA方式和通道方式，下列说法中错误的是()。

舍审公廨

网上支付以_______为基础，利用银行所支持的某种_______工具，实现从_______到_______、_______之间的在线_______、_______、_______、_______等过程，由此为电子商务和其他服务提供金融支持。

外源性感染是可以预防的。

患者男，60岁，左上、下后牙全部缺失，下颌缺牙区的牙槽嵴吸收严重成窄条状，拟可摘局部义齿修复。根据该患者下颌缺牙区的牙槽嵴情况排列人工牙，下列各项中不正确的是

()适用原产于世贸组织成员的进口货物，或原产于与我国签订有双边贸易协定的国家或地区的进口货物。

有下列()情形的人员，不得注册为投资主办人。I．被监管机构采取重大行政监管措施未满2年Ⅱ．未通过证券从业人员年检Ⅲ．尚处于法律法规规定或劳动合同约定的竞业禁止期内Ⅳ．已取得证券从业资格

以下关于文献法的观点哪一种是错误的?()

关于认知心理学的描述，以下哪项是不正确的?（）

无产阶级及其政党在统一战线中必须坚持的原则是

在表达式中，为了和数一般的数值数据区分，Access将文本型的数据用号括起来，在日期／时间型数据两端各加了一个()。

网上支付以___为基础，利用银行所支持的某种_工具，实现从_到_、_之间的在线_、_、_、_____等过程，由此为电子商务和其他服务提供金融支持。