首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
admin
2021-01-13
49
问题
设顺序存储的某线性表共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在某些系统中,存在非常复杂的对象,可以采用循序渐进的方式进行组合,将小对象组合成复杂的大对象。以下实例展示了Builder(生成器)模式。该实例用来建立“文件”,文件内容包
阅读下列说明C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一
现欲开发一个软件系统,要求能够同时支持多种不同的数据库,为此采用抽象工厂模式设计该系统。以SQLSerVer和Access两种数据库以及系统中的数据库表Depanment为例,其类图如图17—3所示。[Java代码]importjava.util
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某企业拟构建一个高效、低成本、符合企业实际发展需要的办公自动化系统。工程师小李主要承担该系统的公告管理和消息管理模块的研发工作。公告管理模块的主要功能包括添加、修改、删除和查
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
(2012年下半年下午试题一)阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下。(1)加入购物车。顾客浏览商品,点击加入购物车,
定义了三种模型来描述系统。(49)可以用状态图来表示;(50)可以用数据流图来表示。(51)为上述两种模型提供了基本的框架。
在RS-232C接口信号中,数据终端就绪信号的连接方向为(61)。
The most accurate and most boring way to(66)Java is that it is a new computer programming language developed by Sun Microsystems
随机试题
ThenumberofspeakersofEnglishinShakespeare’stimeisestimatedtohavebeenaboutfivemillion.Todayitisestimatedthat
条件必需氨基酸
肝炎性假瘤的CT表现缺乏特异性,以下增强表现正确的是
A.4~6cm2B.≤2.0cm2C.≤1.5cm2D.≤1.0cm2E.≤0.5cm2中度二尖瓣狭窄时瓣膜口面积为
下列内容中,属于监理股份有限公司特点的是( )。
证券公司的定向资产管理业务中发生关联交易的,应当采取措施包括()。I.事先将相关信息以书面形式通知客户,要求客户在指定期限内答复Ⅱ.事先将相关信息以书面形式通知资产托管机构Ⅲ.定向资产管理合同应当明确约定关联交易的通知和答复程序Ⅳ.客户未同
以证券交易为中心,有组织机构和人员,有专门设施的交易市场是()。
在追究行为人的法律责任时,应当进行成本收益分析,讲求法律责任的效益。()
Itisabouttimethatsuchpractices
A、DragshavecausedAmericanpeopletohavenoenoughdragsofmedicaluse.B、DrugshaveminedmanyAmericanpeople’smind.C、Dr
最新回复
(
0
)