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

admin2009-05-15 82

问题设顺序存储的某线性表共有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)。

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

软考中级

软件测试工具也是测试设备的一种。以下关于软件测试工具的叙述，正确的是______。

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

数据仓库解决方案常常用来实现______。A．两个或者多个信息系统之间相互访问数据资源B．企业海量数据的存储和访问C．企业决策信息的挖掘和提取D．不同地域的企业信息系统之间进行实时的信息共享和数据通信

综合布线系统是楼宇和园区范围内，在统一的传输介质上建立的可以连接电话、计算机、会议电视和监控电视等设备的结构化信息传输系统。根据EIA/TIA-568A标准，______中列出的各项全部属于综合布线系统的子系统。

()提供项目组织安排的层次化的、有组织的描述，使得工作包与组织执行单元相关联，用于显示各个工作元素被分配到哪个组织单元。

对于一棵非空二叉树，若先访问根节点的每一棵子树，然后再访问根节点的方式通常称为________。

多项目集成管理中，采用项目群管理方式有利于()

投保人办理建筑意外伤害保险的投保手续后，应将投保有关信息以()的方式告诉被保险人。

建设工程项目总概算是确定整个建设工程项目从筹建开始到竣工验收、交付使用所需的全部费用的文件，它是由()等汇总编制而成。

甲30岁，因患精神疾病完全丧失辨识能力。由下列有监护能力的人按顺序担任甲的监护人，则排在首位的是()。

下列税金中，应计入存货成本的有()。

在确定最佳现金持有量时，成本分析模式、存货模式和随机模式均需考虑的因素是()。

高温津贴是针对高温条件下从事经济建设和企业生产经营活动的职工发放的特殊工资性补偿。根据上述定义，下列属于高温津贴的是()。

口头调查又称为（）。

胎儿一开始就具备一定的差异。麦克法内尼通过胎儿对噪声的反应，将其分为()

Exercise,everyoneadvises!Butimmediately,whenyoutry,yourunintotrouble.61)Thereissomuchcontradictory,sometimesi