分块检索中，若索引表和各块内均用顺序查找，则有900个元素线性表，若分成25块，求其平均查找长度

Question

如题所述

Answer 1

长度为n(900)的表分成均等的b（25）个子表，则每个子表的长度为s，b=n/s（900/25=36）。

顺序查找时成功的平均查找长度为：

（b+s)/2+1=(25+36)/2+1=44

例如：

每块最佳长度为：根号625= 25，即每块25个结点，一共分为25块，此时平均查找长度=2((25+1)/2)= 26

扩展资料：

分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

参考资料来源：百度百科-分块查找