📚 课程目录第3章数据结构与算法面试题

第3章：数据结构与算法面试题——STL容器底层、排序算法、哈希表、红黑树

💡 回答逻辑提示：面试中遇到数据结构与算法问题，先明确考察维度（底层结构、时间复杂度、稳定性、应用场景），再按“定义 → 原理 → 对比 → 选型”四步法组织语言，最后结合项目经验佐证。

面试官考察点	是否理解连续内存 vs 链表结构对随机访问、插入删除的影响；能否结合实际场景说出选型依据。
回答框架	底层实现：vector 用动态数组，list 用双向循环链表。性能差异：vector O(1) 随机访问，尾插快；list O(1) 头/中插入，但随机访问 O(n)。场景选型：频繁随机访问选 vector；频繁中间插入/删除选 list。
简短示例回答	vector 底层连续内存，支持 O(1) 下标访问，扩容时涉及拷贝开销；list 采用双向循环链表，任意位置插入删除 O(1) 但无法直接下标访问。项目中数据读多写少且需随机访问时用 vector，需要频繁在中间增删时选用 list。
可能追问	vector 扩容机制（1.5倍/2倍）？list 的 splice 操作复杂度？deque 和 vector 区别？
避坑提醒	不要只说“list 插入快”而不区分位置；vector 尾插快但中间插入需要搬移元素；注意迭代器失效问题。

面试官考察点	是否掌握核心排序的复杂度推导和稳定性含义；是否了解 STL `sort` 的混合策略。
回答框架	快速排序：平均 O(n log n)，不稳定，原地排序，适用大数据无序场景。归并排序：O(n log n)，稳定，需 O(n) 辅助空间，适用需稳定的外部排序。堆排序：O(n log n)，不稳定，原地排序，适用内存受限且对稳定性无要求场景。
简短示例回答	快排通过分治和随机选 pivot 平均效率最高，但最坏 O(n²)；归并稳定递归分治，但额外空间 O(n)；堆排通过堆化实现原地排序。生产环境常用内省排序（快排+堆排降级）保证最坏 O(n log n)。
可能追问	C++ std::sort 为什么用内省排序？手写快排如何避免最坏情况？如何实现稳定快排？
避坑提醒	不要混淆稳定性和时间复杂度；避免死记复杂度的系数常数；强调实际工程中“排序”通常用混合算法。

面试官考察点	是否理解哈希表冲突解决机制（链地址、开放地址）以及红黑树的有序性与平衡特性。
回答框架	哈希冲突解决：链地址法（STL unordered_map 用）、开放地址法（线性探测、二次探测）、再哈希。红黑树优势：有序遍历 O(n)，范围查找高效；最坏操作 O(log n) 稳定，无哈希退化风险。选型：需要有序性或范围查询用红黑树（map/set）；仅查单 key 且不在意顺序用哈希表。
简短示例回答	哈希表通过链地址法存储同义词，负载因子超阈值时触发 rehash。红黑树是近似平衡二叉搜索树，插入/删除通过旋转保持平衡，保证 O(log n) 最坏复杂度，且可中序有序。若业务需按 key 范围查询或遍历有序，优先选红黑树实现。
可能追问	什么是完美哈希？开放地址法的删除问题？红黑树 vs AVL 树区别？
避坑提醒	不要说“哈希表永远 O(1)”，最坏可能 O(n)；红黑树旋转操作不是面试必写，但需理解其核心规则。

📖 复习建议：使用表格对比各容器的底层结构、迭代器类型、内存分配方式；亲手实现一次 AVL 树或红黑树的插入旋转，加深理解。

⚠️ 易错提醒：STL 中 map 底层是红黑树，unordered_map 是哈希表；排序算法中“稳定”指相等元素相对位置不变，堆排和快排通常不稳定。