首页 > 试题广场 >

已知一个线性表(38,25,74,63,52,48)，采用的

[不定项选择题]

已知一个线性表(38,25,74,63,52,48)，采用的散列函数为 Hash($Key)=$Key mod 7，将元素散列到表长为7的哈希表中存储。请选择后面两种冲突解决方法分别应用在该散列表上进行等概率成功查找的平均查找长度，拉链法，线性探测法 .

```
1
```
```
1.5
```
```
1.7
```
```
2
```
```
2.3
```
```
7/6
```
```
4/3
```
```
3/2
```

牛客304487号

选GD

首先根据散列函数hash的结果为

0	1	2	3	4	5	6
63			38	25		48
			52	74

1.拉链法：

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。

根据拉链法在该散列表上进行等概率成功查找的平均查找长度为L=(1+1+2+1+2+1)/6=4/3

2.线性探测法：

线性探测法属于开放定址法，当当前散列表空间p已经有元素时，则将会检测p+1空间，以此类推，得到的结果为