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

admin2019-03-11 31

问题类比二分搜索算法，设计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://www.kaotiyun.com/show/BvRZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

若某文件系统的目录结构如图1-2所示，假设用户要访问文件f1.java，且当前工作目录为Program，则该文件的全文件名为(8)，其相对路径为(9)。 (9)

网络设计过程包括逻辑网络设计和物理网络设计两个阶段，各个阶段都要产生相应的文档。下面的选项中，属于逻辑网络设计文档的是(1)，属于物理网络设计文档的是(2)。(1)

为了解决伴随RIP协议的路由环路问题，可以采用水平分割法，这种方法的核心是(1)，而反向毒化方法则是(2)。(1)

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

结构化布线系统分为六个子系统，其中水平子系统的作用是(67)，园区子系统的作用是(68)。(67)

IPv6的可聚合全球单播地址前缀为(59)，任意播地址的组成是(60)。(60)

在异步通信中，每个字符包括1位起始位、7位数据位、1位奇偶校验位和1位终止位，每秒钟传送100个字符，则有效数据速率为__________。(2008年下半年试题)

边界网关协议BGP的报文(22)传送。一个外部路由器通过发送(23)报文与另一个外部路由器建立邻居关系，如果得到应答，才能周期性地交换路由信息。（23）

被告改变原行政行为，原告不撤诉，人民法院经审查认为原行政行为违法的，应当作出确认其违法的判决；认为原行政行为合法的，应当判决驳回原告的诉讼请求（）

亚硫酸氢钠作为抗氧剂，通常用于()

呕吐清水痰涎，胃脘有振水声者，为吐血鲜红或紫暗有块，挟有食物残渣者，属

下列各项中，不属于行针辅助手法的是

A．1年B．2年C．3年D．5年根据《麻醉药品和精神药品管理条例》印鉴卡的有效期是()。

某企业全年制度工作日为250天，两班制，每班有效工作时间为7．5小时。已知钳工车间生产面积为145平方米，每件产品占用生产面积5平方米，该车间单件产品时间定额为1．5小时。该钳工车间的年生产能力为()件。

“朝鲜”的原意是()。

天京变乱

简述班杜拉的自我效能感理论及其意义。