类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素……这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集

admin2019-03-11 19

问题类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素……这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(53)，在最好情况下搜索失败的时间复杂度为(54)。

选项 A、O(logn)
B、O(nlogn)
C、O(log_kn)
D、O(nlog_kn)

答案C

解析与二分查找法类似，k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个节点的k叉树的深度为[log_kn(k+1)]+1，所以k分查找法在查找成功时和给定值进行比较的关键字个数至多为[log_kn)+1，即时间复杂度为　O(log_kn)。同时，k分查找法在查找不成功时，和给定值进行比较的关键字个数也至多为　[log_kn(k+1)]+1，即时间复杂度为O(log_kn)。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

某报文的长度是1000字节，利用MD5计算出来的报文摘要长度是(41)，利用SHA计算出来的报文摘要长度是(42)。(42)

城域以太网在各个用户以太网之间建立多点第二层连接，IEEE802．lah定义的运营商主干网桥协议提供的基本技术是在用户以太帧中再封装一层(26)，这种技术被称为(27)技术。(27)

ICMP协议属于因特网中的(19)协议，ICMP协议数据单元封装在(20)中传送。(19)

E1信道的数据速率是(16)，其中每个话音信道的数据速率是(17)。(16)

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(62)

一台电脑的本地连接设置如下图所示，结果发现不能ping通任何网络设备，该故障的原因是什么____________。

采用HDLC协议进行数据传输，帧0-7循环编号，当发送站发送了编号为0、1、2、3、4的5帧时，收到了对方应答帧REJ3，此时发送站应发送的后续3帧为(16)，若收到的对方应答帧为SREJ3，则发送站应发送的后续3帧为(17)。(16)

若一个项目由9个主要任务构成，其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数，该项目的关键路径是(1)，完成项日所需的最短时间是(2)天。(2008年下半年试题)(1)

若一个项目由9个主要任务构成，其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数，该项目的关键路径是(1)，完成项目所需的最短时间是(2)天。(1)

(2014年)关于孤立系统熵增原理，下述说法错误的是()。

建设项目管理的核心任务是()。

在季度报告的投资组合报告中，不需要披露基金资产组合的是()。

简单介绍音乐艺术作品的三个层次。

一只蚂蚁从正八面体一顶点爬到相对的顶点，最快用时2分钟，若蚂蚁爬行速度不变，则它从一个顶点爬到相邻的顶点最快用时为：

privateequity

Howlongdoesaninterviewusuallylastaccordingtothespeaker?

A、TomakeacomparisonbetweenDaveandotherfilms.B、TodiscusstheAmericans’ideasaboutthePresident.C、Totellreadersab

FixingaWorldThatFostersObesityEnvironmentFosteringObesityA)WhyareAmericansgettingfatterandfatter?Thesimpleexpl