【正确答案】正确答案：(1)设n=1，则e+2*1=2(只有一个根结点时，有两个外部结点)，公式成立。 设有n个结点时，公式成立，即 E _n =I _n +2n (1) 现在要证明，当有n+1个结点时公式成立。 增加一个内部结点，设路径长度为l，则 I _n+1 =I _n +l (2) 该内部结点，其实是从一个外部结点变来的，即这时相当于也增加了一个外部结点(原外部结点变成内部结点时，增加两个外部结点)，则 E _n+1 =E _n +1+2 (3) 由(1)和(2)，则(3)推导为 E _n+1 =I _n +2n+1+2=I _n+1 －1+2n+1+2 =I _n+1 +2(n+1) 故命题成立。 (2)成功查找的平均比较次数s=I／n不成功查找的平均比较次数u=(E，n)／(n+1)=(I+n)／n+1由以上二式，有s=(1+1／n)*u一1。