数据结构与算法

数组在内存中连续存储，支持 O(1) 随机下标访问，但插入删除需整体搬移为 O(n)，扩容需申请新空间复制，缓存局部性好。链表节点离散存储并用指针串联，插入删除已知位置时 O(1)，但访问需从头遍历 O(n)，每节点有指针额外开销且缓存不友好。选型上读多写少、大小稳定优先数组（含动态数组 vector）；频繁任意位置增删、长度剧烈变化或需无锁队列等结构时选链表。扩展点：双向链表支持 O(1) 删除给定节点；跳表用空间换时间在链表上实现 O(log n) 查找，是 Redis 有序集合的底层选择之一。

哈希表通过哈希函数把键映射到桶数组下标，实现平均 O(1) 的插入删除与查找。冲突解决方案主要有两类：开放寻址在冲突时按探测序列（线性、平方、双重哈希）寻找下一个空位，缓存友好但删除需打墓碑标记且易聚集；链地址法把同桶元素串成链表，实现简单、负载因子可超 1，链表过长时转化为红黑树，Java HashMap 与 Redis dict 均采用此路线并以此优化最坏复杂度。工程要点包括负载因子触发的扩容再哈希、扰动函数让高位参与运算、以及设计良好的哈希函数减少聚集。最坏情况退化为 O(n)，答题时要主动提到平均与最坏的差别。

二叉搜索树中序有序、查找路径取决于树高，若按有序序列插入会退化成链表，操作变为 O(n)，因此需要旋转操作维持平衡把树高压到 O(log n)。AVL 严格平衡任意两子树高差不超 1，查询更快但插入删除旋转频繁，适合查询密集场景；红黑树用颜色约束保证最长路径不超最短两倍，是近似平衡，改写次数更少且最多两次旋转恢复，综合性能好，故 Linux 内核、C++ map、Java TreeMap、epoll 底层都用红黑树。回答时给出两者规则差异与「查询选 AVL、增删与综合选红黑树」的结论，并点出 B 树为磁盘多叉平衡结构用于数据库索引，可体现知识广度。

DFS 深度优先沿一条路径走到底再回溯，用递归或显式栈实现，空间为 O(h) 树高；适合找所有解、路径搜索、拓扑排序、判环、连通分量与回溯类问题（全排列、组合、子集）。BFS 广度优先逐层扩散，用队列实现，空间 O(w) 为最大层宽；特点是最先到达即最短，适合无权图最短路径、层次遍历、多源扩散与状态图最小步数。两者时间复杂度同为 O(V+E)。加权图最短路径需 Dijkstra（非负权）或 Bellman-Ford（可负权）。答题时用「迷宫最短路用 BFS、所有路径用 DFS」这类对比例子并说明空间开销差异即可完整。

稳定性指相等元素排序后相对次序不变，多关键字级联排序（先按 B 再按 A）依赖它。快排平均 O(n log n)、原地但最坏 O(n^2) 且不稳定，工程上用随机化或三数取中规避退化，小段切换插入排序；归并稳定且最坏仍 O(n log n)，但需 O(n) 辅助空间，链表排序与外部排序首选；堆排序原地 O(n log n) 不稳定，缓存局部性差；插入排序在近有序数据上接近 O(n)，是混合排序的基底；计数、桶、基数排序以线性时间处理整数或定长键等受限场景。语言内置 sort 多为优化混合算法，如 Python 的 Timsort、C++ introsort。答出复杂度表并能解释内省与混合策略是加分项。