9、9 解:(1) 二叉排序树查找成功得平均长度:(2)排序后:Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep 1 2 3 4 5 6 7 8 9 10 11 12二叉排序树:查找成功得平均长度:平衡二叉排序树查找成功得平均长度:9 、 14 试 从 空 树 开 始 , 画 出 按 以 下 次 序 向 23 树 即 3 阶 B 树 中 插 入 关 键 码 得 建 树 过程:20、30、50、52、60、68、70,假如此后删除50与68,画出每一步执行后23树得状态。JulyDecMayAprFebJuneyAugOctMarSepJanNovMarJanOctAugJuneMayAprSeptJulyFebNov9、19 选取哈希函数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)构造哈希表,并求等概率情况下查找成功时得平均查找长度。 012345678910226741305346130113111126ASL成功:ASL不成功:9、20 试为下列关键字建立一个装载因子不小于 0、75 得哈希表,并计算您所构造得哈希表得平均查找长度。(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 向下取整,其中 i 为关键字中第一个字母在字母表中得序号。 (1)用线性探测开放定址法处理冲突 ASL成功:ASL 不 成功 = (5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14=60/14（2）用链地址法处理 012345678910111213141516平均查找长度:012345678AprAugDecFebJanMarMayJune12111124910111213141516JulySepOctNov5256AprAug^Dec^Feb^JanJuneJuly^May^MarNovOct^Sep^^ ^ ^^^^^^^^^^^^^^
