首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
admin
2021-01-13
79
问题
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
选项
A、21
B、23
C、41
D、62
答案
B
解析
分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表R[1,...,n]均分为b块,前 b-1块中结点个数为s=[n/b],第b块的结点数允许小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是分块有序的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1,...,b),即ID
(1≤ i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。分块查找的基本思想是:索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。由于块内无序,只能用顺序查找。分块查找是2次查找过程。整个查找过程的平均查找长度是2次查找的平均查找长度之和。如果以二分查找来确定块,则分块查找成功时的平均查找长度为ASL1=log
2
(b+1)-1+(s+1)/2≈log
2
(n/s+1)+s/2;如果以顺序查找确定块,分块查找成功时的平均查找长度为ASL2=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)。在本题中,n=123,b=3,s=41,因此平均查找长度为(41×41+2×41+123)/(2×41)=23。
转载请注明原文地址:https://kaotiyun.com/show/mtCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】一个新的音像商店准备向比较广泛的人群出租录像带和光碟。该商店的管理决定在计算机系统的支持下来运作。音像商店在货架上存放着题材广泛的当前流行的电影库。由于同一个电影片名可能有于不同
阅读下列说明和数据流图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某供销系统接受顾客的订货单,当库存中某配件的数量小于订购量或库存量低于一定数量时,向供应商发出采货单;当某配件的库存量大于或等于订购量时,或者收到供应商的送货单时并更新了库
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求,欲构建数据管理中间件,其主要功能如下:(1)数据管理员可通过中间件进行用户管理、操作管理和权限管理。
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下:(1)加入购物车。顾客浏览商品,点击加入购物车,根据商品标识从商品表中读取商品信息,并更新购物车表。
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m
现欲开发一个软件系统,要求能够同时支持多种不同的数据库,为此采用抽象工厂模式设计该系统。以SQLSerVer和Access两种数据库以及系统中的数据库表Depanment为例,其类图如图17—3所示。[Java代码]importjava.util
某汽车停车场欲建立一个信息系统,已经调查到的需求如下:(1)在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器,示意图如图14-10所示。(2)当汽车到达入口时,驾驶员按下停车卡打印机的按钮获取
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg
若对象A可以给对象B发送消息,那么(48)。
设集合Z26={0,1,…,25),乘法密码的加密函数为Ek:Z26→Z26,Ek(i)=(ki)mod 26,密钥k∈Z26-{0},则加密函数E7(i)=(7i)mod 26是一个(56)函数。
随机试题
重新点燃启蒙的火炬在告别20世纪而进入21世纪之际,中国思想界对启蒙有截然相反的看法。有人历数启蒙的罪状,劝告知识分子放弃启蒙立场;有人则回顾启蒙被压倒的悲剧,希望在中国“重新点燃启蒙的火炬”。面对思想界的矛盾和种种困惑,有一个问题必须回答:今日
静脉肾盂造影对以下哪种疾病最有诊断价值
前置胎盘的处理,以下哪项错误
根据供求总量和结构的关系以及总需求和总供给在国民经济运行中的不同特点,短期应以需求调节为主,中长期应以供给调节为主。其原因正确的有()。
对列入“实施检验检疫的进出境商品目录”和其他法律、法规规定必须经检验检疫机构检验的出口商品的运输包装,进行性能检验,未经检验或检验不合格的,不准用于盛装出口商品。()
在计算披露的经济增加值时,涉及的会计调整很多,其中经济增加值要求对某些大量使用长期机器设备的公司,处理方法是按照更接近经济现实的()。
甲:“你认为电视剧《心术》演得好吗?”乙:“我认为不算好。”甲:“那就是说,你认为坏了?”乙:“不,我并没有说坏。”甲:“说不好就是坏!”以下哪个选项不可能是对甲、乙对话的正确评价?
民革上海市委长期关注公共财政问题,曾以此为题连续两年在市政协全会上作大会发言。“财政预算科目分‘类、款、项、目、节’五个层次,但目前政府向人大代表提交的财政信息大多是到‘款’,有的仅仅为‘类’,人大代表要在全会会期内,全面厘清这些款项并不容易。”
MBA
Researcherswhorefusetosharedatawithothersmay【51】otherstowithholdresultsfromthem,【52】astudybyhealth-policyanalys
最新回复
(
0
)