Appearance
Data Structure 高频面试问答
本文件用于秋招技术面试口头表达训练，不承担完整知识正文职责。
详细原理参见 01_Common_CS/Data_Structure/。
A. 基础结构与 Hash
1. Array 和 Linked List 的主要区别是什么？
Array 通常连续存储，可以通过下标 O(1) 随机访问，但中间插入删除往往需要移动后续元素。
Linked List 节点不要求连续存储，随机访问需要 O(n) 遍历；如果目标位置已经定位，插入删除只需要修改有限个指针，可以做到 O(1)。
实际选择取决于访问模式、插删频率和是否能快速定位节点。
2. 为什么不能简单说“Linked List 插入是 O(1)”？
O(1) 只描述已经获得目标位置或前驱节点后的指针修改成本。
如果还需要从头遍历寻找插入位置，定位过程可能是 O(n)，因此整体仍可能是 O(n)。
3. Stack、Queue 和 Deque 的核心区别是什么？
text
Stack → LIFO
Queue → FIFO
Deque → 两端都可以插入和删除DFS 常见 Stack，BFS 常见 Queue；Deque 可以高效支持两端操作，在 Python 中常用 collections.deque。
4. 为什么 Python 中高频 FIFO 出队不推荐 list.pop(0)？
Python list 底层更接近动态数组。删除第 0 个元素后，后续元素需要整体前移，因此是 O(n)。
deque.popleft() 针对双端操作设计，可以做到 O(1)。
5. 为什么 Hash Table 查询通常是平均 O(1)，而不是永远 O(1)？
Hash Function 可以把 key 快速映射到 bucket，理想情况下不需要扫描整个集合，因此平均接近 O(1)。
但不同 key 可能发生 Hash Collision；当负载过高时还可能需要 Resize / Rehash，因此不能把所有情况下的查询都描述为严格 O(1)。
6. Direct Address Table 和 Hash Table 怎么选？
如果 key 是小范围、稠密整数，Direct Address Array / Bitmap 通常最直接，不存在 Hash Collision。
如果 key 空间巨大、稀疏，或者 key 是字符串等复杂类型，更适合通过 Hash Table 将 key 映射到有限 bucket。
7. Two Sum 为什么可以用 Hash Map 从 O(n²) 优化到平均 O(n)？
遍历当前元素 x 时，只需查询：
text
need = target - x是否已经出现。
Hash Map 将原本需要线性扫描的历史查询降低为平均 O(1)，因此整体只需要一次 O(n) 遍历。
常见状态：
text
key = 已出现的值
value = 下标B. Set / Map
8. Set 和 Map 有什么区别？
Set 主要用于保存唯一 key，适合去重、存在性查询和 visited 等场景。
Map 保存 key → value 映射，除了判断 key 是否存在，还可以保存频次、下标、最近位置或其他状态。
text
Set = membership
Map = membership + state9. Map 的 key 和 value 应该如何设计？
先问两个问题：
- 未来我要通过谁来查询？它通常就是 key；
- 查询后还需要得到什么？它通常就是 value。
例如频次统计：
text
key = 元素
value = 出现次数Two Sum：
text
key = 已出现的数
value = 下标C. Tree / DFS / BFS
10. 二叉树和二叉搜索树有什么区别？
二叉树只要求每个节点最多有两个子节点。
BST 额外要求：
text
左子树所有值 < 当前节点 < 右子树所有值这个约束作用于整棵左右子树，而不只是直接孩子。
11. 前序、中序、后序遍历的本质区别是什么？
三者本质上都是 DFS，只是处理当前 Root 的时机不同：
text
Preorder: Root → Left → Right
Inorder: Left → Root → Right
Postorder: Left → Right → Root12. DFS 为什么既可以递归实现，也可以用 Stack 实现？
递归 DFS 的函数调用由系统 Call Stack 保存返回位置。
显式迭代 DFS 则由程序员自己维护 Stack。
text
DFS = 搜索策略
递归 / Stack = 实现方式13. 为什么迭代前序 DFS 想先访问 left，却要先把 right 压栈？
因为 Stack 是 LIFO。
如果希望访问顺序为：
text
left → right压栈顺序应反过来：
text
right → left这样 left 后入栈、先被 pop。
14. DFS 和 BFS 分别通常使用什么数据结构？
text
DFS → Stack
BFS → QueueDFS 优先向深处扩展；BFS 按发现顺序逐层扩展，因此需要 FIFO Queue。
15. 二叉树 DFS 的时间和空间复杂度是多少？
若访问每个节点一次：
text
Time: O(n)递归空间取决于树高：
text
Space: O(h)平衡树约为 O(log n)，退化树最坏为 O(n)。
16. 为什么求二叉树最大深度通常具有后序思想？
当前节点深度为：
text
max(left_depth, right_depth) + 1父节点答案依赖左右子树答案，因此需要先得到孩子结果，再计算当前节点。
这是数据依赖导致的后序结构；LIFO Call Stack 只是递归实现机制。
17. 为什么 BST 的中序遍历是有序的？
BST 满足：
text
Left < Root < Right中序遍历顺序正好是：
text
Left → Root → Right递归应用到所有子树后，会得到从小到大的有序序列。
18. BST 查找为什么不是永远 O(log n)？
BST 查找复杂度是 O(h)，取决于树高。
平衡情况下：
text
h ≈ O(log n)若树严重退化成链状结构：
text
h = O(n)查找也会退化为 O(n)。
D. Complete Binary Tree / Heap
19. Complete Binary Tree 的核心条件是什么？
除最后一层外，其余层全部填满；最后一层允许不满，但节点必须从左到右连续排列，不能出现中间空洞。
从数组下标 0 开始：
text
left = 2i + 1
right = 2i + 2
parent = (i - 1) // 220. Heap 和 BST 有什么区别？
BST 维护全局有序搜索关系：
text
Left < Root < RightHeap 只维护父子堆序：
text
Min Heap: Parent <= Children
Max Heap: Parent >= Children因此 Heap 擅长快速获得当前极值，但不支持像 BST 那样的全局有序遍历。
21. Heap 为什么通常可以直接用数组存储？
Heap 是 Complete Binary Tree，节点按层序连续排列，可以紧凑映射到数组下标。
父子关系又能通过下标公式直接计算，因此不需要为每个节点额外保存 left/right 指针。
22. Min Heap 的插入和删除堆顶分别怎么恢复堆序？
插入：
text
数组末尾加入
→ 保持 Complete Binary Tree
→ sift up删除堆顶：
text
最后节点移到根
→ 删除数组末尾
→ sift down二者复杂度通常都是 O(log n)。
23. 为什么删除 Heap 堆顶时用最后一个节点补到根？
因为真正移除数组最后位置后，层序下标仍保持连续，从而维持 Complete Binary Tree 的结构。
之后只需通过 sift down 恢复堆序性质。
24. Priority Queue 和 Heap 是什么关系？
Priority Queue 是一种抽象需求：每次优先取出最高或最低优先级元素。
Heap 是实现 Priority Queue 的经典数据结构。
text
Priority Queue = ADT / 功能
Heap = 常见实现25. 为什么找最大的 K 个元素通常维护 Min Heap？
因为需要持续知道当前 Top-K 中最小的元素，也就是淘汰线。
text
x <= heap top → x 没资格进入 Top-K
x > heap top → 淘汰 heap top，加入 x所以：
text
Top K largest → size-K Min Heap26. 使用大小为 K 的 Min Heap 找第 K 大时，答案在哪里？
在堆顶。
因为最终 Heap 保存整体最大的 K 个元素，而 Min Heap 堆顶是这 K 个元素中最小的，因此正好是整体第 K 大。
text
K-th largest = Min Heap topPractice:
04_Practice/CS_MCQs/Data_Structure_Lesson_1.md04_Practice/CS_MCQs/Data_Structure_Lesson_2.md
Mistakes:
05_Mistakes/CS.md