数据结构(C语言版)习题解答

内容发布更新时间 : 2024/12/23 9:40:13星期一 下面是文章的全部内容请认真阅读。

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi