有序表数据 do,for,if,repeat,while，其查找成功概率分别为0.2,0.15,0.14,0.03,0.01，回答如下问题： 1）画出对该有序表采用顺序查找和折半查找的判定树。 2）分别计算顺序查找时的查找成功和折半查找时的查找成功的平均查找长度。 3）判定折半查找好还是顺序查找好。

好的，我可以回答你的问题。

1）对于该有序表，采用顺序查找和折半查找的判定树如下所示：

顺序查找判定树：

        ┌──[do]───┐
   ┌──[for]───┐   ├──[if]───┐
[do]    [for]   [if]   [repeat]
  |       |      |       |
0.2     0.35   0.49    0.52

折半查找判定树：

            ┌──[do]───┐
       ┌──[for]───┐   ├──[if]───┐
   ┌──[do]    [if]   [repeat]  [while]
[do] [for]    |       |         |
  |   |     0.14    0.29      0.43
0.2 0.15

2）顺序查找时的查找成功的平均查找长度为：

ASLs = 0.2*1 + 0.15*2 + 0.14*3 + 0.03*4 + 0.01*5 = 0.885

折半查找时的查找成功的平均查找长度为：

ASLb = log2(5)/2 = 0.86

其中，ASLs表示顺序查找时的平均查找长度，ASLb表示折半查找时的平均查找长度。

3）通过比较ASLs和ASLb，可以发现折半查找的平均查找长度更小，也就是说折半查找比顺序查找更好。因此，对于该有序表，采用折半查找更为适合。

相关问题

设有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。