第 3 章
数据结构与算法
1. 数组和链表有什么区别？什么时候用哪个？
数组在内存里是一块连续空间，靠"首地址 + 下标 × 元素大小"直接算出任意元素的位置，所以随机访问是 O(1)；但插入删除要把后面的元素整体挪动，是 O(n)，而且容量固定，扩容得重新申请一块更大的空间再整体拷贝过去。链表每个节点额外存一个指向下一个节点的指针，节点在内存里可以散落各处，插入删除只要改几个指针，是 O(1)——前提是你已经拿到了那个位置的节点；但查找必须从头一个一个走，是 O(n)。
除了复杂度，还有个常被忽略却实际影响很大的差异：缓存友好性。数组元素挨着放，CPU 从内存取数据时是按缓存行（通常 64 字节）成批取的，取一个就顺带把邻居也装进了缓存，遍历时几乎每次都命中；链表节点散落在堆上各处，每跳一个节点就可能是一次缓存未命中。所以实测中即便理论复杂度相同，数组遍历往往比链表快好几倍。
选择标准是：读多写少、需要按下标访问，用数组；频繁在中间插入删除、且已经持有位置引用，用链表。实际工程里数组（动态数组、vector、ArrayList）用得远多于链表，链表更多是作为其它结构的组成部分出现——哈希表的冲突链、LRU 的双向链表都是。
2. 栈和队列有什么区别？各举一个应用场景？
栈是后进先出，只在一端进出；队列是先进先出，一端进另一端出。
栈最典型的场景是函数调用。每调用一个函数就压入一个栈帧，存局部变量、参数和返回地址，函数返回就弹出。之所以用栈，是因为调用关系天然是嵌套的：最后被调用的函数一定最先返回。递归爆栈、看异常堆栈，看的都是这个结构。另一类场景是需要"回到上一步"的问题——括号匹配、表达式求值、浏览器后退、DFS 的非递归实现。
队列的典型场景是任务缓冲。生产者往队尾放，消费者从队头取，先来的先被处理，用来削峰填谷和解耦，消息队列、线程池的任务队列、操作系统的就绪队列都是这个模型。BFS 用队列，也是因为要保证按层次的先后顺序访问。
3. HashMap 底层原理是什么？哈希冲突怎么解决？
底层是一个桶数组。存 key-value 时先对 key 算哈希值，再对数组长度取模得到下标，直接放进那个桶里。查找时同样算一次就定位到桶，不用从头遍历，平均 O(1)。
问题在于不同的 key 可能算出同一个下标，这就是哈希冲突。鸽笼原理决定了它无法避免，只能处理，办法分两类。
链地址法给每个桶挂一条链表，冲突的元素往后追加，查找时先定位桶再沿链比较。Java 8 的 HashMap 在链表长度超过 8 且数组长度不小于 64 时会把链表转成红黑树，把极端情况下的 O(n) 压到 O(log n)，防的是构造大量哈希碰撞的攻击。
开放地址法不挂链，冲突了就按某种规则探测下一个空位，有线性探测、二次探测、双重哈希几种。它省掉了指针开销、缓存也更友好，但删除很麻烦——不能直接把位置置空，否则会截断探测链让后面的元素查不到，必须放一个墓碑标记。
还有个关键机制是扩容。装载因子等于元素个数除以桶数组长度，超过阈值（Java 里是 0.75）就把数组扩大一倍并重新分配所有元素。因为桶越挤冲突越多、链越长，O(1) 就退化了。0.75 是空间和冲突概率之间的折中，太小浪费内存，太大冲突飙升。
面试常追问"为什么数组长度取 2 的幂"：对 2 的幂取模等价于跟长度减一做按位与，位运算比取模快得多；而且扩容时元素要么留在原位、要么整体后移旧长度个位置，可以省掉重新计算哈希。
4. 顺序存储和链式存储有什么区别？
这是数据结构的两种物理存储方式，跟逻辑结构是两个维度的事——同一个逻辑结构（线性表、树、图）既可以顺序存也可以链式存。
顺序存储用一块连续内存，元素之间的逻辑关系靠位置隐含表达，第 i 个元素的后继就在 i+1 的位置，不需要额外存指针。链式存储用指针显式表达关系，节点可以任意分布。
落到具体结构上：线性表顺序存是数组、链式存是链表；树顺序存是完全二叉树的数组表示（下标 i 的左右孩子在 2i+1 和 2i+2，堆就是这么存的）、链式存是每个节点带左右孩子指针；图顺序存是邻接矩阵、链式存是邻接表。
取舍规律在哪种逻辑结构上都一样，第 1 题讲数组和链表时已经说过——那本来就是这两种存储方式落在线性表上的具体形态。真正要建立的意识是：换成树或者图，同一组取舍会原样再出现一遍。
5. 二叉树有哪些基本性质？深度为 5 的二叉树最多有多少个节点？
几条常考的性质：第 i 层最多有 2^(i-1) 个节点；深度为 k 的二叉树最多有 2^k − 1 个节点，也就是满二叉树的情况；对任意二叉树，叶子节点数 n₀ 等于度为 2 的节点数 n₂ 加一；n 个节点的完全二叉树深度是 ⌊log₂n⌋ + 1。
深度为 5 就是每层都填满，1 + 2 + 4 + 8 + 16 = 31，也就是 2⁵ − 1 = 31 个。
n₀ = n₂ + 1 这条不太直观，推一遍就清楚了。从节点数看，总数 n = n₀ + n₁ + n₂；从边数看，每个节点除了根都恰好有一条边连向父亲，所以边数是 n − 1，而边数又等于所有节点的度之和，也就是 0×n₀ + 1×n₁ + 2×n₂。两个式子联立消掉 n₁，就得到 n₀ = n₂ + 1。
要留意深度的起算方式：这里按根为第 1 层算，有些教材把根算第 0 层，同样"深度为 5"就变成 6 层了。笔试遇到先看题目怎么定义。
6. 二叉树有哪几种遍历方式？前序和中序能唯一确定一棵树吗？
前序（根左右）、中序（左根右）、后序（左右根），三者的差别只在什么时候访问根，左右子树的相对顺序始终是先左后右。加上层序遍历，一共四种。前三种天然适合递归实现，层序则要借助队列。
前序加中序能唯一确定一棵二叉树。原理是前序的第一个元素一定是根，拿这个根去中序里找位置，它左边的全属于左子树、右边的全属于右子树，于是知道了左右子树各有多少节点，就能在前序里把对应区间切出来，递归下去。后序加中序同理，只是根在后序的最后一个。
但前序加后序不行。这两种遍历里根都在端点上，缺了中序就没法确定左右子树的分界——当一个节点只有一个孩子时，前序和后序都区分不出这个孩子是左孩子还是右孩子。中序的作用正是提供这个分界信息。
三种遍历的用途也不同：前序适合复制一棵树和序列化，先建根再建子树；中序在二叉搜索树上遍历出来正好是有序序列；后序适合释放整棵树、计算子树的汇总值，因为必须先处理完孩子才能算父亲。
7. 二叉搜索树的查找时间复杂度是多少？最坏情况呢？
BST 的性质是左子树所有节点都小于根、右子树所有节点都大于根，且左右子树本身也是 BST。查找时把目标跟当前节点比一下就能决定往左还是往右，每比较一次就排除掉一整棵子树，所以复杂度取决于树高，平均是 O(log n)。
最坏是 O(n)。当插入的数据本身有序，比如按 1、2、3、4、5 的顺序插，每个新节点都挂到右边，树退化成一条链表，查找就得从头走到尾。而有序插入在实际中一点都不罕见——按自增 ID 插入、按时间戳插入都是这个模式，所以这不是理论上的极端情况，而是很容易撞上的常态。
这正是引出平衡二叉树的原因：光有 BST 的排序性质不够，还得有机制保证树不长歪。
8. 为什么需要平衡二叉树？红黑树比 AVL 树好在哪？
需要平衡，是因为 BST 的所有优势都建立在"树高是 log n"这个前提上，一旦退化成链，查找、插入、删除全部掉到 O(n)。平衡的本质就是通过旋转操作，在每次插入删除后强制把树高控制在 O(log n)。
AVL 树的平衡条件很严：任意节点的左右子树高度差不超过 1。红黑树松得多，靠五条规则——节点非红即黑、根是黑、叶子（NIL 空节点）是黑、红节点的孩子必须是黑、从任一节点到它所有叶子的路径上黑节点数相同——把最长路径压在最短路径的两倍以内。
| AVL 树 | 红黑树 | |
|---|---|---|
| 平衡程度 | 严格，左右高度差不超过 1 | 宽松，最长路径不超过最短的 2 倍 |
| 树高 | 更矮，查找更快 | 略高，查找略慢 |
| 插入删除 | 可能需要 O(log n) 次旋转一路回溯到根 | 插入最多 2 次旋转，删除最多 3 次 |
| 适合 | 查多写少 | 增删频繁 |
红黑树好在哪要看场景——它牺牲了一点查询效率，换来插入删除时维护成本的稳定。AVL 为了守住高度差不超过 1，一次删除可能触发从叶子一路到根的连续旋转；红黑树因为条件松，绝大多数情况改改颜色就完事，旋转次数有常数上界。所以在增删改查混合的通用场景里红黑树更划算，Java 的 TreeMap、C++ 的 std::map、Linux 内核的进程调度和虚拟内存区间管理用的都是它。如果是构建一次之后基本只查的场景，AVL 反而更合适。
9. B+ 树为什么适合做数据库索引？
关键前提是数据库索引存在磁盘上，不在内存里。磁盘随机 IO 的代价比内存访问高好几个数量级，所以索引结构的目标不是"减少比较次数"，而是"减少磁盘 IO 次数"，也就是压低树高。
红黑树、AVL 这类二叉结构每个节点只有两个分支，n 个数据的树高是 log₂n，一百万条数据要走二十层，每层一次磁盘 IO 就是二十次。B+ 树是多路平衡树，一个节点对应一个磁盘页（InnoDB 里是 16KB），一页能塞下几百上千个键，分支数就是几百上千，树高变成以几百为底的对数。同样一百万条数据三层就够了，加上根节点常驻内存，实际只需要一两次磁盘 IO。
B+ 树相对 B 树还有两处专为数据库设计的改动。一是只有叶子节点存数据，内部节点只存键和指针，同样大小的一页能容纳更多的键，扇出更大、树更矮。二是所有叶子节点用链表串起来，范围查询只要定位到起点，顺着叶子链表往后扫就行，不用回到根节点重新查。B 树的数据散落在各层节点上，做范围查询要在树里反复上下走，效率差很多。而范围查询、排序、分页在数据库里恰恰是高频操作。
10. 堆是什么？堆排序怎么做？Top-K 问题怎么解？
堆是一棵完全二叉树，满足堆序性质：大顶堆中任意节点都不小于它的孩子，小顶堆反之。注意它只约束父子关系，不约束兄弟之间，所以堆是部分有序的——能 O(1) 拿到最值，但不能像 BST 那样有序遍历。因为是完全二叉树，堆通常用数组存，下标 i 的左右孩子在 2i+1 和 2i+2、父亲在 (i−1)/2，一个指针都不用。
核心操作是上浮和下沉。插入时放到数组末尾，然后跟父亲比较、不满足堆序就交换，一路上浮，O(log n)；删除堆顶时把末尾元素挪到堆顶，然后跟较大的那个孩子交换、一路下沉，同样 O(log n)。
堆排序分两步。先把无序数组原地建成大顶堆，做法是从最后一个非叶子节点开始依次下沉，这一步是 O(n) 而不是 O(nlogn)；然后重复"把堆顶跟当前末尾元素交换、堆大小减一、对新堆顶下沉"，每次都把当前最大值固定到数组末尾，n 轮之后整个数组有序。总复杂度 O(nlogn)，空间 O(1)，但不稳定。
Top-K 用堆是最经典的解法，而且有个反直觉的点：求最大的 K 个数要用小顶堆，不是大顶堆。维护一个大小为 K 的小顶堆，遍历数据时拿新元素跟堆顶（也就是当前这 K 个里最小的）比，比它还小就直接丢弃，比它大就替换堆顶再下沉。这样堆里始终是目前见过的最大的 K 个，复杂度 O(n log K)，空间只要 O(K)。空间这一点才是它的真正价值——数据量大到内存装不下时（比如从十亿条日志里找访问量前 100 的 IP），排序法根本跑不起来，堆法只需要一百个元素的空间。
11. 八大排序算法怎么对比？哪个排序的比较次数与初始顺序无关？
| 算法 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
比较次数与初始顺序无关的是选择排序。它每一趟都要在剩下的未排序区间里完整扫一遍找最小值，不管数据是已经有序还是完全逆序，第 i 趟就是雷打不动的 n−i 次比较，总共 n(n−1)/2 次。冒泡和插入都会被初始顺序影响——数据接近有序时插入排序只要 O(n)，冒泡加了提前退出标志也能 O(n)。
顺带一提，选择排序虽然比较次数固定，交换次数却极少（每趟最多一次），这是它唯一的优点：适合交换代价远大于比较代价的场景。
12. 快排的思路是什么？最坏时间复杂度？怎么优化？
分治。选一个基准值 pivot，把数组分成"小于 pivot"和"大于 pivot"两部分，pivot 归位到中间，然后对左右两段递归。跟归并排序对比着看很清楚：快排是先划分后递归，划分时干活，递归回来就完事了；归并是先递归后合并，合并时才干活。
最坏是 O(n²)，发生在每次划分都极度不均匀的时候。如果固定取第一个元素做 pivot，遇到已经有序的数组，每次划分都是一边 0 个、一边 n−1 个，递归深度变成 n，直接退化成冒泡。有序输入在实际中很常见，所以这是必须处理的问题，不是理论上的极端。
几个常见优化：随机选 pivot 或者三数取中（取首、中、尾三个数的中位数），把最坏情况打散成概率极低的事件；小区间（长度小于十几）改用插入排序，因为小数据量下插入排序的常数更小；三路划分处理大量重复元素，把等于 pivot 的那一段单独归位、不再参与递归，否则全部相同的数组也会退化成 O(n²)；先递归较短的那一半、较长的一半用循环处理，把递归栈深度控制在 O(log n)。
13. 归并排序是稳定的吗？空间复杂度是多少？
稳定的。合并两个有序子数组时，遇到左右两边元素相等的情况，只要规定优先取左边的（写成 if (left[i] <= right[j])），原本靠前的元素就仍然排在前面。稳定性完全取决于这个等号写在哪一边——写成 < 让相等时取右边，就变成不稳定的了。
空间复杂度是 O(n)，因为合并必须在辅助数组里进行。不能原地合并，边写边覆盖会毁掉还没读的数据。实现上通常只申请一个跟原数组等大的辅助数组反复复用，而不是每层递归都申请一份。递归栈还要 O(log n)，但被 O(n) 盖过去了。
正因为空间开销大，归并在内存排序里常输给快排。但它有两样快排给不了的东西：最坏情况也保持 O(nlogn)，以及天然适合外部排序——数据大到内存装不下时，可以先把数据切成若干块分别排好写回磁盘，再做多路归并，这是快排做不到的。
14. 哪些排序是稳定的？稳定性为什么重要？
稳定指的是排序前后，值相等的元素相对顺序不变。稳定的有冒泡、插入、归并、基数（以及计数、桶排序），不稳定的有选择、希尔、快排、堆排。
不稳定的根源都是长距离交换：选择排序把最小值跟当前位置的元素直接对调，中间跨过的相等元素顺序就乱了；快排的分区、堆排的堆顶与末尾交换、希尔的跨增量比较，都是同类问题。而冒泡和插入只在相邻元素之间比较交换，相等时不交换，顺序自然保得住。
稳定性重要，是因为它让多关键字排序可以拆成多趟单关键字排序。比如要"先按部门排、部门内按工资排"，可以先按工资排一遍，再用稳定排序按部门排一遍——第二趟不会打乱同部门内已经排好的工资顺序。如果第二趟用的是不稳定排序，第一趟就白做了。基数排序能成立靠的正是这个性质：它按位从低到高排若干趟，每趟都必须稳定，否则低位的排序结果会被高位那趟毁掉。
15. 邻接矩阵和邻接表有什么区别？各自适用什么场景？
邻接矩阵是一个 n×n 的二维数组，matrix[i][j] 表示 i 到 j 有没有边，带权图就存权值。邻接表是给每个顶点挂一条链表或数组，存它的所有邻居。
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 空间 | O(n²)，跟边数无关 | O(n + e) |
| 判断两点之间有没有边 | O(1) | O(该点的度) |
| 遍历某点的所有邻居 | O(n)，要扫一整行 | O(该点的度) |
| 增删边 | O(1) | 删边要遍历链表 |
选择只看一件事：图是稠密还是稀疏。稠密图（边数接近 n²）用邻接矩阵，空间没浪费，还能 O(1) 查任意两点是否相连；稀疏图用邻接表，n 个顶点只有几条边时，邻接矩阵会有绝大多数格子存着 0，纯属浪费。实际问题里的图大多是稀疏的——社交网络、路网、依赖图，每个点的邻居数都远小于总点数，所以邻接表是更常见的选择。
补两个细节：无向图的邻接矩阵是对称的，可以只存上三角省一半空间；邻接矩阵在图算法里还有个特殊用途，矩阵乘法能直接算出定长路径的条数，Floyd 算法也是基于矩阵形式写的。
16. BFS 和 DFS 有什么区别？各用什么数据结构？
BFS 从起点开始一层一层向外扩展，先访问所有距离为 1 的点，再访问距离为 2 的，用队列——先进先出正好保证了按距离由近及远的顺序。DFS 沿一条路走到底，走不通再回退换一条，用栈；递归实现时用的是函数调用栈，本质一样。
时间复杂度都是 O(n + e)（邻接表存储），两者都需要一个 visited 标记防止重复访问和死循环。差别在空间和用途上。BFS 的队列里同时存着一整层的节点，空间是 O(最宽一层的宽度)；DFS 的栈深度是当前路径长度，空间是 O(最深路径)。所以宽而浅的图用 DFS 省空间，深而窄的图用 BFS 省空间。
用途上最关键的区别是：无权图求最短路径必须用 BFS。因为 BFS 是按距离递增的顺序扩展的，第一次访问到某个点时走过的边数一定最少。DFS 第一次到达某点走的可能是绕远的路，要求最短还得把所有路径都试一遍。反过来，枚举所有路径、判断连通性、拓扑排序、找环这类问题，DFS 写起来更自然。
17. Dijkstra 算法的思路是什么？能处理负权边吗？
Dijkstra 求单源最短路径，思路是贪心加逐步确定。维护每个点的当前最短距离估计，起点为 0、其余为无穷大；每轮从还没确定的点里挑出距离估计最小的那个，认定它的估计值就是最终答案，然后用它去松弛所有邻居——如果"经由它到某个邻居"比该邻居当前的估计更短，就更新。重复 n 轮，所有点的最短距离就都确定了。
用普通数组找最小值是 O(n²)，用小顶堆优化到 O(e log n)，稀疏图上快很多。
不能处理负权边。它的正确性完全依赖一个假设：当前估计最小的那个点，其估计值已经是最终答案，因为从它再往外走只会让路径变长。有了负权边这个假设就崩了——一条现在看起来更长的路，后面可能接着一条负权边使总长反而更短，而那个点已经被"确定"了，不会再更新。有负权边要用 Bellman-Ford（对所有边松弛 n−1 轮，O(ne)，还能顺带检测负权环）或它的队列优化版 SPFA。
顺带区分一下：Dijkstra 是单源到所有点，Floyd 是所有点对之间，三重循环 O(n³)，能处理负权边但不能有负权环。
18. O(nlogn) 比 O(n²) 快多少？
大 O 描述的是增长趋势，也就是数据规模翻倍时耗时怎么变：O(n²) 的算法数据翻一倍耗时变四倍，O(nlogn) 大约变两倍多一点。数据量越大，差距拉得越开。
代入具体数字最直观。n = 1000 时，n² 是一百万，n log₂n 大约一万，差 100 倍；n = 100 万时，n² 是一万亿，n log₂n 大约两千万，差了五万倍。前者在现代 CPU 上要跑十几分钟，后者几十毫秒就完事。这就是为什么数据量一上来，冒泡和快排就不是"慢一点"的关系，而是"能不能跑完"的关系。
但要注意大 O 忽略了常数和低阶项，小数据量下结论可能反过来。插入排序是 O(n²)，可它常数极小又缓存友好，n 小于几十时比快排还快——所以工业级的排序实现（Java 的 Arrays.sort、C++ 的 introsort）都是混合的：主体用快排或归并，递归到小区间就切成插入排序。分析复杂度是为了判断规模上限，不是拿来教条地选算法。