面试题蒸馏卡：数据结构与算法

高频题按「问题 → 追问链 → 标准答要点 → 常见误解」编排，覆盖 Fcant + 叶 + 遥不可及源稿。

1. 栈和队列的区别？

追问链：各自规则？→ 基本操作？→ 应用场景？
标准答：栈 LIFO（push/pop，函数调用栈），队列 FIFO（offer/poll，任务排队）。
常见误解：只答 LIFO/FIFO 不给场景。

2. 数组和链表的区别？

追问链：随机访问谁快？→ 插入删除谁快？→ 内存连续性？
标准答：数组连续内存、随机访问 O(1)、插入删除 O(n)；链表非连续、随机访问 O(n)、插入删除 O(1)。
常见误解：以为「ArrayList 是链表」（它底层是数组）。

3. 哈希表原理？哈希冲突怎么解决？

追问链：为什么 O(1)？→ 冲突是什么？→ 开放定址 vs 拉链？
标准答：散列函数 h(key) 直接映射存储位置。冲突解决：开放定址法（线性/二次/双散列探查）、拉链法（同义词链表）。
常见误解：以为哈希无冲突；不知道装填因子影响性能。

4. HashMap 底层结构？

追问链：JDK1.8 前后区别？→ 为什么用红黑树？→ 线程安全吗？
标准答：数组 + 链表（JDK1.8 起链表长度 > 8 转红黑树，防退化成 O(n)）。非线程安全，用 ConcurrentHashMap 替代。
常见误解：以为 HashMap 线程安全；用 Hashtable（已淘汰）。

5. 二叉树 / 完全 / 满 / 平衡 / 红黑树区别？

追问链：为什么需要平衡？→ 红黑树几条性质？→ 用途？
标准答：二叉树最多两子；完全=除末层外全满；满=每层满；平衡=左右高度差 ≤1；红黑树=弱平衡（5 性质），解决 BST 退化，用于 TreeMap/HashMap。
常见误解：以为红黑树严格平衡（实为黑高平衡）。

6. B 树和 B+ 树区别？为什么数据库用 B+？

追问链：B+ 叶子有什么特殊结构？→ 范围查询为什么快？
标准答：B+ 非叶只存索引、叶子存全部关键字且链表相连 → 支持范围查询/扫库。B 树叶不链表、非叶也存数据。
常见误解：以为 B 树也能高效范围查询。

7. 排序算法的时间复杂度？

追问链：冒泡/选择/快排？→ 快排最坏何时 O(n²)？→ 稳定性？
标准答：冒泡 O(n²) 稳定、选择 O(n²) 不稳定、快排平均 O(nlogn) 最坏 O(n²) 不稳定。
常见误解：以为快排永远 O(nlogn)；混淆稳定性。

8. 二分查找的适用条件与 mid 溢出？

追问链：前提是什么？→ 时间复杂度？→ mid 怎么写安全？
标准答：前提有序，O(log₂n)。mid 用 low + (high - low) / 2 或 (low + high) >>> 1 防溢出。
常见误解：用 (low + high) / 2 忽略溢出。

9. 一致性哈希是什么？解决什么问题？

追问链：普通哈希的痛点？→ 环怎么建？→ 节点增减影响什么？→ 数据倾斜怎么办？
标准答：把哈希空间组织成环，数据顺时针找节点，节点增减只重定位相邻小部分。解决分布式缓存扩容时全量失效；用虚拟节点解决分布不均。
常见误解：以为一致性哈希能彻底解决分布不均（还需虚拟节点）。

10. 如何找出单链表倒数第 k 个元素？

追问链：遍历几次？→ 能否用双指针？
标准答：双指针，前指针先走 k 步，两指针同步走，前指针到尾时后指针即倒数第 k 个。本质仍是两次遍历（2n+1-k 元素）。
常见误解：以为双指针只遍历一次（链表元素仍被遍历两次）。

关联