5.假定对有序表：（3，5，7，24，30，46，63，72，87）进行折半查找，试回答下列问题： 1）画出描述折半查找过程的判定树。 2）若查找元素46，需依次与哪些元素比较？ 3）假定每个元素的查找概率相等，求查找成功时的平均查找长度ASL。

1）判定树如下：

                     (3,5,7,24,30,46,63,72,87)
                               |
                             (24,46,72,87)
                               |
                             (46,72,87)
                               |
                              (46)

2）查找元素46需要依次与30、63、46比较。

3）平均查找长度ASL = 成功查找时的ASL × 成功查找概率 + 不成功时的ASL × 不成功概率。

由于每个元素的查找概率相等，成功查找概率为1/9，不成功概率为8/9。成功查找时的ASL为3，不成功时的ASL为4。因此，ASL = 3 × 1/9 + 4 × 8/9 = 35/9。

相关问题

假定对有序表:(3,4,5,7 , 24, 30, 42, 54, 63,72, 87 , 95 )进行折半查找,试回答下列问题: 1画出描述折半查找过程的判定树; 2若查找元素54 ,需依次与哪些元素比较? 3若查找元素90 ,需依次与哪些元素比较? 4假定每个元素的查找概率相等求查找成功时的平均查找长度。

好的，我来回答您的问题：

1. 下面是描述折半查找过程的判定树：

                      54?
                    /     \
                  30?     87?
                 /   \    /   \
               24?   42? 72?  95?
              /   \  /  \ /  \
            3?    5? 7?  63?  54?

2. 查找元素54时，需要依次与30、87、63进行比较。

3. 查找元素90时，需要依次与54、87进行比较，但因为没有找到，最后返回空。

4. 假设每个元素的查找概率相等，那么成功查找的平均查找长度为:

(1/12)*1 + (1/6)*2 + (1/6)*3 + (1/4)*4 + (1/4)*5 = 2.92

其中，1/12表示查找第一个元素的概率，需要比较1次；1/6表示查找第二个元素的概率，需要比较2次；1/4表示查找第四个或第五个元素的概率，需要比较4次或5次。

假定对有序表:(2，4,5,7.24，35，42，53，63，72，90，95)进行折半口找，成回答下列问题:(1) 画出届述历半查就过程的判定树; (2)精直代元家54,需依次与邮些元素比4敌?(3...

非常抱歉，我并不是一个能够绘制图表的AI。但是，我可以回答您的问题。

1. 如果对有序表(2,4,5,7,24,35,42,53,63,72,90,95)进行折半查找，它的判定树如下：

53
/ \
24 72
/ \ / \
7 42 63 90
/ \ / \ / \ / \
4 5 35 - - - - 95
/ \
2 -

2. 如果要在该有序表中查找元素54，则需要与元素53比较，因为其为最接近且小于于54的元素，而元素72过大。

3. 通过折半查找，最坏情况下最多需要比较11次。