散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。 (1)元素59存放在散列表中的地址是( )。 (2)存放元素59需要搜索的次数是( )

(1) 元素59的散列地址为：59 mod 17 = 8。但是8号地址已经被元素8占据了，因此需要进行线性探测。依次检查9,10,...,16,0,1,2,3,4,5,6,7这些地址，直到找到一个空闲地址为止。假设最终找到了地址3，那么元素59就会被存放在地址3上。
因此，元素59存放在散列表中的地址是3。

(2) 存放元素59需要搜索的次数为：1次。因为59的散列地址就是8，但是8号地址已经被元素8占据了，因此直接检查下一个地址9，发现地址9是空闲的，因此59就被存放在了地址9上，只进行了1次探测。

相关问题

设散列表的地址区间为0~17，散列函数为H(K) =K mod 13，K为关键字。用线性探测法

来解决散列冲突，其中插入的关键字序列为{16, 25, 20, 36, 14, 23, 8, 18}，请画出插入后的散列表。

首先，根据散列函数H(K) =K mod 13，我们可以算出每个关键字的散列地址：

- 16 -> H(16) = 3
- 25 -> H(25) = 12
- 20 -> H(20) = 7
- 36 -> H(36) = 10
- 14 -> H(14) = 1
- 23 -> H(23) = 10（冲突）
- 8 -> H(8) = 8
- 18 -> H(18) = 5

发现23和36的散列地址相同，因此需要使用线性探测法来处理冲突。具体来说，就是从冲突地址开始，依次往后查找下一个空闲位置，直到找到可以插入的位置。在这个例子中，我们可以按照以下步骤来插入关键字：

- 16 -> 3 -> 空 -> 空 -> 16
- 25 -> 12 -> 空 -> 空 -> 25
- 20 -> 7 -> 空 -> 空 -> 20
- 36 -> 10 -> 空 -> 空 -> 36
- 14 -> 1 -> 空 -> 空 -> 14
- 23 -> 10 -> 空 -> 1 -> 23
- 8 -> 8 -> 空 -> 空 -> 8
- 18 -> 5 -> 空 -> 空 -> 18

最终的散列表如下图所示：

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 16 |    |    | 25 |    |    | 20 | 36 |    | 14 | 23 |  8 | 18 |    |    |    |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
  0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17

注意，在线性探测法中，如果散列表已经被占满，插入新的关键字将失败。因此，在设计散列表时，需要考虑预留一定的空间，以免发生这种情况。

设散列表的地址区间为0~17，散列函数为H(K) =K mod 13，K为关键字。用线性探测法（di=1,2,3,4，...）处理冲突，输入关键字序列：（10,24,32,17,31,30,46,47,40,63,49）

解析：
根据散列函数，将关键字对应的位置计算出来：
H(10) = 10 mod 13 = 10
H(24) = 24 mod 13 = 11
H(32) = 32 mod 13 = 6
H(17) = 17 mod 13 = 4
H(31) = 31 mod 13 = 5
H(30) = 30 mod 13 = 4
H(46) = 46 mod 13 = 7
H(47) = 47 mod 13 = 8
H(40) = 40 mod 13 = 1
H(63) = 63 mod 13 = 8
H(49) = 49 mod 13 = 10

接下来，按照线性探测法进行处理。首先，将第一个关键字10存入位置10，如果后面的关键字计算后的位置已经被占用，就从下一个位置开始尝试放入，即依次尝试11、12、0、1、2……直到有空位置为止。

关键字 位置
10 10
24 11
32 6
17 4
31 5
30 12
46 7
47 8
40 1
63 3
49 0

因为所有的位置都已经被占用了，所以需要重新散列。根据重新散列后的位置，同样应用线性探测法存储关键字。

关键字 位置
10 10
24 11
32 6
17 4
31 5
30 12
46 7
47 8
40 15
63 3
49 0

最终结果为：
位置 关键字
0 49
1 40
2
3 63
4 17
5 31
6 32
7 46
8 47
9
10 10
11 24
12 30
13 14
14
15
16
17

可以看到，所有的关键字都被放入散列表中了。