设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……, 11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?

第1题：

画出对长度为10的有序表进行折半查找的判定树（以序号1，2，……10表示树结点），并对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。
（1）

（2）ASL=（1x1+2x2+3x4+4x3）/10=29/10
略

第2题：

画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度。

第3题：

1. 假定对有序表：（6，10，15，17，24，35，46，57，66，73，85，90）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树；（4分） （2）若查找元素24，需依次与哪些元素比较？（2分） （3）若查找元素92，需依次与哪些元素比较？（2分） （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。（2分）

第4题：

设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）。为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？
（1）

（2）4次；3次
略

第5题：

画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。