C++数据结构第7章：查找技术详解与习题解析

本资源是关于数据结构在C++中的第7章——查找技术的详细解析，主要涵盖了查找算法在不同存储结构和数列中的应用以及相关理论。章节内容包括填空题和选择题，旨在帮助学习者理解和掌握查找技术的基础概念和实际操作。 **填空题详解：** 1. **顺序查找** 适用于存储结构为**顺序存储** 的线性表，这是因为顺序存储方式下，元素按照物理顺序排列，查找时按顺序访问。而**折半查找** 则适用于**顺序存储** 结构，且要求表中的元素必须是**按关键码有序**，以便于快速定位目标元素。 2. 对于已排序的线性表，折半查找的最坏情况（查找失败）需要比较**表长**，即125次，最好情况（查找成功）只需比较**根节点**，即1次。因此，若查找成功，至少需要比较1次，最多需比较7次。 3. 对于给定的数列，顺序存储结构中查找的平均比较次数为**数列长度**，即8次，因为每个元素都需要被检查一次。而对于二叉排序树，平均查找长度为所有结点比较次数之和除以元素个数，等于**59/15**次。 4. 在长度为20的有序表中，采用折半查找，查找长度为3的元素数量等于第3层的结点数，即4个元素。 5. 在散列函数H(k)=k mod 7的映射下，元素48的同义词是**62**，因为它们经过散列函数运算后的结果相同。 6. 散列技术中处理冲突的主要方法有**开放定址法** 和**拉链法**，前者通过重新计算散列地址直到找到空闲位置，后者在每个桶里维护一个链表来存储冲突的元素。 7. 在查找方法中，**散列查找** 的平均查找长度与结点个数无关，因为它依赖于散列表的装载因子，而不是元素的数量。 8. 散列查找的特点是通过**关键码计算确定记录的存储地址**，并可能涉及一定的比较，以解决冲突，查找效率通常较高。 **选择题详解：** 1. 静态查找与动态查找的区别在于**所施加的操作不同**。静态查找仅进行查找操作，不涉及插入和删除，而动态查找则支持这些操作。 2. 对于有序顺序表，顺序查找在查找成功时和查找不成功时的比较次数都与目标值的位置有关，不一定等于折半查找的次数。查找成功时，可能s和b相等，也可能s更多，具体取决于目标值的位置；查找不成功时，由于顺序查找需要检查整个序列，所以s通常会大于b。 总结来说，本章内容深入浅出地讲解了查找技术在C++中的应用，包括基本原理、适用场景以及在不同情况下的性能分析，是理解数据结构优化和高效搜索算法的重要章节。