数据结构查找问题解答：顺序查找与二叉排序树

"该资源为一份关于查找技术的习题和实验解答，涵盖了第9章的习题、思考题和上机题，旨在帮助学习者巩固和理解查找算法的相关知识，包括顺序查找、二分查找、二叉排序树、散列表等数据结构和算法的应用。" 在这份习题解答中，主要涉及了以下几个知识点： 1. **顺序查找**：对于长度为11的顺序表，等概率情况下，查找成功时的平均查找长度是6，查找失败时的平均查找长度是11。这表明在未排序的序列中，平均需要检查一半的元素才能找到目标。 2. **动态查找与静态查找**：动态查找允许在数据结构中插入或删除元素，而静态查找通常适用于不可变的数据集。例如，有序表更适合静态查找，而二叉排序树则既适合静态也适合动态查找。 3. **二分查找**：在长度为7的有序表中，使用二分法查找，每个元素被查找的概率相等时，查找成功的平均查找长度是17/7，查找失败的平均查找长度是3。这是因为二分查找每次可以排除一半的元素，所以查找次数少。 4. **二叉排序树**： - 最低高度为4的二叉排序树能包含16个键值，因为每个内部节点最多有两个子节点。 - 最大的高度为16，这对应于完全不平衡的二叉树，即每个节点只有一个子节点。 - 最大值结点位于最右下角，即右子树为空的最下方节点。 - 最小值结点位于最左下角，即左子树为空的最下方节点。 5. **分块查找**：为了适应动态变化且提高查找效率，可以采用分块查找。当线性表有225个元素时，每块含15个元素最佳，因为这可以平衡查找块和在块内查找的时间。 6. **散列表**： - 线性探查法处理冲突的例子中，当表长m=15，散列函数H(k)=k mod 13时，元素74的存储地址是13，因为74 mod 13 = 1，然后根据线性探查，发现13位置已经有元素（64），因此加1得到14，但14位置也有元素（52），再加1得到15，溢出回到0，所以是13。 - 在采用二次探测法处理冲突的闭散列表上，查找成功时探测的位置上的键值可能都是同义词，这意味着这些位置存储的是哈希冲突的元素。 这份习题解答涵盖了查找技术的基本概念和应用，有助于学习者深入理解各种查找算法的效率和适用场景，以及解决冲突的方法。通过解决这些习题，学生可以更好地掌握查找算法的精髓，并能运用到实际问题中。