首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为______。
admin
2021-01-13
54
问题
设顺序存储的某线性表共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在某些系统中,存在非常复杂的对象,可以采用循序渐进的方式进行组合将小对象组合,成复杂的对象。以下实例展示了Builder(生成器)模式。该实例用来建立“文件”,文件内容包括
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某学校拟开发一套实验管理系统,对各课程的实验安排情况进行管理。【需求分析】一个实验室可进行多种类型不同的实验。由于实验室和实验员资源有限,需根据学生人数分批次安排实验室和实验
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】计算两个字符串x和y的最长公共子串(LongestCommonSubstring)。假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
当在软件工程的环境中考虑风险时,主要基于Charette提出的3个概念。以下选项中不属于这3个概念的是(1)。项目风险关系项目计划的成败,(2)关系着软件的生存能力。在进行软件工程风险分析时,项目管理人员要进行4种风险评估活动,这4种活动分别是(3)以及确
某一确定有限自动机(DFA)的状态转换图如下图所示,该DFA接受的字符串集是(28),与之等价的正规式是(29)。
设集合A={{1,2,3},{4,5},{6,7,8}},则下式为真的是(19),设A:{1,2},B={a,L,c},C={c,d},则Ax(B∩C)=(20)。
大学生王某,对某办公软件的技术保护措施进行解密,并将其解密后的版本制作成光盘,在中关村电子市场进行销售,破坏正常的市场秩序,损害广大消费者利益,王某的法律责任应当(21)。
王某买了一幅美术作品原件,则他享有该美术作品的_______。
随机试题
能产生LTA的细菌是
管电压在摄影条件选择中的意义,错误的是
保管特殊类型药材必须具有
在公共场所附近开挖沟槽时,应设防护设施,夜间设置照明灯和警示红灯。()
在某些情况下,被保险人患病或遭受意外伤害,最终是否残疾在短期内难以判定,为此保险公司规定一个定残期限,过了该期限后仍无明显好转征兆的,认定为全残。这种情况称为( )。
立面图的绘制中整个建筑的外轮廓尺寸线用( )线绘制。
信用风险管理委员会或类似机构可以考虑重新设定/调整限额的情况有()。
饮水时,应注意遵循少次多量的原则。
把对集体与个人的管理结合起来的班级管理是()。
A、Thecablecarride.B、GoldenGatePark.C、Fisherman’sWharf.D、Busesandstreetcars.A男士问女士最喜欢旧金山的什么,女士回答:“我也不知道,这很难说。我喜欢金门大桥
最新回复
(
0
)