资源描述：
《北交数据结构-徐薇-第九章作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、9.9解：(1)二叉排序树杳找成功的平均长度：ASL詁M+2x2+3x3+3x4+2x5+lx6]=3.5(2)排序局Apr,Aug,Dec,FebJan,July5June,Mar,May5Nov5Oct,Sep123456789101112二叉排序树：VApr丿〔Feb；June)丿平衡二叉排序树Mar查找成功的平均长度：=-[1x1+2x2+3x4+4x5]=37/129.14试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20、30、50、52、60、68、70,如果此后删除50和68,画出每一步执行后
2、2-3树的状态。9.19选取哈希函数H(k)=(3k)MODllo用开放定址法处理冲突，di=i((7k)MOD10+1)(i=l,2,3-)o试在0—10的散列地址空间中对关键字序列(22、41、53、46、30、13、01、67)构造哈希表，并求等概率情况下查找成功时的平均查找长度。012345678910226741305346130113111126ASL成功：ASL=
3、[lx4+2x2+3+6]=17/8ASL不成功：A5L=
4、[lx4+2x2+3+6]=17/89.20试为下列关键字建立一个装载因子不小于0.75的哈希表，并计
5、算你所构造的哈希表的平均査找长度。(ZHAO、QIAN、SUN、LI、ZHOU、WU、ZHANG、WANG>CHANG、CHAO、YANG、JIN)9.21在地址空间为0—16的散列区中，对以下关键字序列构造两个哈希表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(10,6,13,1,13,10,10,1,19,15,14,4)(1)用线性探测开放定址法处理冲突(2)用链地址法处理并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为H(x)二i/2向下取
6、整，其中i为关键字中第一个字母在字母表中的序号。(1)用线性探测开放定址法处理冲突012345678AprAugDecFebJanMarMayJune12111124910111213141516JulySepOctNov5256ASL成功:血詁[Ix5+2x2+3xl+4xl+5x2+6]=31/12ASL不成功二(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14-60/14(2)用链地址法处理123456789111213141516
