数据结构（C语言版）习题解答

9.4已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，Jun，July，Aug，Sept，Oct，Nov，Dec）表中，每一个元素的查找概率分别为：（0.1, 0.25, 0.05, 0.13, 0.01, 0.06, 0.11, 0.07, 0.02, 0.03, 0.1, 0.07）

（1）若对该表进行顺序查找，求查找成功的平均查找长度； （2）画出从初态为空开始，依次插入结点，生成的二叉排序树； （3）计算该二叉排序树查找成功的平均查找长度；

（4）将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树。

解：（1） ASL=0.1?10.25?2...+0.07?12 （2）与初始输入序列有关

5.43

JanFebMarAprJunMayAugJulySepDecOctNov

（3）ASL=0.1?10.25?2...+0.07?53.2

（4）找到Mar的直接后继，将Mar的左子树移动到最左孩子的左孩子处，然后用直接

后继取代当前结点。

JanFebMayAprJunSepAugJulyOctDecNov

9.5 已知关键字序列{10，25，33，19，06，49，37，76，60}，哈希地址空间为0-10，哈希函数为H(key)=Key，求：

（1）用开放定址线性探测法处理冲突，构造哈希表HT1，分别计算在等概率情况下HT1查找成功和查找失败的ASL；

（2）用开放定址二次探测法处理冲突，构造哈希表HT2，计算在等概率下HT2查找成功的ASL；

（3）用拉链法解决冲突，构造哈希表HT3，计算HT3在等概率情况查找成功的ASL。 解：

这9个数的hash值为： 10,3,0,8,6,5,4,10,5 冲突有2个。 0 33 1 76 2 3 25 4 37 5 49 6 06 7 60 8 19 9 10 10 ASL1=11?73?13?1)(913 938 遇到空还没有，则算失败。 11ASL2=(F(0)+F(1)+...+F(10))/11=

（2）d=0,1,-1,4,-4…… 0 33 1 60 2 3 4 25 5 49 6 06 7 8 19 9 76 10 10 ASL=(3)

012345678910151?73?15?1 )(93332537490660191076

ASL=11?72?2)(911 9