2. 设有一组关键字(71,23,73,14,55,89,33,43,48),采用哈希函数:h(key)=key

根据给定的哈希函数h(key)=key，我们可以直接将关键字映射为它自己的值作为哈希地址。即71映射为71，23映射为23，以此类推。

在使用哈希函数时，我们通常需要考虑解决冲突的方法。冲突是指不同的关键字经过哈希函数计算后映射到了相同的地址上。对于本题中的哈希函数h(key)=key而言，由于每个关键字都直接映射到自身，因此不会产生冲突的情况。

在实际应用中，使用h(key)=key这样简单的哈希函数并不常见。通常会采用一些更复杂的哈希函数来确保更好的分布性和更小的碰撞概率。

对于给定的关键字(71,23,73,14,55,89,33,43,48)，将它们分别经过哈希函数计算后得到对应的哈希地址(71,23,73,14,55,89,33,43,48)。这样每个关键字就对应了它自己的哈希地址。当我们需要查找某个关键字时，可以直接通过哈希函数计算出它的哈希地址，从而快速定位到对应的位置。

相关问题

1. 假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE，回答以下问题： （1）画出该二叉排序树； （2）求在等概率下的查找成功的平均查找长度。 （3）求在等概率下的查找不成功的平均查找长度。 2. 设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），其哈希函数为h(key)=key % 13。采用开放地址法的线性探测法解决冲突，试在0～18的哈希表中对该关键字序列构造哈希表，并求在成功和不成功情况下的平均查找长度。 （参考答案： 23/12=1.92 58/13=4.46）

很高兴为您解答问题！

1. (1) 二叉排序树如下所示：

          G
         / \
        E   J
       / \   \
      C   F   I
     /     \
    A       H
           /
          D

(2) 对于等概率下的查找成功，平均查找长度为 L = (1+2+3+4+5+6+7+8)/8 = 4.5。

(3) 对于等概率下的查找不成功，平均查找长度为 L = (1+2+3+4+5+6+7+9)/9 ≈ 4.11。

2. 采用线性探测法的哈希表如下所示：

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18
1  14 84 27 68 11 55 20 23 19  10   -   -   -   -   -   -   -   77

对于查找成功的情况，平均查找长度为 L = (1+1+1+1+1+1+1+1+1+1+1+1)/12 = 1。

对于查找不成功的情况，平均查找长度为 L = (1+2+3+4+5+6+7+8+9+10+11+12)/13 ≈ 4.46。

设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：h（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表。计

### 回答1：
根据哈希函数：h（key）=key mod 7，给定一组关键字{9,1,23,14,55,20,84,27}，并采用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表。计算：

1. 对每个关键字应用h（key）函数，得到：{2,1,2,0,6,6,0,6}
2. 根据线性探测再散列法，发生冲突的关键字按照h（key）+1, h（key）+2, h（key）+3 …的顺序查找空闲地址。在这里，h（key）=2，所以当插入23时，需要查找的顺序是2,3,4,5,6,0,1。最终将23插入地址2。
3. 继续插入其他关键字，所有关键字最终被存储在哈希表中。

该关键字序列构造的哈希表为：
0: 20 84
1: 1
2: 9 23
3:
4: 14
5: 55
6: 27

### 回答2：
哈希表是一种数据结构，用于实现集合或映射等抽象数据类型。其特点在于能够快速定位到数据所在的位置，使查找、插入和删除操作具有很高的效率。在哈希表中，数据通过哈希函数转换为索引值，然后在索引位置上存储。不同的数据可能会产生相同的索引值，这种现象称为“哈希冲突”。

本题中，给定的关键字序列为{9，1，23，14，55，20，84，27}，采用哈希函数h（key）=key mod 7进行哈希构造。表长为10，也就是说哈希表有10个位置可以存储数据。若某个位置上已存储有数据，则需要通过开放地址法进行线性探测解决冲突。

哈希表的构造过程如下：

1. 初始化哈希表，将所有位置赋值为空。

2. 遍历关键字序列，将每个关键字通过哈希函数计算出对应的索引值。例如，第一个关键字9的索引值为2，第二个关键字1的索引值为1，依次计算可得：

9 mod 7 = 2
1 mod 7 = 1
23 mod 7 = 2
14 mod 7 = 0
55 mod 7 = 6
20 mod 7 = 6
84 mod 7 = 0
27 mod 7 = 6

3. 检查每个索引位置上是否已经存储数据，如果没有，则将该数据存储在该位置上；如果已经存储了数据，则需要进行线性探测。线性探测的方法是，检查该位置后面的位置，直到找到一个空位置为止，然后将该数据存储在该位置上。例如，第一个关键字9的索引位置2为空，因此将数据存储在该位置上。第二个关键字1的索引位置1也为空，将数据存储在该位置。第三个关键字23的索引位置2已经存储了数据9，因此需要进行线性探测。依次检查索引位置3、4、5、6、7、8、9，发现都已经存储了数据，因此返回索引位置0继续检查，索引位置0为空，将数据23存储在该位置上。依次进行下去，最终得到的哈希表如下：

0 14
1 1
2 9
3 27
4
5 84
6 55
7 20
8
9

4. 统计哈希表中存储的数据个数，得到最终的结果为8个。

### 回答3：
哈希表是一种用于实现字典的数据结构，可以快速地查找和插入数据。哈希表采用哈希函数将关键字映射为表中的地址，在解决冲突方面有多种方法。本题采用开放地址法的线性探测再散列方法来解决冲突。

首先确定关键字的哈希函数：h(key) = key mod 7。即将关键字除以7，取余数作为哈希表的地址。表长为10，因此哈希表中有10个槽位。

接下来，根据开放地址法的线性探测再散列方法，对于发生冲突的关键字，需要将其向后寻找下一个可用的槽位。具体的方法是，如果位置i已经被占用，就从位置i+1开始依次查找，直到找到一个为空的槽位为止。

下面是关键字序列的哈希表构造过程：

1. 初始化哈希表，将所有槽位设为空。
对应二维数组：[[], [], [], [], [], [], [], [], [], []]

2. 将第一个关键字9插入哈希表，计算其地址为2，将其放入这个位置。
对应二维数组：[[], [], [9], [], [], [], [], [], [], []]

3. 将第二个关键字1插入哈希表，计算其地址为1，将其放入这个位置。
对应二维数组：[[], [1], [9], [], [], [], [], [], [], []]

4. 将第三个关键字23插入哈希表，计算其地址为2，发生冲突，向后查找。查找到位置3为空，将23插入该位置。
对应二维数组：[[], [1], [9, 23], [], [], [], [], [], [], []]

5. 将第四个关键字14插入哈希表，计算其地址为0，将其放入这个位置。
对应二维数组：[[14], [1], [9, 23], [], [], [], [], [], [], []]

6. 将第五个关键字55插入哈希表，计算其地址为6，将其放入这个位置。
对应二维数组：[[14], [1], [9, 23], [], [], [], [55], [], [], []]

7. 将第六个关键字20插入哈希表，计算其地址为6，发生冲突，向后查找。查找到位置7为空，将20插入该位置。
对应二维数组：[[14], [1], [9, 23], [], [], [], [55, 20], [], [], []]

8. 将第七个关键字84插入哈希表，计算其地址为0，发生冲突，向后查找。查找到位置1已被占用，继续向后查找。查找到位置2已被占用，继续向后查找。查找到位置3已被占用，继续向后查找。查找到位置4已被占用，继续向后查找。查找到位置5已被占用，继续向后查找。查找到位置6已被占用，继续向后查找。查找到位置7已被占用，继续向后查找。查找到位置8为空，将84插入该位置。
对应二维数组：[[14], [1], [9, 23], [], [], [], [55, 20], [84], [], []]

9. 将第八个关键字27插入哈希表，计算其地址为6，发生冲突，向后查找。查找到位置7已被占用，继续向后查找。查找到位置8已被占用，继续向后查找。查找到位置9为空，将27插入该位置。
对应二维数组：[[14], [1], [9, 23], [], [], [], [55, 20], [84], [], [27]]

10. 哈希表已填满，构造完成。
对应二维数组：[[14], [1], [9, 23], [], [], [], [55, 20], [84], [], [27]]

因此，该关键字序列构造的哈希表为：
0: [14]
1: [1]
2: [9, 23]
6: [55, 20]
7: [84]
9: [27]

其中各槽位中的方括号表示一个链表，链表中存储了哈希地址相同的关键字。每个槽位中的关键字可以通过遍历链表访问到。通过哈希表构造，我们可以快速的定位关键字所对应的槽位，提高查找和插入的效率。