题18

题18

题目

Q:设顺序存储的某线性表共有 123 个元素, 按分块查找的要求等分为 3 块.
若对索引表采用顺序查找法来确定子块, 且在确定的子块中也采用顺序查找法, 则在等概率情况下, 分块查找成功的平均查找长度为 ( ).
A. 21
B. 23
C. 41
D. 62

分析

A:

解

B
根据公式 ,其中 ,代入不难得出 ASL 为 23。所以选 B。
另一方面, 可根据穷举法来一步步模拟。
对于 A 块中的元素, 查找过程的第一步是先找到 A 块,由于是顺序查找,找到 A 块只需一步,然后在 A 块中顺序查找。
因此,A 块内各元素查找长度分别为 。对于 块,采用类似的方法,但查找到 块要比查找到 块多一步,因此 块内各元素查找长度为 。同理, 块中各个元素查找长度为 , 44。
所以平均查找长度为 。