二分查找与B树相关练习题解析

第9章(查找)的练习题涵盖了多种查找算法和数据结构的理论与实践应用。本部分主要探讨了以下几个关键知识点： 1. 二分查找的速度比较：二分查找（也称折半查找）相比于顺序查找，由于其每次将搜索范围缩小一半，因此在有序表中查找元素的速度通常会更快，选项A“必然快”是正确的。 2. 平均查找长度：具有12个关键字的有序表，折半查找的平均查找长度可以通过计算得到，由于二分查找的平均情况是每一次查找都正好找到中间位置，直到找到或搜索范围为空，所以对于12个元素，最坏情况下需要查找6次，平均次数为 (1+2+...+6)/2=13/2=6.5，接近于选项C的2.5，但题目可能需要四舍五入到小数点后一位，具体答案可能是2.5或3.1，取决于题目要求的精度。 3. 动态变化的需求：为了实现在线性表中快速查找且能适应动态增删操作，应选择动态查找方法，即哈希查找或动态查找表，选项A“分块查找”一般用于数据库中的索引，而选项C“折半查找”适用于静态且完全有序的表，选项D“基于属性”没有明确提及，所以选项A可能是最佳选择，但实际中可能还需根据具体需求判断。 4. 二叉排序树的构造：不同序列构造的二叉排序树可能会导致不同的形状，其中B选项的顺序与大多数其他选项相反，可能导致树的形态不同，因此结果与其他三个不同。 5. 平衡二叉树调整：当平衡二叉树插入后出现不平衡，通过观察不平衡结点A的左右孩子平衡因子，A的左孩子平衡因子为0，右孩子平衡因子为1，说明插入导致右孩子偏大，应该进行右旋（Right Rotation，即RR型调整）来恢复平衡。 6. B和B+树的比较：选项D表述错误，B树和B+树虽然都是平衡的多叉树，可用于文件索引结构，支持顺序检索，但B+树在插入和删除时会更加高效，因为所有键都在叶子节点，而B树的非叶子节点也存储键值，这使得B+树更利于随机检索而非顺序。 7. B-树特性：m阶B-树是一种特殊的平衡多叉树，每个节点有m个或更多的子节点，选项C描述正确，m阶B-树是m叉平衡排序树。 8. 散列表的构建与哈希地址计算：给定的散列函数H(key) = key % 13，计算散列地址为1的链表中包含哪些记录，由于19、68和79模13余数均为1，所以散列地址为1的链中有3个记录。 9. 哈希查找的理解：哈希函数的复杂度并非越复杂越好，而是要尽可能减小冲突，选项A和B过于绝对；选项C强调哈希函数的选择应根据具体情况调整，合理即可；选项D指出删除元素时，需要考虑冲突解决方案，不仅仅是简单删除。 10. 链地址法与散列表大小：链地址法构建的散列表需要根据哈希函数确定链表的数量。对于H(key) = key % 17，链表数量为17，选项A正确；链表下标范围为0到16，对应数组下标从0开始，选项C正确。 11. 最后两个问题涉及具体实现细节，散列表的链表数量是17，下标范围是0到16。选项C和D符合题意，但由于题目可能需要具体到链表数量的整数形式，所以答案可能是16，但题目未明确，这里保留为C。 本练习题围绕查找算法、数据结构、哈希表以及平衡树的维护等内容展开，旨在考察学生的理论理解和实践应用能力。