首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
admin
2009-05-15
60
问题
设顺序存储的某线性表共有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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某企业经过多年的发展,在产品研发、集成电路设计等方面取得了丰硕成果,积累了大量知识财富,______不属于该企业的知识产权范畴。
以下网络存储模式中,真正实现即插即用的是______。
项目实施过程中,围绕对项目质量的监控、追踪管理,以下做法不正确的是______。
在系统建设后期,建设方考虑到系统运维管理问题,希望增加8课时的IT服务管理方面的知识培训,承建方依此要求进行了范围变更。在对范围变更进行验证时,验证准则是______。
某单位的公共服务大厅为客户提供信息检索服务并办理相关行政审批事项,其信息系统运行中断将造成重大经济损失并引起服务大厅严重的秩序混乱。根据《电子信息系统机房设计规范GB50174—2008)),该单位的电子信息系统机房的设计应该按照______机房进行设计
以下关于项目可行性研究内容的叙述,______是不正确的。A.技术可行性是从项目实施的技术角度,合理设计技术方案,并进行评审和评价B.经济可行性主要是从资源配置的角度衡量项目的价值,从项目的投资及所产生的经济效益进行分析C.可行性研究不涉及合同责任、
______不属于制订WBS过程的功能。A.为提高项目成本、活动历时估算和资源估算的准确度建立的基础B.定义绩效考核和控制的基准C.形成清晰的职责任命D.建立项目经理和项目干系人之间的沟通网络
2005年12月,ISO正式发布了①作为IT服务管理的国际标准;2007年10月,ITU接纳②为3G标准;2005年10月,ISO正式发布了③作为信息安全管理的国际标准。①、②和③分别是______。A.①ISO27000②IEEE802.16③
在UML提供的图中,(101)用于描述系统与外部系统及用户之间的交互;(102)用于按时间顺序描述对象间的交互。(101)
煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连,位置如下图所示,结点代表各住宅楼和主管道位置,线上数字代表两节点间距离(单位:百米)。则煤气公司铺设的管道总长最短为()米。
随机试题
患者张某,男性,28岁。农民,患者发热恶寒,咳嗽,咳白黏痰,痰量由少渐多,胸痛剧烈,呼吸不利,苔薄黄,脉浮滑数。其治法是
营养大腿诸肌的主要血管是
构成招标采购服务项目费用的最主要部分是()。
根据《全国年节及纪念日放假办法》,()不是全体公民放假的节日。
下列各项中,不能记入“销售费用”的是()。
甲公司为生产加工企业,其在20×6年度发生了以下与股权投资相关的交易: (1)甲公司在若干年前参与设立了乙公司并持有其30%的股权,将乙公司作为联营企业,采用权益法核算。20×6年1月1日,甲公司自A公司(非关联方)购买了乙公司60%的股权并取得了控制
四棱锥P—ABClD底面为正方形,侧面PAD为等边三角形,且侧面PAD上底面ABCD,点M在底面正方形ABCD内运动,且满足MP=MC,则点M在正方形ABCD内的轨迹一定是().
实现中华民族伟大复兴的中国梦,反映了近代以来一代又一代中国人的美好夙愿,进一步揭示了中华民族的历史命运和当代中国的发展走向,指明了全党全国各族人民共同的奋斗目标。习近平总书记指出:“实现中国梦必须走中国道路、弘扬中国精神、凝聚中国力量。”这些从根本上讲就是
人民检察院依法对公安机关的侦查活动是否合法实行监督,主要内容是发现和纠正下列违法行为()。
给定资料1.2016年4月19日,中共中央总书记、国家主席、中央军委主席、中央网络安全和信息化领导小组组长习近平主持召开网络安全和信息化工作座谈会,深刻回答了事关中国网信事业长远发展的一系列重大问题,科学描绘了中国建设网络强国的宏伟蓝图和实践路径
最新回复
(
0
)