设一组有序的关键字序列为（13，18，24，35，47，50，62，83，90），查找方法采用折半查找，要求：（1）画出折半查找的二叉判定树；（2）给出查找关键字62时需要和哪些关键字进行比较；（3）计算出查找成功时的平均查找长度。

好的，我来回答你的问题。

（1）折半查找的二叉判定树如下所示：

                            47
                           /  \
                          /    \
                         /      \
                       18      83
                      /  \    /  \
                     /    \  /    \
                    13    24 62    90
                          /  \
                         /    \
                        35    50

（2）查找关键字62时需要和以下关键字进行比较：47，83，62。

（3）查找成功时的平均查找长度是log2n，其中n为关键字序列中关键字的个数。在这个例子中，n=9，所以平均查找长度为log2(9)≈3.17。

相关问题

设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用3.二分查找，要求计算出查找关键字 62 时的比较次数并计算出查找成功时的平均查找长度。

使用二分查找法查找关键字 62，具体步骤如下：

1. 设变量 low=0，high=8，mid=(low+high)/2=4，即取中间位置的值 47。
2. 由于 62>47，所以在序列的右半部分继续查找，令 low=mid+1=5。
3. 再次计算 mid=(low+high)/2=6，即取中间位置的值 62。
4. 查找成功，比较次数为 2，平均查找长度为 (4+2)/2=3。

所以，查找关键字 62 时的比较次数为 2，查找成功时的平均查找长度为 3。

设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为____。

利用二分法查找关键字 90，需要进行以下步骤：

1. 确定中间位置，即 (0 + 10) / 2 = 5。

2. 比较中间位置的关键字 50 和要查找的关键字 90，由于 50 < 90，所以在右半部分继续查找。

3. 在右半部分中，确定中间位置，即 (6 + 10) / 2 = 8。

4. 比较中间位置的关键字 90 和要查找的关键字 90，由于相等，查找成功。

因此，利用二分法查找关键字 90 需要比较的关键字个数为 2。