设有一组关键字序列为（31,23,17,27,19,11,13,91,61,41)，要求： (1）采用哈希函数： H ( key )= key mod 7。用链地址法解决冲突，试在0~6的散列地址空间对关键字序列构造哈希表。并计算出在等概率情况下查找成功的平均查找长度；(2）以该关键字序列中的各关键字为叶子构造一棵哈夫曼树，并计算出它的带权路径长度 WPL ; (3）按各关键字在该关键字序列中的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

好的，以下是对应的题解：

1. 哈希表构建

采用哈希函数 $H(key) = key \ mod \ 7$，对于每个关键字，计算出其散列地址并插入哈希表中。若发生冲突，则采用链地址法解决，即在对应散列地址的链表中插入该关键字。

关键字序列为（31,23,17,27,19,11,13,91,61,41），哈希表构建的过程如下：

| 地址 | 关键字 |
| --- | --- |
| 0 | 41 |
| 1 | 31，17 |
| 2 | 23，13 |
| 3 | 27，91 |
| 4 | 19 |
| 5 | 11 |
| 6 | 61 |

在等概率情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于采用链地址法解决冲突，所以每个地址上的关键字出现的概率相等，即 $p_i = \frac{1}{n}$。而查找第 $i$ 个关键字时的查找长度与该关键字所在地址上的链表长度 $k_i$ 有关，即 $L_i = k_i + 1$。因此，可以得到：

$$ASL = \frac{1}{n}\sum_{i=1}^n(k_i + 1) = \frac{1}{n}\sum_{i=0}^6(k_i + 1)$$

其中 $k_i$ 表示地址 $i$ 上链表的长度。

2. 哈夫曼树构建

按照哈夫曼树构建的方法，可以得到如下哈夫曼树：

         289
       /     \
     125      164
    /   \    /   \
  53    72  82   82
 / \   /  \
27 26 30  42

其中，每个叶子节点的权值即为对应的关键字，带权路径长度 WPL 为：

$$WPL = 27 \times 1 + 26 \times 2 + 30 \times 2 + 42 \times 2 + 53 \times 3 + 72 \times 3 + 82 \times 3 + 82 \times 3 = 707$$

3. 二叉排序树构建

按照给定的关键字序列，依次插入一棵初始为空的二叉排序树中，可以得到以下二叉排序树：

          31
         /  \
       23   91
      /  \    \
    17   27   41
         /      \
        19      61
           \
           13

在等概率的情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于二叉排序树中各节点的结构与关键字的插入顺序有关，因此 $L_i$ 的值也与插入顺序有关，无法通过概率论的方法进行计算。在一般情况下，二叉排序树的查找成功时间复杂度为 $O(h)$，其中 $h$ 为树的高度。因此，二叉排序树的平均查找长度与树的高度有关，即：

$$ASL = O(h)$$

由于一棵 $n$ 个节点的随机构造的二叉排序树的平均高度为 $O(\log n)$，因此在等概率情况下，该二叉排序树的平均查找长度为 $O(\log n)$。