二叉查找树与哈希表：概念、排序算法与冲突解决

这篇资源主要涵盖了计算机科学中的多个核心知识点，主要源自中科大软件学院历年面试真题，涉及数据结构、算法、操作系统、计算机系统基础知识等多个领域。以下是详细的知识点解析： 1. **二叉排序树**：二叉排序树是一种特殊的二叉树，其中每个节点的值都大于其左子树中的所有节点的值，小于其右子树中的所有节点的值。查找操作在二叉排序树中遵循“左小右大”的原则，具有平均时间复杂度O(logn)。 2. **哈希冲突**：哈希冲突发生在两个或多个不同的输入通过哈希函数映射到同一哈希表位置时。解决哈希冲突的方法包括开放寻址法、链地址法、再哈希法等。 3. **哈希表**：哈希表是一种数据结构，通过散列函数将关键码值映射到特定位置，用于快速查找。常见的散列函数包括直接寻址法、数字分析法、平方取中法、折叠法和随机数法。 4. **哈弗曼树**：哈弗曼树是一种带权路径长度最短的二叉树，用于数据压缩和效率高的编码。构造哈弗曼树通常采用贪心策略，每次合并权值最小的两棵树来构建新树。 5. **排序算法**：面试中可能涉及各种排序算法的时间复杂度和性能比较，例如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。最优的时间复杂度通常是O(nlogn)，如快速排序和归并排序。 6. **深度优先搜索（DFS）**和**广度优先搜索（BFS）**：DFS是沿着树的深度遍历，而BFS则是在每一层上遍历，两者都是图遍历的重要方法。 7. **最小生成树**：在加权无向图中，找到边的权重之和最小的树，常用的算法有Prim算法和Kruskal算法。 8. **平衡二叉树**：如AVL树和红黑树，它们保持左右子树的高度差不超过1，以确保高效的查找性能。 9. **二叉树的存储**：二叉树可以采用顺序存储（数组）或链式存储（链表）。 10. **进程与线程**：进程是程序的执行实例，拥有独立的内存空间；线程是进程内的执行单元，共享进程的内存。 11. **页面置换算法**：如LRU（最近最少使用）、FIFO（先进先出）等，用于处理虚拟内存中页面替换的问题。 12. **磁盘调度算法**：如FCFS（先来先服务）、SCAN、C-SCAN、SSTF（最短寻道时间优先）等，用于优化磁盘读写操作。 这些知识点是计算机科学基础教育的重要组成部分，也是软件开发人员必须掌握的基础理论。了解和熟练应用这些概念对于面试和实际工作至关重要。