首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
admin
2005-03-15
63
问题
类比二分搜索算法,设计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
软件设计师上午基础知识考试
软考中级
相关试题推荐
目前,国内短消息服务平台按照接入方式主要可分为哪两种?请简要说出网关服务器与短消息服务过程。
阅读以下有关传统局域网络运行和维护的叙述,将应填入(n)处的字句写在对应栏内。在对网络运行及维护前首先要了解网络,包括识别网络对象的硬件情况、判别局域网的拓扑结构和信道访问方式、确定网络互联以及用户负载等。常见的3种拓扑结构是星形、(1)与(2)拓扑结
图中(a)、(b)、(c)、(d)为不同类型IPSee数据包的示意图,其中(1)和(2)工作在隧道模式;(3)和(4)支持报文加密。R2与Rl之间采用预共享密钥“12345678”建立IPSec安全关联,请完成下面配置命令。Rl(eonfig)#c
阅读以下说明,回答问题1~7,将解答填入对应的解答栏内。图3-1是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口
根据该网络的需求,防火墙至少需要(14)个百兆接口和(15)个千兆接口。(14)
【说明】某单位网络结构如下图所示,其中维护部通过DDN专线远程与总部互通。根据网络拓扑和需求说明,完成汇聚交换机Switch2的部分配置。Switch2(config)#interfacefastEthernet0/0Swi
Packet-switchingwirelessnetworksarepreferable(66)whentransmissionsare(67)bemuseofthewaychargesare(68)perpacket.Circ
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
X.509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者,它(2);(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(1)
随机试题
与慢波睡眠有关的主要神经递质是
图象后处理技术与CT图象重建的本质区别是
图示桁架在竖向外力P作用下的零杆根数为()。
用扣件式钢管脚手架作为支架立柱,且支架立柱为群柱架,其高宽比不应()。
根据《房屋建筑与装饰工程工程量计算规范》(GB50854—2013),措施项目中安全文明施工的“四口”有()。
按管道的设计压力分类,管道分为()
中国古代实行君主专制,古代希腊雅典实行民主政治,古代东西方实行不同的政治制度,主要是由于()。
(2015年真题)下列关于我国司法制度的表述,正确的是()。
在考生文件夹下有一个数据库文件“samp2.accdb”,里面已经设计好了两个表对象“tNorm”和“tStock”。请按以下要求完成设计。创建一个查询,查找库存数量在合理范围([最低储备,最高储备])的产品,并显示“产品名称”和“库存数量”。所建查询
LANDUSEAproblemrelatedtothecompetitionforlanduseiswhethercropsshouldbeusedtoproducefoodorfuel.【1】_____
最新回复
(
0
)