数据结构（查找）习题及答案

一、填空 １、顺序查找法等概率下查找成功时的平均查找长度为（），查找不成功时的比较次数为（）。 ２、对线性表进行折半查找时，要求线性表必须（）。 ３、设哈希表L长m=14，哈希函数H(key)=key%11，表中已...... ........ 五、设有３阶Ｂ－树如下，画出删除关键字值１７的过程。 　 　 六、设哈希函数H(key)=key%13，用公共溢出区法处理冲突。试在０～１９的散列地址空间中对关键字序列（１９，０１，２３，１４，５５，２０，８４，２７，６８，１１，１０，７７）造哈希表，并求等概率下查找成功时的平均查找长度。 ....... 数据结构中的查找技术是计算机科学中的重要概念，用于在数据集合中寻找特定元素。本题主要涉及了多种查找方法，包括顺序查找、折半查找、哈希查找以及B-树和二叉排序树的构建与操作。以下是这些知识点的详细说明： 1. **顺序查找**： - 平均查找长度：当等概率查找时，如果查找成功，平均查找长度为（n+1）/2，查找不成功时的比较次数为n+1。 - 适用于任何数据结构，但效率较低，特别是对于大型无序数据集。 2. **折半查找**： - 要求线性表必须是有序的，且通常采用顺序存储结构。 - 在长度为17的有序表中，等概率下查找成功的平均查找长度可以通过计算判定树得出。 3. **哈希查找**： - 哈希函数H(key)=key%11，当哈希表长度m=14时，可以计算特定关键字的哈希地址。 - 使用二次探测再散列法处理冲突，例如关键字值为49的节点在L中的下标可以通过二次探测得到。 - 即使使用哈希表，也可能因为冲突的存在导致仍需进行关键字间的比较。 - 在给定的关键字序列中构造哈希表并计算等概率下查找成功时的平均查找长度，需要考虑冲突解决策略对查找效率的影响。 4. **二叉排序树**： - 对给定的关键字序列（33, 62, 76, 45, 52, 58）构造二叉排序树，可以手动绘制并计算等概率下查找成功的平均查找长度。 - 构造平衡的二叉排序树，如AVL树，可以保持树的平衡，从而提高查找效率。 5. **B-树**： - 删除关键字值17的B-树操作需要理解B-树的性质，确保删除后仍然满足B-树的平衡条件。 - 可能需要合并结点来保持树的平衡。 6. **递归算法**： - 递归算法OutputNLT用于从大到小输出二叉排序树中所有关键字值不小于x的数据元素，其时间复杂度为O(log2n+m)，其中n是排序树中结点数，m是输出的关键字个数。 这些知识点是数据结构中查找算法的基础，理解和掌握它们对于解决实际问题至关重要，尤其是在数据库、操作系统、编译器等领域的应用。通过这些习题，我们可以深入学习查找算法的实现和性能分析，提升解决问题的能力。