长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是 ，查找失败时的平均查找长度是 。A．37/12B．62/13C．39/12D．49/13

第1题：

第2题：

第3题：

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

A37/12

B39/12

C41/12

D35/12

A
略

第4题：

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

• A、37/12
• B、39/12
• C、41/12
• D、35/12

正确答案:A

第5题：

假定对有序表：（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

第6题：

对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为（）的值除以8。

• A、17
• B、19
• C、21
• D、20

正确答案:B

第7题：

在最坏的情况下，查找成功时二叉排序树的平均查找长度（）

• A、小于顺序表的平均查找长度
• B、大于顺序表的平均查找长度
• C、与顺序表的平均查找长度相同
• D、无法与顺序表的平均查找长度比较

正确答案:C

第8题：

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

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

正确答案:D

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

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

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

第16题：

对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为（）的9分之一。

• A、 20
• B、 18
• C、 25
• D、 22

正确答案:A

第17题：

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

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

第18题：

假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。

正确答案:20.5；41

第19题：

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

正确答案:正确

第20题：

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

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

第21题：

第22题：

第23题：

第24题：