具有12个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（)，折半查找查找失败的平均查找长度为（)。 37/12 B .35/12 C .39/13 D. 49/13，这个是怎么计算的

对于有序表的折半查找算法，成功的平均查找长度为`log2(n+1)-1`，失败的平均查找长度为`log2(n+1)`，其中`n`为表长。

根据题意可知，有序表中有12个关键字，所以`n=12`。因为每个关键字的查找概率相同，所以成功和失败的概率都是`1/12`。

将`n`和成功、失败的概率代入公式可得：

成功的平均查找长度 = `log2(12+1)-1 ≈ 2.58496`

失败的平均查找长度 = `log2(12+1) ≈ 3.58496`

所以答案为B. 35/12。

相关问题

设有5个关键字do,for,if,repeat,while，他们存放在一个有序顺序表中，其查找概率分别是p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01,而查找各关键字不存在的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。（1）分别计算顺序查找是查找成功和不成功的平均查找长度 （2）分别计算折半查找是查找成功和不成功的评价查找长度

（1）顺序查找是一种从头到尾依次查找的算法，其平均查找长度ASL可以通过下面的公式计算：

ASL = Σpi * (i+1) + Σqi * (n+1)
其中，pi表示第i个关键字的查找概率，qi表示第i个关键字的查找失败概率，n表示关键字的总数（这里n=5）。

根据题目中的信息，可以得到每个关键字的查找概率pi和查找失败概率qi，如下所示：

| 关键字 | 查找成功概率 pi | 查找失败概率 qi |
| ------ | --------------- | --------------- |
| do | 0.2 | 0.8 |
| for | 0.15 | 0.85 |
| if | 0.1 | 0.9 |
| repeat | 0.03 | 0.97 |
| while | 0.01 | 0.99 |

将这些值代入公式，得到顺序查找的平均查找长度ASL为：

ASL = 0.2*1 + 0.15*2 + 0.1*3 + 0.03*4 + 0.01*5 + 0.2*6 + 0.15*6 + 0.1*6 + 0.03*6 + 0.02*6 + 0.01*6
= 3.01

因此，顺序查找的平均查找长度为3.01。

（2）折半查找是一种基于比较目标值和中间值的大小来缩小查找范围的算法。在有序顺序表中，折半查找的平均查找长度ASL可以通过下面的公式计算：

ASL = ∑(log2(i+1)) * pi + ∑(log2(n+1)) * qi
其中，pi和qi分别表示关键字的查找概率和查找失败概率，n表示关键字的总数。

将题目中的数据代入公式，得到折半查找的平均查找长度ASL为：

ASL = (log2(1+1)*0.2 + log2(2+1)*0.15 + log2(3+1)*0.1 + log2(4+1)*0.03 + log2(5+1)*0.01)
+ (log2(5+1)*0.2 + log2(5+1)*0.15 + log2(5+1)*0.1 + log2(5+1)*0.03 + log2(5+1)*0.02 + log2(5+1)*0.01)
= 1.779

因此，折半查找的平均查找长度为1.779。