数据结构教程第5版：查找章节习题详解与平均查找长度

在数据结构教程（第5版）的第九章查找部分，作者李春葆针对有序表的查找策略进行了深入探讨。章节内容包括两个主要部分： 1. 顺序查找与折半查找的判定树: - 本题首先要求构建一个包含五个元素（do、for、if、repeat、while）的有序表，每个元素对应的查找概率和查找不存在的概率已给出。顺序查找的判定树展示了每个元素被查找的可能路径，每一步根据当前元素位置决定下一步搜索方向。折半查找则有所不同，它每次都将搜索范围减半，所以判定树展示的是内部结点和外部结点的层次关系。 2. 平均查找长度（ASL）计算: - 对于顺序查找，平均查找长度分为成功和不成功两种情况。成功查找是指找到目标元素，平均需要的比较次数等于各元素查找概率的加权和；不成功查找是指未找到目标元素，平均次数是查找不存在概率之和。计算结果表明顺序查找的ASL成功为0.97，不成功为1.07。 - 折半查找的ASL计算更复杂，因为它考虑了查找成功时进入内部结点的层次和不成功时进入外部结点的层次。成功查找的ASL为1.04，不成功查找的ASL为1.3。 3. 等概率下的折半查找: - 对于等概率情况下的A[0..10]有序表，需要构建判定树来确定平均查找长度。具体数值未在提供的内容中给出，但通常会根据元素数量和查找概率计算。 - 对于给定的有序表（12, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134），题目要求分析查找特定值时的查找次数。例如，查找90时，由于90在列表中间，折半查找会较快，可能只需进行log2(11)次查找即可定位到。查找47时，因为47在数组前部，查找次数可能会略多一些，具体次数取决于起始位置。查找100时，由于100不在列表中，查找会一直失败直到达到最大查找次数，即11次。 总结来说，第九章查找部分主要涉及了查找算法的基础理论和实际应用，通过实例演示了顺序查找和折半查找的查找过程以及平均查找长度的计算方法，对于理解数据结构中的查找算法性能优化具有重要意义。同时，通过具体问题的解答，帮助读者掌握了如何运用所学知识解决实际问题的能力。