首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
类比二分搜索算法,设计A分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,...,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得
admin
2005-03-15
120
问题
类比二分搜索算法,设计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
软件设计师上午基础知识考试
软考中级
相关试题推荐
如何根据网络流量选择联网设备,给出所选设备的作用?在我国,目前可供选择大的用户选择的接入方式有哪些,各自的接入速率为多少?
在OSI参考模型有哪几层?Windows组网中采用什么工具来实现域的创建和管理?在什么情况下需要设置“主域”?
为了实现VLAN1、VLAN2和VLAN3的虚拟网络划分,在ATM和RT路由器中应设置哪几种服务协议(如BUS)?试述从PC,发送一个IP包到PC4数据封装与解封的整个过程。
阅读以下说明,回答问题。(2011年上半年下午试题四)[说明]某公司两分支机构之间的网络配置如图3-11所示。为保护通信安全,在路由器router-a和router-b上配置IPSec安全策略,对192.168.8.0/24网段和192.168.
阅读下列说明,回答问题,将解答填入对应栏内。【说明】图2—1是某企业网络拓扑,网络区域分为办公区域、服务器区域和数据区域,线上商城系统为公司提供产品在线销售服务。公司网络保障部负责员工办公电脑和线上商城的技术支持和保障工作。图2-1中,存储域网络
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
如果两个交换机之间设置多条Trunk,则需要用不同的端口权值或路径费用来进行负载均衡。默认情况下,端口的权值是(55)。在如下图所示的配置下,(56)。
某开发人员不顾企业有关保守商业秘密的要求,将其参与该企业开发设计的应用软件的核心程序设计技巧和算法通过论文向社会发表,那么该开发人员的行为(8)。
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
随机试题
内地居民同香港居民、澳门居民、台湾居民、华侨在中国内地自愿离婚的,当事人有下列哪些情形的,婚姻登记机关不予受理?()
错误选项为:C;正确写法为:VESSEL:GLORIAV.123DATEDAPRIL30,2004根据UCP600第20条,当提单上显示从起运港的船只是预期(INTENDED)船时,即使预期船只与实际装运船只一致,提单的装船批注(ONBOARD
对于商用房贷款抵押物,以下说法错误的是()。
以下关于可转换债券的说法中,正确的有()。(2004年)
材料:初二(3)班的汤老师在辅导学生上晚自习时因私事偷偷外出,快放学的时候才回来。他回来时发现小李正在偷偷写情书,为了让其他同学引以为戒,汤老师将小李的情书在班上念了出来,引得全班哄堂大笑。小李觉得没面子,请假回家休息了。班上的小敏喜欢
某次考试有一道多项选择题,共有A、B、C三个选项。参加考试的人中,共有20人选了A,15人选了B,10人选了C。其中选了两个选项的有5人,选了三个选项的有3人,还有2人未答此题。问有多少人参加考试?
马斯洛的需要层次理论中的最高层次是()。
Ayoungmangoingtojointhearmy(军队)andhadto【C1】________amedicalexamination.Thedoctorwassittingatadeskwhenhec
Whatrecommendationsdoesthetutormakeaboutthereferencebooks?AAllBResearchmethodCMainBodyDConclusionE
Tobereallyhappyandreallysafe,oneoughttohaveatleasttwoorthreehobbies,andtheymustallbereal.Itdoesn’tmatte
最新回复
(
0
)