给定11个关键字序列22，66, 9，11，6，33，7，56，18，19，16试分别用二分查找（假设已排序）、二叉排序树查找（不做平衡）、散列查找的开地 址法(用线性探查法，模取13的HASH函数）和拉链法（模取7的HASH函数）)来实现查找的平均查找长度

1. 二分查找法平均查找长度：
首先需要将序列排序，排好序后，每次查找中间位置的数，比较关键字大小，然后根据比较结果缩小查找范围，直到找到目标数据或者范围缩小到只有一个数。

对于11个关键字序列，排序后为6，7，9，11，16，18，19，22，33，56，66。则平均查找长度为：log2(11) ≈ 3.46。

2. 二叉排序树查找法平均查找长度：
将11个关键字序列依次插入到一棵二叉排序树中，查找时从根节点开始，比较关键字大小，根据比较结果选择左子树或右子树继续查找，直到找到目标数据或者发现节点为NULL。

对于这11个关键字序列，可以构建如下的二叉排序树：

            22
          /    \
         11     66
        /  \      \
       9   16      56
      /   /  \     / \
     6   18  19  33  67

则平均查找长度为：(1+2+2+3+3+3+4+4+4+4+5)/11 ≈ 3.36。

3. 散列查找的开地址法平均查找长度：
使用线性探查法，将11个关键字序列依次插入到一个大小为13的散列表中，冲突时采用线性探查法，即向后查找直到找到空位为止。

使用模取13的HASH函数，对于每个关键字计算出的散列地址如下所示：

22 -> 9
66 -> 3
 9 -> 9
11 -> 11
 6 -> 6
33 -> 7
 7 -> 7
56 -> 4
18 -> 5
19 -> 6
16 -> 3

插入完成后，散列表如下所示：

 0: 
 1: 
 2: 
 3: 66 16
 4: 56
 5: 18
 6: 19
 7: 33 7
 8: 
 9: 22 9
10: 
11: 11
12: 6

则平均查找长度为：(1+2+2+4+3+1+1+3+2+2+4)/11 ≈ 2.18。

4. 散列查找的拉链法平均查找长度：
使用拉链法，将11个关键字序列依次插入到一个大小为7的散列表中，冲突时采用链表法，即在散列表中的每个位置上维护一个链表，将冲突的元素插入到链表中。

使用模取7的HASH函数，对于每个关键字计算出的散列地址如下所示：

22 -> 1
66 -> 3
 9 -> 2
11 -> 4
 6 -> 6
33 -> 5
 7 -> 0
56 -> 0
18 -> 4
19 -> 5
16 -> 2

插入完成后，散列表如下所示：

0: 7 -> 56
1: 22
2: 9 -> 16
3: 66
4: 11 -> 18
5: 33 -> 19
6: 6

则平均查找长度为：(1+1+2+1+2+2+1+1+2+2+2)/11 ≈ 1.82。