设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为(72)。

admin2009-05-15 58

问题设顺序存储的某线性表共有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₂(b+1)-1+(s+1)/2≈log₂(n/s+1)+s/2；如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2＝(b+1)/2+(s+1)/2＝(s²+2s+n)/(2s)。在本题中，n=123，b=3，s=41，因此平均查找长度为(41×41+2×41+123)/(2×41)＝23。

转载请注明原文地址:https://kaotiyun.com/show/bsTZ777K

本试题收录于：数据库系统工程师上午基础知识考试题库软考中级分类

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为(72)。

数据库系统工程师上午基础知识考试

软考中级

IEEE802系列规范、TCP协议、MPEG协议分别工作在______。

某OA系统处于试运行阶段，用户反映不能登录，承建方现场工程师需要对导致该问题的各种原因进行系统分析，使用______工具比较合适。

某园区的综合布线系统中专门包含一个子系统用于将终端设备连接到信息插座，包括装配软线、连接器和连接所需的扩展软线。根据EIA/TIA-568A综合布线国际标准，该子系统是综合布线系统中的______。

根据《软件文档管理指南GB/T16680—1996))的要求，有关正式组织需求文档的评审，不正确的是______。

近年来，电子商务在我国得到了快速发展，很多网站使企业能够通过互联网直接向消费者销售产品和提供服务。从电子商务类型来说，这种模式属于______模式。A．B2BB．B2CC．C2CD．G2B

在UML提供的图中，(101)用于描述系统与外部系统及用户之间的交互；(102)用于按时间顺序描述对象间的交互。(102)

成本基准是用来度量与检测项目成本绩效的按时间分段预算。下图中给出了某项目期望现金流、成本基准、资金需求情况。图中区间A应为(57)。

行政处罚的原则包括（）。

McDonald’sistheworldsinglebiggestfoodproviderwithannualsalesofaround$12.4bn.Andthecompany’ssymbolRonaldMcDona

进出口货物的完税价格，由海关以该货物的__________为基础审查确定。

在计算长期资金的个别成本时，如果证券发行成本忽略不计，那么留存收益成本等于()。

根据下列资料，回答问题2015年1—4月，民间固定资产投资为()亿元。

下列不属于民事诉讼法中表述的诉讼参与人的是()。

第三次科技革命

曲线y=x2+2lnx在其拐点处的切线方程是________．

利用程序模拟脱机输入输出时外围控制机的功能，在主机的直接控制下实现脱机的输入输出功能，此时外围操作与CPU对数据的处理同时进行，这种技术称为()。