三．（1） 二叉排序树 T T case for while class proted do private virtu const if publi int templace （2）删去关键字“for”之后的二叉排序树 T case class do while protecte const private virtual if public int templace 

（3）再插入关键字“for”后的二叉排序树 T do case while class protected virtual const private publi if for int templac （4）T”的先序序列：do case const while protected private if for int virtural public template T’的中序序列：case class const do for if int private protected public templat virturale while T”的后序序列：class const for case int if private template public virtural protected while 4.（1）查找 707 时，首先根据哈希函数计算得出该元素应该在哈希表中的 0 单元，但是在 0 但愿没有找到，因此将向下一个单元探测，结果发现该单元是-1，所以结束查找，这将导致 707 无法找到。 （2）如果改用“-2“作为删除标记，则可以正确找到 707 所在结点。 四．（1）查找成功时 ASL=37/12，查找失败时的 ASL=６２/１３． （５）采用除留余数法构造哈希函数，即Ｈ（ｋ）＝ｋＭＯＤ１１，且采用步长为１的线性 探测再哈希表法处理冲突，对应的地址如下： Ｈ（３２）＝３２ＭＯＤ１１＝１０ Ｈ（６３）＝６３ＭＯＤ１１＝８ Ｈ（９４）＝９４ＭＯＤ１１＝６ Ｈ（３６）＝３６ＭＯＤ１１＝３（冲突） （仍然冲突） Ｈ（３６）＝（４＋１）ＭＯＤ１１＝５ Ｈ（７０）＝７０ＭＯＤ１１＝４（冲突） （仍然冲突） Ｈ（７０）＝（５＋１）ＭＯＤ１１＝６（仍然冲突） Ｄ１１＝７（仍然冲突） Ｈ（７０）＝（７＋１）ＭＯＤ１１＝８（仍然冲突） Ｄ１１＝９（仍然冲突） Ｈ（７０）＝（９＋１）ＭＯＤ１１＝１０（仍然冲突） Ｈ（７０）＝（１０＋１）Ｍ ＯＤ１１＝０ Ｈ（４８）＝４８ＭＯＤ１１＝４ Ｈ（２５）＝２５ＭＯＤ１１＝３ Ｈ（３６）＝（３＋１）ＭＯＤ１１＝４ Ｈ（１８）＝１８ＭＯＤ１１＝７ Ｈ（７０）＝（４＋１）ＭＯＤ１１＝５ Ｈ（７５）＝７５ＭＯＤ１１＝９ Ｈ（７０）＝（６＋１）ＭＯ Ｈ（７０）＝（８＋１）ＭＯ 

哈希表 地址 关键字 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ ２５ ４８ ３６ ９４ １８ ６３ ７５ ３２ 平均查找长度 ASL=（1*7+3*1+8*1）/9=18/9=2/1 （2）采用除留余数法构造哈希函数，即 H（k）=kMOD11，且采用步长为 3 的线性探测再哈 希法处理冲突，哈希表： Ｈ（３２）＝３２ＭＯＤ１１＝１０ Ｈ（６３）＝６３ＭＯＤ１１＝８ Ｈ（９４）＝９４ＭＯＤ１１＝６ Ｈ（３６）＝３６ＭＯＤ１１＝３（冲突） （仍然冲突） Ｈ（３６）＝（6＋3）ＭＯＤ１１＝9（仍然冲突） １＝1 Ｈ（18）＝18ＭＯＤ１１＝7 Ｈ（７０）＝（4＋3）ＭＯＤ１１＝7（仍然冲突） １＝10（仍然冲突） Ｈ（７０）＝70ＭＯＤ１１＝4（冲突） Ｈ（７０）＝（7＋3）ＭＯＤ１ Ｈ（７０）＝（10＋3）ＭＯＤ１１＝2 Ｈ（７５）＝７５ＭＯＤ１１＝９ Ｈ（４８）＝４８ＭＯＤ１１＝４ Ｈ（２５）＝２５ＭＯＤ１１＝３ Ｈ（３６）＝（３＋3）ＭＯＤ１１＝6 Ｈ（３６）＝（6＋3）ＭＯＤ１ 哈希表 0 地址 关键字 1 36 2 70 3 25 4 48 5 6 94 7 18 8 63 9 75 10 32 平均查找长度 ASL=（1*7+4*2）/9=15/9=5/3