已知散列表的表长为12(0~11),散列函数为H(k)=k%11,采用拉链法处理冲突,将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中,试构造出该散列表,并求出在等概率情况下的平均查找长度。
时间: 2023-10-07 21:06:52 浏览: 72
首先根据散列函数 H(k)=k%11,计算出关键字的散列地址:
- 20%11=9
- 30%11=8
- 70%11=5
- 15%11=4
- 8%11=8
- 12%11=1
- 18%11=7
- 63%11=8
- 19%11=8
然后将关键字插入到散列表中,按照拉链法处理冲突:
- 下标为0的链表:无元素
- 下标为1的链表:12
- 下标为2的链表:无元素
- 下标为3的链表:无元素
- 下标为4的链表:15
- 下标为5的链表:70
- 下标为6的链表:无元素
- 下标为7的链表:18
- 下标为8的链表:30 -> 8 -> 63 -> 19
- 下标为9的链表:20
这样得到的散列表如下:
```
0:
1: 12
2:
3:
4: 15
5: 70
6:
7: 18
8: 30 -> 8 -> 63 -> 19
9: 20
10:
11:
```
在等概率情况下的平均查找长度可以通过以下公式计算:
$ASL=\sum_{i=0}^{m-1}p_i(s_i+1)$
其中,$m$ 是散列表的长度,$p_i$ 是查找表中第 $i$ 个元素的概率,$s_i$ 是查找第 $i$ 个元素时需要遍历的链表长度。
在这个问题中,每个元素被查找的概率是相等的,为 $\frac{1}{9}$。对于每个下标上的链表,我们可以计算出它的长度 $s_i$:
- 下标为0的链表:$s_0=0$
- 下标为1的链表:$s_1=1$
- 下标为2的链表:$s_2=0$
- 下标为3的链表:$s_3=0$
- 下标为4的链表:$s_4=1$
- 下标为5的链表:$s_5=1$
- 下标为6的链表:$s_6=0$
- 下标为7的链表:$s_7=1$
- 下标为8的链表:$s_8=3$
- 下标为9的链表:$s_9=1$
然后代入公式计算平均查找长度:
$ASL=\frac{1}{9}[(0+1)+(1+1)+(0+1)+(0+1)+(1+1)+(1+1)+(0+1)+(1+1)+(3+1)]$
$ASL=\frac{16}{9}$
因此,在等概率情况下,该散列表的平均查找长度是 $\frac{16}{9}$。