（11 分）使用散列函数 hash(x)=x mod 11，把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22 插入到散列表中。 （1）使用链地址的冲突处理方法来构造散列表。 （2）分别计算等概率情况下，查找成功和查找不成功的平均探查长度。（假设探查到空结点也算一次探查） （3）若查找关键字 34，则需要依次与哪些关键字比较。

散列表

[tag_link]

**【解析】** (1) 采用链地址法构造散列表时，在直接计算出关键字对应的哈希地址后，将关键字结点插入到此哈希地址所在的链表中。由 `hashf(x) = x mod 11` 可知，散列地址空间是 0 到 10。链地址法构造的表如下：

(2) 在链地址表中查找成功时，查找关键字为 33 的记录需进行 1 次探测，查找关键字为 22 的记录需进行 2 次探测，依此类推。因此： $$AS{L}_{\text{成功}}=\frac{1\times 4+2\times 3+3}{8}=\frac{13}{8}$$

查找失败时，假设对空结点的查找长度为 1，则对于地址 0，查找失败的探测次数为 3；对于地址 1，查找失败的探测次数为 4，则平均探查长度为： $$AS{L}_{\text{失败}}=\frac{3+4+2+1+3+1+1+1+1+1+1}{11}=\frac{19}{11}$$

(3) 由 (1) 可知，查找关键字 34，需要依次与关键字 1, 12, 34 进行比较。

【扩展】对同样一组关键字，设定相同的散列函数，则不同处理冲突方法将得到不同的散列表，它们的平均查找长度也不同，本题若采用线性探查法处理冲突，题目应如何解答？