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

第1题：

第2题：

第3题：

有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

A37/12

B39/12

C41/12

D35/12

A
略

第4题：

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

（2）4次；3次
略

第5题：

假定对长度n=50的有序表进行折半查找，则对应的判定树高度为（），最后一层的结点数为（）。

正确答案:6；19

第6题：

假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为（）；比较四次查找成功的结点数为（），其下标从小到大依次是（），平均查找长度为（）。

正确答案:2；8；1，3，6，8，11，13，16，19；3.7

第7题：

有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）

• A、22/8
• B、20/8
• C、23/8
• D、21/8

正确答案:D

第8题：

有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

• A、29/9
• B、26/10
• C、31/10
• D、29/10

正确答案:D

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）。

略

第15题：

设查找表为（20，19，24，57，68，11）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）

略

第16题：

假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。假定每个元素的查找概率相等，求查找成功时的平均查找长度。

正确答案:求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08

第17题：

对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是（），对于查找成功，他们的平均查找长度是（）

正确答案:不同的；相同的

第18题：

若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（）。

• A、1
• B、2
• C、3
• D、4

正确答案:C

第19题：

长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。

正确答案:37/12；62/13

第20题：

设查找表为（20，19，24，57，68，11）。求在等概率条件下，对上述有序表成功查找的平均查找长度。

正确答案:平均查找长度=（1*1+2*2+3*3）/6=14/6

第21题：

第22题：

第23题：