首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
admin
2009-05-15
38
问题
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
选项
A、21
B、23
C、41
D、62
答案
B
解析
分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表R[1,…,n]均分为b块,前 b-1块中结点个数为s=[n/b],第b块的结点数允许小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是分块有序的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1,…,b],ID[I](1≤i≤b)中存放第i块的最大关键字及该块在表只中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。分块查找的基本思想是:索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。由于块内无序,只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。如果以二分查找来确定块,则分块查找成功时的平均查找长度为ASL1=log
2
(b+1)-1+(s+1)/2≈log
2
(n/s+1)+s/2;如果以顺序查找确定块,分块查找成功时的平均查找长度为ASL2=(b+1)/2+(s+1)/2=(s
2
+2s+n)/(2s)。在本题中,n=123,b=3,s=41,因此平均查找长度为(41×41+2×41+123)/(2×41)=23。
转载请注明原文地址:https://kaotiyun.com/show/bsTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
通过建设学习型组织使员工顺利地进行知识交流,是知识学习与共享的有效方法。以下关于学习型组织的描述,正确的包括______。①学习型组织有利于集中组织资源完成知识的商品化②学习型组织有利于开发组织员工的团队合作精神③建设金字塔型的组织结构有利于构建学习型组织
在Windows操作系统平台上采用通用硬件设备和软件开发工具搭建的电子商务信息系统宜采用______作为信息安全系统架构。
UML是面向对象开发方法的标准化建模语言。采用UML对系统建模时,用______模型描述系统的功能,等价于传统的系统功能说明。A.分析B.设计C.用例D.实现
项目范围说明书(初步)列出了项目及其相关产品、服务的特性和______及范围控制和接受的方法。A.章程B.高层范围控制过程C.质量控制方法D.项目边界
投资大、建设周期长、专业复杂、技术人员来自多个部门的大型项目,最好采用______组织形式或近似的组织形式。
用户数据报(UDP)协议是互联网传输层的协议之一。下面的应用层协议或应用软件使用UDP协议的是________。
决策树分析法通常用决策树图表进行分析,根据下表的决策树分析法计算,图中机会节点的预期收益EMV分别是90和(272)(单位:万元)。
在编制WBS时,应考虑以下_________基本原则。①每个WBS元素都代表一个独立的、有形或无形的可交付成果②可交付成果中包括最终可交付物和为实现最终结果所需要的中间可交付物③每个WBS元素应只从属一个母层次的WBS元素或子层次的WBS元素④每个
(2008上项管)下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计____(1)公里的公路,这种总公里数最少的改造方案共有____(2)个。(2)
对于一棵非空二叉树,若先访问根节点的每一棵子树,然后再访问根节点的方式通常称为________。
随机试题
简述牛头刨床加工表面粗糙度值增大的原因。
市场营销管理的实质是()
市场机制是一个有机整体,主要包括_________、_________、_________。
简述计算企业所得税额时不可扣除的支出。
哪类微生物对化学消毒剂最敏感
某制药企业为扩大经营规模,准备将位于W市城区的老工厂迁出。根据当地政府规定,老厂区土地由政府按一定价格收购后,重新开发利用。该企业拟用政府收购老厂区的补偿价格在郊区工业开发区购置土地,建设新的现代化制药厂。经调查,该企业老厂区土地为1987年以无偿划拔方式
根据我国《建筑法》的规定,()工程,可以由两个以上的承包单位联合共同承包。
旅游团队在境外遇到突发事件的,由()提交总结报告。
1880年7月,_________等赴彼得堡与俄国谈判,于1881年2月在彼得堡签订了中俄________,此后根据此条约签订的_________等几个边界议定书,沙俄共割占了中国斋桑湖东北、霍尔果斯河以西等地7万多平方公里的土地。清政府收回伊犁后,于__
Whoisspeaking?
最新回复
(
0
)