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

admin2009-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₂(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)。

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

软考中级

某企业经过多年的发展，在产品研发、集成电路设计等方面取得了丰硕成果，积累了大量知识财富，______不属于该企业的知识产权范畴。

以下网络存储模式中，真正实现即插即用的是______。

项目实施过程中，围绕对项目质量的监控、追踪管理，以下做法不正确的是______。

在系统建设后期，建设方考虑到系统运维管理问题，希望增加8课时的IT服务管理方面的知识培训，承建方依此要求进行了范围变更。在对范围变更进行验证时，验证准则是______。

______不属于制订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岁。农民，患者发热恶寒，咳嗽，咳白黏痰，痰量由少渐多，胸痛剧烈，呼吸不利，苔薄黄，脉浮滑数。其治法是

营养大腿诸肌的主要血管是

构成招标采购服务项目费用的最主要部分是()。

根据《全国年节及纪念日放假办法》，()不是全体公民放假的节日。

下列各项中，不能记入“销售费用”的是()。

四棱锥P—ABClD底面为正方形，侧面PAD为等边三角形，且侧面PAD上底面ABCD，点M在底面正方形ABCD内运动，且满足MP=MC，则点M在正方形ABCD内的轨迹一定是()．

人民检察院依法对公安机关的侦查活动是否合法实行监督，主要内容是发现和纠正下列违法行为()。