首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
admin
2009-05-15
88
问题
设顺序存储的某线性表共有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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
以下关于项目沟通原则的叙述中,______是不正确的。
某商业银行在A地新增一家机构,根据《计算机信息安全保护等级划分准则》,其新成立机构的信息安全保护等级属于______。
某公司打算经销一种商品,进价为450元/件,售价500元/件。若进货商品一周内售不完,则每件损失50元。假定根据已往统计资料估计,每周最多销售4件,并且每周需求量分别为0、1、2、3和4件的统计概率如下表所示:则公司每周进货______件可使利润最高。
软件的质量需求是软件需求的一部分,根据《软件工程产品质量第1部分:质量模型GB/T16260.1—2006)),软件产品质量需求的完整描述要包括______,以满足开发者、维护者、需方以及最终用户的需要。①内部质量的评估准则②外部质量的评估准则③使用质量
关于网络安全服务的叙述中,______是错误的。A.应提供访问控制服务以防止用户否认已接收的信息B.应提供认证服务以保证用户身份的真实性C.应提供数据完整性服务以防止信息在传输过程中被删除D.应提供保密性服务以防止传输的数据被截获或篡改
某业务员需要在出差期间能够访问公司局域网中的数据,与局域网中的其他机器进行通信,并且保障通信的机密性。但是为了安全,公司禁止Internet上的机器随意访问公司局域网。虚拟专用网使用______协议可以解决这一需求。A.PPTPB.RC-5C.UDP
______体现了项目计划过程的正确顺序。A.范围计划—范围定义—活动定义—活动历时估算B.范围定义—范围规划—活动定义—活动排序—活动历时估算C.范围计划—范围定义—活动排序—活动定义—活动历时估算D.活动历时估算—范围规划—范围定义—活动定义—
某系统集成企业为做好项目风险管理,给风险定义了3个参数:(1)风险严重性:指风险对项目造成的危害程度:(2)风险可能性:指风险发生的几率;(3)风险系数:是风险严重性和风险可能性的乘积。其中,对项目进度延误、费用超支的风险严重性等级和风险可能性等级如下表所
决策树分析法通常用决策树图表进行分析,根据下表的决策树分析法计算,图中机会节点的预期收益EMV分别是90和(272)(单位:万元)。
制造某产品需要四道工序,每道工序可选用多种方法。下图列出了制造这种产品各道工序可选用的不同方法:从结点1开始,连续经过4条线段(表示4道工序所选用的方法),组成一条线路,直到结点12结束。每条线段上标记的数字表示利用相应方法每件产品可以获得的利润(元)。企
随机试题
热证形成的主要原因是()(2009年第137题)
下列有关专家参与反垄断诉讼的表述中,正确的是()。
当你需要传递一条信息时,从理解到接受阶段可能发生的障碍是
简述代位继承与转继承的区别。
金合金全冠抛光所用抛光剂是
下列关于无形资产会计处理的表述中,正确的是()。
LetterofCreditisissuedbythe()forimporterbenefits.
截至今年5月12日,全国电影票房超过81亿元,其中,中国产影片市场份额达到63%,而去年同期仅为34%。吴冠平指出:《致我们终将逝去的青春》《北京遇上西雅图》等国产电影有自己独特的文化吸引力,这是其魅力所在。目前,基于本土文化的国产电影已经取得了不错的成绩
设n维行向量α=,A=E-ααT,B=E+2αTα,则AB为().
TheHypertextTransferProtocol,theWeb’s(1)protocol,isattheheartoftheWeB.HTTPisimplementedintwoprograms:a(2)program
最新回复
(
0
)