A-A+

有一个长度为12的有序表按折半查找法对该表进行查找在表内各元素等概率情况下查找成功时所需

2022-08-12 15:56:34 问答库阅读 196 次

问题详情

有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功时所需平均比较次数为_______。
A．35／12
B．37／12
C．39／12
D．43／12

请帮忙给出正确答案和分析，谢谢！

参考答案

正确答案：B
由题目已知元素序号(即下标)范围为1～12。查找1次成功的结点为：6。查找2次成功的结点为：3，9。查找3次成功的结点为：1，4，7，11。查找4次成功的结点为：2，5，8，10，12。成功查找所有结点的总的比较次数为:1×1+2×2+3×4+4×5=37平均比较次数为37／12。因此选择B。