12. 顺序存储和链式存储有什么区别？
顺序存储把数据放在连续的内存空间中，比如数组；链式存储的数据可以分散在不同的内存位置，然后通过指针连接起来。
- 顺序存储最大的优势是随机访问快，可以通过下标直接找到元素；
- 链式存储则更灵活，插入和删除节点时不需要大量移动其他元素。
但链表并不是所有情况下都比数组好，因为链表虽然插入删除方便，但访问第 i 个元素需要从头开始遍历，时间复杂度是 O(n)。
[!TIP] 实际选择要看需求：需要频繁随机访问就更适合数组，需要频繁插入删除可以考虑链表。
13. 循环队列如何计算元素个数？
普通数组实现队列时，如果不断出队和入队，前面的位置可能被浪费掉，所以可以把数组首尾连接起来，形成循环队列。
循环队列中，队头和队尾指针不断向后移动，到数组末尾之后再回到开头，通常通过取模实现。
如果采用"牺牲一个存储空间"的实现方式，容量为 N，那么元素个数可以通过：
(rear - front + N) % N来计算。这里加 N 是为了避免 rear - front 出现负数。
14. 循环队列如何判断队空和队满？
循环队列中，通常使用 front 表示队头，rear 表示队尾。
在常见的"牺牲一个空间"的实现方式中：
- 队空：
front == rear - 队满：
(rear + 1) % N == front
为什么要牺牲一个空间？因为如果不这样做，队空和队满时可能出现完全相同的指针状态，无法区分。
[!TIP] 牺牲一个位置，就是人为留出一个状态用来区分"空"和"满"。
15. B树和B+树有什么区别？为什么数据库常用B+树？
B树和B+树都是多路平衡搜索树，主要用于解决数据量很大、无法全部放入内存时的高效查找问题。
最大的区别是：
- B树的非叶子节点和叶子节点都可以存储数据；
- B+树只有叶子节点存储真正的数据，非叶子节点主要存储索引；
- B+树的叶子节点通常通过链表连接起来。
数据库更常使用B+树，因为：
- 数据库很多时候不仅要查一个数据，还要进行范围查询。B+树的叶子节点按照顺序连接起来，所以范围查询非常方便；
- B+树的非叶子节点只存索引，可以放更多的索引项，从而降低树的高度，减少磁盘 IO。
16. Prim、Kruskal、Dijkstra、Floyd 分别解决什么问题？
- Prim 和 Kruskal 解决的是最小生成树问题，也就是在保证所有节点连通的情况下，选择一些边，使得总权重最小。Prim 是从某个节点开始，不断选择连接当前集合和外部节点的最小边；Kruskal 则是把所有边按照权重排序，然后不断选择最小的边，同时避免形成环。
- Dijkstra 解决的是单源最短路径问题，也就是从一个起点出发，求它到其他节点的最短距离。
- Floyd 解决的是多源最短路径问题，可以一次性求出任意两个节点之间的最短距离。
[!TIP] 可以直接记成：Prim/Kruskal → 最小生成树；Dijkstra → 一个点到其他点；Floyd → 任意两个点之间。
17. 邻接表和邻接矩阵有什么区别？
邻接矩阵使用二维数组表示图。如果顶点有 V 个，就需要 V × V 的空间，所以空间复杂度通常是 O(V²)。它的优点是判断两个节点之间有没有边非常快，直接访问矩阵中的对应位置即可。
邻接表则是每个节点维护一个列表，里面存放和它相连的节点，所以空间复杂度通常是 O(V+E)。
[!TIP] 稠密图，也就是边很多，可以考虑邻接矩阵；稀疏图，也就是边比较少，更适合邻接表。
18. 什么是 Top-K 问题？常用什么方法？
Top-K 就是从大量数据中找出最大的 K 个或者最小的 K 个元素。
最简单的方法就是把所有数据排序，然后取前 K 个，但是如果数据量特别大，全部排序其实比较浪费。
比如有 100 万个数字，只需要找最大的 10 个数字，就没有必要把 100 万个数字全部排序。这时候可以维护一个大小为 10 的小顶堆：
- 堆中保存当前最大的 10 个数；
- 新数据比堆顶大，就替换堆顶；
- 最后堆中的 10 个元素就是最大的 10 个。
这样比全部排序更加高效。
19. 什么是数据结构？为什么需要数据结构？
数据结构就是组织和存储数据，并支持对数据进行高效操作的一种方式。
同样的数据，如果采用不同的数据结构，操作效率可能差别非常大：
- 数组适合随机访问；
- 链表适合插入和删除；
- 栈适合后进先出的场景；
- 队列适合先进先出的场景；
- 哈希表适合快速查找；
- 树适合表示层次关系。
[!TIP] 数据结构本质上就是研究：数据应该怎么组织，才能让我们更高效地使用它。
20. 什么是平衡二叉树？有什么优势？
普通二叉搜索树虽然查找平均情况下比较快，但如果插入的数据本身接近有序，比如依次插入 1、2、3、4、5，它可能会退化成一条链，这时候查找效率就从原来的接近 O(log n) 下降到 O(n)。
平衡二叉树就是通过限制树的高度，让左右子树尽量保持平衡，避免树退化。
[!TIP] 它的核心优势就是：控制树的高度，从而保证查找、插入、删除操作能够保持较好的效率。
21. 什么是 AVL 树？它如何保持平衡？
AVL 树是一种比较严格的平衡二叉搜索树，它要求每个节点的左右子树高度差不能超过 1。这个高度差叫做平衡因子。
当插入或者删除节点之后，如果某个节点的平衡因子超过允许范围，就说明树失衡了，需要通过旋转来恢复平衡。主要有四种情况：
- LL：右旋；
- RR：左旋；
- LR：先左旋，再右旋；
- RL：先右旋，再左旋。
[!TIP] AVL 树的核心就是：利用旋转控制树的高度，让二叉搜索树不要退化。
22. 什么是拓扑排序？有什么应用？
拓扑排序用于有向无环图（DAG），它要求对于一条边 u → v，u 必须排在 v 前面。
它实际上是在解决一种"先后依赖关系"。例如大学课程：高等数学 → 机器学习，那么学习机器学习之前必须先学习高等数学。拓扑排序就可以把这种依赖关系转换成一个合理的执行顺序。
常见实现方法有入度法和 DFS。
23. 什么是并查集？有什么作用？
并查集是一种用来维护多个不相交集合的数据结构，主要有两个操作：
- find：查找一个元素属于哪个集合；
- union：把两个集合合并。
例如有很多节点，需要不断判断"节点 A 和节点 B 是否连通"，就可以使用并查集。为了提高效率，通常会使用路径压缩和按秩合并，使得大量操作下来效率非常高。
它常用于：
- 判断连通性；
- Kruskal 最小生成树；
- 网络连接问题。
24. 如何判断一棵二叉树是否平衡？
可以递归计算每个节点的左右子树高度。
对于一个节点：
- 如果左子树高度和右子树高度相差超过 1，那么这棵树就不平衡；
- 同时还要继续判断它的左右子树是否平衡。
比较高效的方法是采用自底向上的方式计算高度：如果某个子树已经不平衡，就直接返回特殊值，不需要继续计算。这样可以做到 O(n) 的时间复杂度。
25. 什么是平衡二叉树？
平衡二叉树主要是为了防止二叉搜索树退化成链表。它要求树中每个节点的左右子树高度保持在一定范围内，这样树的整体高度不会太高。
例如 AVL 树要求左右子树高度差不超过 1，而红黑树的平衡要求相对宽松一些。
[!TIP] 所以"平衡"的核心不是要求左右完全一样高，而是：让树的高度保持在一个合理范围内，避免查找效率退化。
26. 二叉树中如何寻找最大值？
如果是普通二叉树，节点之间没有大小关系，所以不能像二叉搜索树那样直接判断应该去左边还是右边。
最简单的方法就是遍历整棵树，在遍历过程中维护一个 max，每访问一个节点就和当前最大值比较。因此需要访问所有节点，时间复杂度是 O(n)，额外空间取决于使用递归还是队列等方式。
[!TIP] 如果题目明确说是二叉搜索树，那么情况就不一样了：二叉搜索树中右边的节点更大，可以直接沿着右子树寻找最大值。
留言板