查找练习题(答案).docx

【知识点详解】 1. **顺序表的平均查找长度**：在长度为 n 的顺序表上查找任一元素的平均查找长度为 (n+1)/2。这是因为每查找一个元素都有可能在查找过程中遇到，所以平均来说需要查看 (n+1)/2 个元素。 2. **折半查找的平均查找长度**：对于长度为 n 的顺序存储的有序表，如果采用折半查找，在等概率情况下，平均查找长度是 log2n 向上取整减 1。例如，长度为 9 的有序表的平均查找长度为 20/9，长度为 18 的有序表的平均查找长度为 25/9。 3. **折半查找的具体应用**：在题目中，查找有序表（5,12,20,26,37,42,46,50,64）中的元素26，需要进行3次比较，因此答案是B. 3。 4. **有序表的查找效率**：对于长度为 n 的有序表，采用折半查找的时间复杂度为 O(log2n)，这是因为在每次比较后，搜索范围都能减半。 5. **索引查找**：如果主表被均分为12个子表，每个子表长度为12，那么索引查找的平均查找长度为12。这是因为通常索引查找的第一步是在索引表中找到正确的子表，然后再在子表中进行查找，而子表的平均查找长度仍为 log2n 向上取整减1，但这里每个子表长度相同，所以直接查找子表平均需要1次。 6. **二叉排序树查找效率**：在二叉排序树中，平均情况下查找时间复杂度为 O(log2n)，最坏情况下为 O(n)。这意味着树平衡时查找速度快，不平衡时速度慢。 7. **哈希表查找**：线性探测法处理冲突时，如果一个元素的初始哈希地址为 d，下一次的哈希地址为 d+1（如果 d+1 不超过表的长度）。在给定的查找表中，元素64的哈希地址可以通过哈希函数计算，即64%13。 8. **哈希表的查找效率**：线性探测法在最坏情况下，当元素分布导致冲突连续时，平均查找长度接近于表的长度的一半。在给定的哈希表中，地址为0的元素有2个，地址为5的元素有2个。 9. **折半查找的比较次数**：在有序表 (12,18,30,43,56,78,82,95) 中，查找43需要1次比较，查找56需要3次比较。 10. **索引查找的平均查找长度**：当主表被等分为8个子表，每个子表长度为12时，索引查找的平均查找长度为11。 11. **二叉排序树的性质**：在二叉排序树中，左子树上的所有节点值小于等于父节点，右子树上的所有节点值大于等于父节点。中序遍历二叉排序树会得到升序序列。 12. **哈希函数和冲突解决**：在给定的线性表 (18,25,63,50,42,32,90) 中，哈希函数为 H(K) = K % 9，哈希地址为0的元素有2个，地址为5的元素也有2个。 13. **应用题解**： - 对于有序表 (15,26,34,39,45,56,58,63,74,76)，折半查找的平均查找长度可通过计算查找判定树得出。 - 线性表 (38,52,25,74,68,16,30,54,90,72) 生成的二叉排序树，可以手动绘制并计算平均查找长度。 - 线性表 (32,75,29,63,48,94,25,46,18,70) 用除留余数法构造哈希函数 H(K) = K % 11，拉链法处理冲突，可构建哈希表并计算平均查找长度。 以上是关于查找算法的详细解释，包括顺序查找、折半查找、索引查找、二叉排序树查找以及哈希查找的相关知识点，涉及它们的平均查找长度、时间复杂度、具体应用及解决冲突的方法。