9.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4

首先，我们根据散列函数将关键字散列到对应的槽中：

0: 14
1: 1 -> 27
2: 55
3: 23
4:
5: 19 -> 84
6: 20
7:
8: 68
9: 10 -> 79
10: 11
11:
12:

可以看出散列地址为1的链中有两个记录，即1和27，所以选项B. 2 是正确答案。

相关问题

9.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链接法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。

将关键字用散列函数H(key)=key MOD 13计算散列地址，得到的散列地址如下：

| key | H(key) |
| --- | --- |
| 19 | 6 |
| 14 | 1 |
| 23 | 10 |
| 1 | 1 |
| 68 | 5 |
| 20 | 7 |
| 84 | 4 |
| 27 | 1 |
| 55 | 3 |
| 11 | 11 |
| 10 | 10 |
| 79 | 12 |

其中，散列地址为1的链中有3个记录，即14、1、27。

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。