首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
admin
2005-03-15
126
问题
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得到的集合上进行k分搜索;如此进行,直到找到要搜索的元素或搜索失败。此A分搜索算法在最坏情况下搜索成功的时间复杂度为(1),在最好情况下搜索失败的时间复杂度为(2)。
选项
A、O(logn)
B、O(nlogn)
C、O(log
k
n)
D、O(nlog
k
n)
答案
C
解析
与二分法查找类似,k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键个数最多不超过树的深度,而具有n个结点的k叉树的深度为[log
k
n(k+1)]+ 1,所以,k叉查找法在查找成功时和给定值进行比较的关键字个数至多为[log
k
n]+1,即时间复杂度为O(log
k
n)。同时,k分查找法在杳找不成功时,与给定值进行比较的关键字个数也至多为[log
k
n(k+1)]+1,即时间复杂度为O(log
k
n)。
转载请注明原文地址:https://kaotiyun.com/show/woxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
通常VLAN有哪两种实现方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪3种模式划入VLAN中,并简述它们的含义。
如图4所示,GSW为千兆以太网交换机,内设ATM模块。SW1为100M/1000Mbit/s以太网交换机,SW2为ATM/100Mbit/s以大网交换机,RT为中心路由器;S1和S2为服务器,分别经千兆以太网卡和155Mbit/sATM网卡与GSW(千兆以
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?限制制MailUser邮件主机里每个用户邮箱里所能存放的最多邮件数量不超过30个,如何配置?
阅读以下说明,回答问题1~3,将解答填入对应的解答栏内。某公司的分支机构通过一条DDN专线接入到公司总部,地址分配和拓扑结构如图5-1所示。在两台路由器之间可以使用静态路由,也可以使用动态路由。下面是公司总部的路由器R2的配置命令列表,在
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(13)
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
某公司网络结构如图3-9所示,通过在路由器上配置访问控制列表ACL来提高内部网络和Web服务器的安全。(2011年下半年下午试题四)请说明下面这组ACL语句的功能。Routerfconfig)#access-list101permit
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
TheSimpleNetworkManagementProtocol(SNMP)isan(71)protocolthatfacilitatestheexchangeofmanagementinformationbetween(7
随机试题
胸段椎管的横断面呈_______________形,胸段脊髓的横断面呈_______________形,在第12胸椎处形成_______________,然后迅速缩小为_______________。
患者女,26岁。孕37周,因“鼻塞2个月,间断血涕3天”就诊。体检发现患者双上颈多个肿大淋巴结,最大径约3cm,行直接鼻咽镜检查发现右侧鼻咽咽隐窝消失,局部可见菜花样新生物,活检证实为鼻咽低分化鳞癌。患者诉近几天颈部肿块增大明显,鼻塞症状加重,关于下一
按照《处方管理办法(试行)》文件,处方是医师为患者开具的一种
某上市公司董事吴某,持有该公司6%的股份。吴某将其持有的该公司股票在买人后的第5个月卖出,获利600万元。关于此收益,下列哪些选项是正确的?
题中的风险属于施工管理风险类型中的()。根据《中华人民共和国建筑法》的有关规定,工程监理人员认为:厂程施工不符合工程设计要求、施工技术标准和合同约定的,有权()。
教育史上,“产婆术”的提出者是()。
“1966年5月至1976年10月的‘文化大革命’,使党、国家和人民遭到建国以来最严重的挫折和损失。”然而。尽管经历过这样的曲折,党和国家在这“十年浩劫”中仍取得了一些重大成就,下列成就是在“文化大革命”期间取得的有
系统软件开发的原型化方法是一种有效的开发方法,下述基本环节中哪一个是原型形成以后才应实施的内容?
A、Thesametoyou.B、Youdo,too.C、Thesameasyou.D、Youhaveit,too.A“Haveaniceweekend!”即“祝你度过一个愉快的周末!”是常用的祝福语。A选项“Thes
Asusedinthefirstparagraphofthepassage,theword"motivate"mostprobablymeans______.What’sthemainideaofasucce
最新回复
(
0
)