首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找的平均查找长度为(72)。
admin
2009-05-15
59
问题
设顺序存储的某线性表共有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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
Projectschedulemanagementismadeupofsixmanagementprocessesincluding:activitydefinition,activitysequencing,______,
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示:项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成______任务。
软件的质量需求是软件需求的一部分,根据《软件工程产品质量第1部分:质量模型GB/T16260.1—2006)),软件产品质量需求的完整描述要包括______,以满足开发者、维护者、需方以及最终用户的需要。①内部质量的评估准则②外部质量的评估准则③使用质量
某信息系统项目采用结构化方法进行开发,按照项目经理的安排,项目成员小张绘制了下图。此时项目处于______阶段。
______体现了项目计划过程的正确顺序。A.范围计划—范围定义—活动定义—活动历时估算B.范围定义—范围规划—活动定义—活动排序—活动历时估算C.范围计划—范围定义—活动排序—活动定义—活动历时估算D.活动历时估算—范围规划—范围定义—活动定义—
以下关于工作分解结构的叙述,错误的是______。A.工作分解结构是项目各项计划和控制措施制订的基础和主要依据B.工作分解结构是面向可交付物的层次型结构C.工作分解结构可以不包括分包出去的工作D.工作分解结构能明确项目相关各方面的工作界面,便于责任
以下有关WebService技术的示例中,产品和语言对应关系正确的是______。A..NETFramework—CB.Delphi6—PascalC.WASP—C++D.GLUE—JAVA
甲、乙两个公司在项目实施过程中,对合同的生效时间产生了分歧。仲裁机构调查时发现以下事实:①双方签署的合同上并没有对合同的生效日期做出规定;②双方签署合同的过程如下:乙公司在拟定好合同文本并签署后以邮寄的方式寄给甲公司,信封上盖有乙公司所在地邮局3月18日的
现有两个用例UC1和UC2,其中UC2是一个完整的用例,可被实例化,而UC1需要UC2中的事件流才可被实例化,且UCl指定了使用UC2的精确位置,则UCl和UC2间的关系是“(105)”。
应用系统运行安全与保密的层次按照粒度从粗到细排序为()。
随机试题
简述学习现代管理学的具体方法。
肩胛骨前后位,中心线应对准
中药配伍相反意义是()
用塑料(丙烯聚合物)扁条(宽6mm)编结的缏条缝合的遮阳帽
某企业注册资本为3000万元,2015年按同期金融机构贷款利率从其关联方借款6800万元,发生借款利息680万元。该企业在计算企业所得税应纳税所得额时,准予扣除的利息金额为()万元。
社会主义初级阶段的起点是()。
(2011年河北.2)河北省河流众多,长度在18公里以上1000公里以下者就达300多条。境内河流大都发源或流经燕山、冀北山地和太行山山区,其下游有的合流入海,有的单独人海,还有因地形流入湖泊不外流者。主要河流从南到北依次有漳卫南运河、子牙河、大清河、永定
TheUnitedStatesCarriesOuttheNewBillWhenshegraduatesfromColumbiaUniversitynextyearwithamaster’sdegreeinp
A、 B、 C、 C
A、Tomakeasavingplan.B、Toopenabankaccount.C、Tosetclearinvestinggoals.D、Tomakeclearwhytoinvest.C
最新回复
(
0
)