采用折半搜索法搜索长度为n的有序顺序表，搜索每个元素的平均比较次数()对应二叉判定树的高度(设高度≥2)。

A、n

B、

C、

D、

A.1,2,3

B.9,5,2,3

C.9,5,3

D.9,4,2,3

A、1

B、2

C、4

D、8

(1)搜索失败;

(2)搜索成功，且表中只有一个关键码等于给定值k的元素;

(3)搜索成功，且表中有若千个关键码等于给定值k的元素，要求一次搜索找出所有元素。

已知如下所示长度为12的表：(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)

①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

对线性表采用折半查找法，该线性表必须______ 。

A．采用顺序存储结构

B．采用链式存储结构

C．采用顺序存储结构，且元素按值有序

D．采用链式存储结构，且元素按值有序

A、i>0

B、1≤i≤n

C、0≤i≤n-1

D、0≤i≤n

证明下列关系：

(1)设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。试利用归纳法证明E=1+2n，n≥1.

(2)利用(1)的结果，试说明：成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度U.之间的关系可用公式Sn=(1+1/n)Un-1，n≥1表示。