📋 摘要
- C++ 数据结构面试高频问答，每题保留回答重点与扩展知识
- 详细原理解析与代码示例见 03-Resources/cpp/C++ 数据结构
- 持续补充中
1. 数组和链表有什么区别？各自适用场景？
📋 回答重点
- 数组内存连续、链表指针串联，这是所有差异的根源。
- 数组随机访问 O(1)，插入/删除（中间）O(n)；链表相反，访问 O(n)，已知节点处增删 O(1)。
- 数组缓存友好（cache line 命中），链表指针跳跃 cache miss 频繁。
- 数组空间紧凑无额外指针，链表每节点多 1~2 个指针。
- 数组适合频繁按下标读、元素稳定；链表适合频繁头/中部增删、规模动态不可预估。
扩展知识
- C++ 对应容器：
std::vector（数组）、std::list（双向链表）、std::forward_list（单向链表）。 vector尾部插入均摊 O(1)，扩容时迭代器全部失效。- 现代 CPU 下 vector 遍历远快于 list，工程上多数场景默认选 vector。
- 详细讲解：03-Resources/cpp/C++ 数据结构
2. 用 C++ 实现一个单链表（增删查改）？
📋 回答重点
- 节点
struct ListNode { int val; ListNode* next; }，链表类维护head指针。 - 尾部插入需遍历到末尾；按值查找遍历比较；删除需找到前驱。
- 删除用「指向指针的指针」（
ListNode**）可统一处理删头节点与中间节点。 - 插入先接新节点
next再断前驱，避免后半段丢失。 - 析构函数遍历释放全部节点，防内存泄漏。
扩展知识
- 高频变体：反转链表（迭代/递归）、链表中点（快慢指针）、判断环（快慢指针相遇）、合并两个有序链表。
- 单向链表删除给定「非尾」节点可用「值覆盖 + 删除后继」技巧，O(1)。
- 详细讲解：03-Resources/cpp/C++ 数据结构
3. 栈和队列有什么区别？如何用栈实现队列？
📋 回答重点
- 栈是 LIFO（后进先出），队列是 FIFO（先进先出）。
- C++ 中
std::stack/std::queue都是容器适配器，默认底层std::deque。 - 栈操作
push/pop/top，队列操作push/pop/front/back。 - 两个栈实现队列：
in栈入队，out栈出队；out空时把in全倒入out，栈顶即队首。 - 每个元素最多搬移两次，出队均摊 O(1)。
扩展知识
- 队列实现栈：入栈时新元素入队，再把前
size-1个元素出队再入队，使新元素总在队首。 - 栈应用：函数调用栈、括号匹配、DFS；队列应用：BFS、任务调度、消息队列。
- 单调栈/单调队列是高频进阶考点（如「每日温度」「滑动窗口最大值」）。
- 详细讲解：03-Resources/cpp/C++ 数据结构
4. 哈希表的原理？如何解决哈希冲突？
📋 回答重点
- 哈希函数把 key 映射到数组下标，理想 O(1) 定位。
- 不同 key 映射到同一下标即哈希冲突，冲突不可避免。
- 链地址法：每槽挂链表（
unordered_map），冲突追加到链表。 - 开放定址法：冲突时按探测序列找下一个空槽，缓存友好但删除需墓碑。
- 平均 O(1) 前提是哈希均匀 + 负载因子受控，最坏退化 O(n)。
扩展知识
- 探测序列：线性探测、二次探测、双重哈希。
- 链过长可转红黑树（Java）或 rehash（C++），保最坏 O(log n) 或摊平。
- 详细讲解：03-Resources/cpp/C++ 数据结构
5. unordered_map 的底层实现原理？
📋 回答重点
- 采用链地址法：桶数组（
vector）+ 每个桶一条单向链表。 - 查找流程：
hash(key)→ 取模定位桶 → 桶内链表顺序查找。 - 负载因子 =
size / bucket_count，超过max_load_factor（默认 1.0）触发 rehash。 - rehash 时桶数翻倍（常取质数），重哈希全部元素，O(n)。
- 平均 O(1) 但无序、内存大、rehash 后迭代器失效。
扩展知识
- 与
map对比：map红黑树有序 O(log n)，unordered_map无序平均 O(1)。 - 已知规模可
reserve(n)预留桶数，避免频繁 rehash。 - 自定义 key 需提供
std::hash<T>特化和operator==。 - 详细讲解：03-Resources/cpp/C++ 数据结构
6. 哈希函数如何设计？什么是哈希碰撞？
📋 回答重点
- 哈希函数把任意 key 映射为桶下标；碰撞指不同 key 得同一哈希值。
- 好哈希三要素：分布均匀（雪崩效应）、计算快、确定性。
- 除留余数法
key % m（m 取质数）、乘法散列、字符串多项式哈希h = h*31 + c。 - 碰撞不可避免（鸽巢原理），目标是最小化而非消除。
- 雪崩效应：输入一位变化引起约一半输出位变化。
扩展知识
- 工程常用：murmurhash、xxhash、FNV-1a。
std::hash对整数基本恒等映射，字符串实现由库决定。- 详细讲解：03-Resources/cpp/C++ 数据结构
7. 堆（优先队列）的原理？如何用堆求 TopK？
📋 回答重点
- 堆是完全二叉树 + 堆序（大顶堆根最大，小顶堆根最小）。
- 数组紧凑存储：节点 i 左子
2i+1、右子2i+2、父(i-1)/2。 - push 上浮 O(log n)，pop 下沉 O(log n)，top 取
a[0]O(1)。 - TopK：维护大小 K 的小顶堆，元素大于堆顶则替换，堆顶即第 K 大。
- 复杂度 O(n log k)，空间 O(k)，可处理流式数据。
扩展知识
- 「第 K 小」用大顶堆；TopK 另一路线是快速选择 quickselect（平均 O(n)）。
- 双堆（大顶 + 小顶）求流式数据中位数。
- 应用：排行榜、Dijkstra 优先队列、定时器。
- 详细讲解：03-Resources/cpp/C++ 数据结构
8. priority_queue 的底层实现？
📋 回答重点
- 容器适配器，底层默认
std::vector，用堆算法维持堆序。 - 只暴露
top/push/pop，不支持遍历和随机访问。 - 模板参数
priority_queue<T, Container, Compare>，默认vector+less（大顶堆）。 std::greater得小顶堆（Compare 语义与直觉相反）。- push/pop O(log n)，top O(1)。
扩展知识
- 自定义比较器：函数对象 / lambda（配 decltype）/ 重载
operator<。 - 不能删任意元素、不能改优先级；需此能力改用
std::set或手写堆 + 懒删除。 - 详细讲解：03-Resources/cpp/C++ 数据结构
9. 二叉树的遍历（前/中/后/层序）如何实现？
📋 回答重点
- 前序「根左右」、中序「左根右」、后序「左右根」、层序逐层从左到右。
- DFS 递归三行模板；迭代需显式栈模拟递归调用栈。
- 中序非递归：一路向左压栈，弹出访问后转向右子树。
- 层序用队列，按层计数（
q.size()）分批处理。 - BST 中序遍历得到有序序列。
扩展知识
- 后序非递归技巧：前序「根右左」再
reverse即后序，或节点加访问标记。 - 前序可序列化树；层序即 BFS，可求树宽度/最短路径。
- 详细讲解：03-Resources/cpp/C++ 数据结构
10. 二叉搜索树 BST 的特点？为什么容易退化？
📋 回答重点
- 左子树全小于根、右子树全大于根，中序有序。
- 查找/插入/删除平均 O(log n)。
- 形态完全由插入顺序决定，有序插入退化成单链。
- 退化后树高 O(n)，所有操作退化 O(n)。
- 解决退化：AVL、红黑树、Treap/Splay。
扩展知识
- C++
std::map/std::set用红黑树正是为避免退化。 - 依次插入 1..5 得全右链，是退化典型例子。
- 详细讲解：03-Resources/cpp/C++ 数据结构
11. 平衡二叉树 AVL 的原理？
📋 回答重点
- 自平衡 BST，任意节点左右子树高度差（平衡因子）≤1。
- 平衡因子 = 左子树高 - 右子树高，正常取值 -1/0/1。
- 插入/删除失衡通过旋转恢复，保证树高 O(log n)。
- 四种失衡：LL 右旋、RR 左旋、LR 先左后右、RL 先右后左。
- 严格平衡，查找最优但插入删除旋转频繁，适合读多写少。
扩展知识
- 失衡节点平衡因子必为 ±2，在最近失衡祖先处旋转一次即可。
- 相比红黑树更矮、查找更快，但写入成本高。
- 详细讲解：03-Resources/cpp/C++ 数据结构
12. 红黑树的特点？为什么 map 用红黑树不用 AVL？
📋 回答重点
- 近似平衡 BST，五性质：非红即黑、根黑、叶子黑、红不连续、黑高一致。
- 由性质推出最长路径 ≤ 2× 最短路径，保证 O(log n)。
- 插入/删除最多常数次旋转 + 重着色，比 AVL 旋转少。
map用红黑树因写入成本更低、整体吞吐更高（读写均衡）。- AVL 只在读远多于写时才更优。
扩展知识
- 红黑树有序性支持
lower_bound、范围查询、按序遍历。 - 应用：
std::map/std::set、Linux CFS、epoll、Java TreeMap。 - 详细讲解：03-Resources/cpp/C++ 数据结构
13. 图的存储方式：邻接矩阵 vs 邻接表？
📋 回答重点
- 邻接矩阵
g[i][j]存边，邻接表每顶点一条链表存邻接点。 - 矩阵空间 O(V²)、查边 O(1)、遍历邻居 O(V)。
- 邻接表空间 O(V+E)、查边 O(deg)、遍历邻居 O(deg)。
- 稠密图用矩阵，稀疏图用邻接表。
- 工程绝大多数图稀疏，邻接表是默认选择。
扩展知识
- 带权图邻接表存
vector<vector<pair<int,int>>>，节点存 (邻接点, 权重)。 - 边列表
vector<tuple<u,v,w>>适合 Kruskal。 - 详细讲解：03-Resources/cpp/C++ 数据结构
14. 图的遍历 BFS 和 DFS？
📋 回答重点
- BFS 用队列逐层扩散，DFS 用栈/递归一路深入回溯。
- BFS 天然求无权图最短路径（首次到达即最短）。
- DFS 适合连通性、环检测、拓扑排序。
- BFS 空间 O(层宽)，DFS 空间 O(树高/递归深度)。
- 递归 DFS 深层图可能爆栈，可改迭代或 BFS。
扩展知识
- 三色标记：白未访问、灰在栈中、黑已结束，灰→灰即发现环。
- 应用：BFS 最短路径、N 度人脉、爬虫；DFS 依赖解析、迷宫、拓扑排序。
- 详细讲解：03-Resources/cpp/C++ 数据结构
15. 跳表的原理？为什么 Redis 用跳表？
📋 回答重点
- 在有序链表上建多层索引，第 0 层完整、上层抽样。
- 查找从最高层跳，不能跳就下沉，O(log n)。
- 空间换时间 + 随机化层高，实现比红黑树简单。
- Redis ZSet 用跳表：有序 + 范围查询 + 排名（span）高效。
- 局部修改、无复杂旋转，并发/持久化更友好。
扩展知识
- 层高随机：约 50% 概率升一层。
- 应用：Redis ZSet、LevelDB/RocksDB MemTable、Lucene 倒排索引。
- 详细讲解：03-Resources/cpp/C++ 数据结构
16. 并查集的原理和适用场景？
📋 回答重点
- 维护不相交集合，每集合一棵树，根为代表元。
find(x)找根 + 路径压缩；unite(x,y)合并 + 按秩。- 路径压缩把沿途节点直接挂根，摊平树高。
- 按秩合并小树挂大树，控制高度增长。
- 两者结合均摊复杂度反阿克曼函数 α(n)，近似 O(1)。
扩展知识
- 应用：图连通性判断、连通分量计数、Kruskal 判环、朋友圈/省份数量、等价关系。
- 只路径压缩是 O(log n) 均摊，两者结合才最优。
- 详细讲解：03-Resources/cpp/C++ 数据结构
17. Trie 树（前缀树）的原理和适用场景？
📋 回答重点
- 多叉树，节点存「字符→子节点」映射，路径即前缀。
- 共享公共前缀压缩空间，前缀查询天然高效。
- 插入/查询 O(m)，m 为字符串长度，与词表规模无关。
- 节点需标记
is_end区分「前缀」与「完整单词」。 - 应用：自动补全、敏感词过滤、IP 路由最长前缀匹配。
扩展知识
- 内存敏感场景用数组
children[26]代替哈希表。 - AC 自动机基于 Trie 做多模式匹配。
- 详细讲解：03-Resources/cpp/C++ 数据结构
18. 布隆过滤器的原理？如何控制误判率？
📋 回答重点
- 位数组 + k 个哈希函数，插入把 k 个位置置 1。
- 查询 k 位全 1「可能存在」，任一 0「一定不存在」。
- 只有假阳性（误判存在），无假阴性，不支持删除。
- 误判率 p ≈ (1 - e^(-kn/m))^k，最优 k = (m/n)ln2。
- m/n 越大误判越低，空间换精度。
扩展知识
- 典型应用：缓存穿透防护、URL 去重、垃圾邮件过滤、LSM 树判断 key 是否可能存在。
- 需删除用计数布隆过滤器。
- 详细讲解：03-Resources/cpp/C++ 数据结构
19. B 树和 B+ 树的区别？为什么数据库索引用 B+ 树？
📋 回答重点
- 都是多路平衡搜索树，矮胖、专为磁盘减少 I/O 设计。
- B 树内部节点也存数据；B+ 树只有叶子存全部数据，内部只存索引。
- B+ 树叶子用双向链表串联，支持高效范围查询和顺序扫描。
- B+ 树每次查找都到叶子，路径等长、性能稳定。
- 数据库索引用 B+ 树：磁盘友好、范围查询快、查询稳定。
扩展知识
- MySQL InnoDB 主键索引即 B+ 树，叶子存完整行；辅助索引叶子存主键值（回表）。
- 红黑树是二叉树，高度高、磁盘 I/O 多，不适合数据库索引。
- 详细讲解：03-Resources/cpp/C++ 数据结构
20. 如何实现 LRU 缓存？
📋 回答重点
- 哈希表 + 双向链表：哈希 O(1) 定位，链表维护访问顺序（头新尾旧）。
- get 命中移到头部（访问也算刷新）；put 满时淘汰尾部（最久未用）。
std::list::splice可 O(1) 移动节点到头部。- 用双向链表而非单向：删除尾节点时能经 prev O(1) 定位新尾。
- get/put 均 O(1)。
扩展知识
- 应用：页面置换、CPU 缓存、Redis
allkeys-lru、InnoDB Buffer Pool。- 常见坑：splice/erase 后同步 map 迭代器；get 命中必须刷新顺序。
- 详细讲解：03-Resources/cpp/C++ 数据结构
21. 线段树的原理和适用场景？
📋 回答重点
- 线段树是平衡二叉树，把区间
[l, r]递归二分，叶子是单点，每个节点存该区间的聚合信息（和/最值）。 - 区间查询与区间更新都是 O(log n)，建树 O(n)，用数组紧凑存储，空间需开 4n。
- 区间更新靠懒惰标记（lazy）：完全覆盖时只打标记、不递归到叶子，访问子区间时再
pushdown下传并清零。 - 能维护任意可合并信息（和、最值、最大子段和等），功能比树状数组强，但常数和代码量更大。
- 适合：区间求和/最值（RMQ）、区间修改、扫描线求矩形面积、主席树求区间第 K 大。
扩展知识
- 下标从 1 起时节点
i的左子2i、右子2i+1；懒标记务必在下传时累加到子节点并清零自身，否则重复计算。 - 进阶：动态开点（值域线段树）、线段树合并、扫描线（矩形面积并/周长并）。
- 对比树状数组：线段树支持区间最值和区间修改，BIT 只支持前缀和类可差分信息。
- 详细讲解：03-Resources/cpp/C++ 数据结构
22. 树状数组（BIT）的原理和适用场景？
📋 回答重点
- 树状数组（Fenwick Tree）维护前缀和，支持 O(log n) 单点更新 + O(log n) 前缀和查询，空间 O(n)、代码仅几行。
- 核心是 lowbit：
lowbit(x) = x & (-x)，取 x 最低位的 1；tree[i]存[i-lowbit(i)+1, i]的和。 - 更新沿
i += lowbit(i)向上累加，查询沿i -= lowbit(i)向下累加，均只经过 O(log n) 个节点。 - 区间和 =
sum(r) - sum(l-1)；配合差分可做「区间更新 + 单点查询」。 - 相比线段树：BIT 更快、更省内存，但只支持前缀和类可差分信息，不支持区间最值/区间修改。
扩展知识
- 经典应用：离散化后求逆序对——倒序遍历，BIT 统计已出现且小于当前值的个数。
- 实现细节：下标从 1 开始，数组大小
n+1。 - 对比线段树：能用 BIT 解决时优先 BIT；需要区间最值/区间修改等通用操作才用线段树。
- 详细讲解：03-Resources/cpp/C++ 数据结构