将上述内容中$$改成数字
时间: 2023-09-06 19:10:38 浏览: 51
好的,以下是对应的题解:
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}{10}\sum_{i=1}^{10}(k_i + 1) = \frac{1}{10}\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 = O(h) = O(\log n)$$
其中 $n$ 为关键字数,$h$ 为二叉排序树的高度。由于一棵 $n$ 个节点的随机构造的二叉排序树的平均高度为 $O(\log n)$,因此在等概率情况下,该二叉排序树的平均查找长度为 $O(\log n)$。