假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_
时间: 2024-04-05 16:32:47 浏览: 30
首先,根据散列函数H(K)=K%7,可以得到以下散列表:
|位置|线性探查法|链接法|
|:-:|:-:|:-:|
|0| | |
|1| | |
|2| | |
|3|52| |
|4|25|48->38|
|5|74| |
|6| | |
其中,线性探查法是指当发生冲突时,依次向后查找下一个位置,直到找到空位置为止。链接法是指将散列到同一位置的元素以链表的形式存储在该位置上。
平均查找长度是指查找某个元素时,需要访问的节点数的期望值。对于线性探查法,平均查找长度可以通过以下公式计算:
ASL = (1+1/2+1/3+...+1/m)*(1/(1-a))
其中,m为散列表的长度,a为填充因子(已存储元素个数/散列表长度)。将数据填入公式中,得到:
ASL(linear) = (1+1/2+1/3+1/4+1/5)*(1/(1-5/7)) = 2.4
对于链接法,平均查找长度可以通过以下公式计算:
ASL = 1+a/2
其中,a为填充因子。将数据填入公式中,得到:
ASL(linked) = 1+(5-1)/2 = 2
因此,采用线性探查法处理冲突时,对散列表进行查找的平均查找长度为2.4;采用链接法处理冲突时,对散列表进行查找的平均查找长度为2。
相关问题
假定对线性表(38,25,74,52,48)进行哈希存储,采用H(K)=K % 7作为哈希函数,采用线性探测法处理冲突,则平均查找长度为________。
根据题目描述,将线性表中的元素存储到哈希表中,哈希函数为 $H(K) = K \mod 7$,采用线性探测法处理冲突。
首先,我们将哈希表初始化为空表,如下图所示:
```
0 1 2 3 4 5 6
-------------
| | | | | | | |
-------------
```
接下来,我们将线性表中的元素按照哈希函数的结果存储到哈希表中。如果存储到的位置已经被占用了,则采用线性探测法向后查找,直到找到一个空闲的位置。具体地,对于第一个元素 38,其哈希函数的结果为 3,因此存储到哈希表的第 3 个位置。对于第二个元素 25,其哈希函数的结果为 4,因此存储到哈希表的第 4 个位置。对于第三个元素 74,其哈希函数的结果为 4,但是哈希表的第 4 个位置已经被占用了,因此采用线性探测法向后查找。发现哈希表的第 5 个位置为空闲的,因此将 74 存储到哈希表的第 5 个位置。对于第四个元素 52,其哈希函数的结果为 3,但是哈希表的第 3 个位置已经被占用了,因此采用线性探测法向后查找。发现哈希表的第 4 和第 5 个位置都被占用了,因此继续向后查找。发现哈希表的第 6 个位置为空闲的,因此将 52 存储到哈希表的第 6 个位置。对于最后一个元素 48,其哈希函数的结果为 6,因此存储到哈希表的第 6 个位置。最终得到的哈希表如下所示:
```
0 1 2 3 4 5 6
-------------
| | | |38|25|74|
-------------
|52| | | | |48|
-------------
```
因此,平均查找长度为:
$$
ASL=\frac{1}{5}(1+1+2+2+1)=\frac{7}{5}=1.4
$$
因此,平均查找长度为 1.4。
.对线性表(7,34,55, 25, 64, 46,20,10)进行散列存储时,若选用 H(K)=K%9-作为散列 函数,则散列地址为 1的元
素为:
H(7) = 7 % 9 = 7
H(34) = 34 % 9 = 7
H(55) = 55 % 9 = 1
H(25) = 25 % 9 = 7
H(64) = 64 % 9 = 1
H(46) = 46 % 9 = 1
H(20) = 20 % 9 = 2
H(10) = 10 % 9 = 1
因此,散列地址为1的元素有55、64、46和10。