2. 试分别画出在线性表(a,b,c,d,e,e,f)中进行折半查找，以查关键字等于 e、f 和 g 的过程。

　3. 画出对长度为 10 的有序表进行折半查找的判定树，并求其等概时查找成功的平均查找长度。

　4. 假设按下述方法进行顺序表的查找：若表长<=10，则进行顺序查找，否则进行折半查找。试画出对表长 n=50 的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。

　5. 已知含12个关键字的有序表及其相应权值为：
　　关键字 A B C D E F G H I J K L
　　权值 　8 2 3 4 9 3 2 6 7 1 1 4
　(1) 试按次优查找树的构造算法并加适当调整画出由这12个关键字构造所得的次优查找树，并计算它的PH值；
　(2) 画出对以上有序表进行折半查找的判定树，并计算它的 PH 值。

　6. 已知如下所示长度为12的表
　　(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)
　(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
　(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
　(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
　

　7. 可以生成右侧二叉排序树的关键字初始排列有几种？请写出其中的任意三个。

　8. 选取哈希函数 H(k)=(3k) MOD 11。用开放定址法处理冲突，di = i((7k) MOD　10+1) (i=1,2,3,…)。试在 0～10 的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概情况下查找成功时的平均查找长度。

　9. 试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的平均查找长度。
　　（ZHAO, QIAN, SUN, LI, ZHOU, WU, CHEN, WANG, CHANG, CHAO, YANG, JIN）