数据结构面试题（30 题，含答案）

适用方向：嵌入式软件、底层开发及通用 C/C++ 面试。复杂度默认讨论平均或最坏情况时会特别说明。

1. 什么是时间复杂度和空间复杂度？

答案： 时间复杂度描述输入规模 n 增长时基本操作次数的增长量级，空间复杂度描述算法额外占用空间的增长量级。大 O 表示渐进上界，常见量级从优到劣为 O(1)、O(log n)、O(n)、O(n log n)、O(n²)。分析时要明确平均、最好还是最坏情况，也不能忽略嵌入式系统中的常数开销、内存上限和实时性要求。

2. 数组和链表有什么区别？

答案： 数组内存连续，可通过下标 O(1) 随机访问，缓存局部性好，但中间插入/删除通常是 O(n)，固定数组容量也不易扩展。链表节点可分散存储，已知位置时插入/删除可为 O(1)，但查找是 O(n)，每个节点还有指针开销且缓存不友好。嵌入式中数组通常更可控；链表若使用动态分配，要考虑碎片和失败处理。

3. 单链表如何实现头插、尾插和删除节点？

答案： 头插时令新节点的 next 指向原头，再更新头指针，复杂度 O(1)。尾插若只有头指针，需要遍历到尾部，复杂度 O(n)；若维护尾指针可做到 O(1)。删除时要保存前驱并修改其 next；删除头节点需单独更新头指针。必须处理空链表、单节点、目标不存在、释放后的悬空指针等边界。

4. 如何反转单链表？

答案： 迭代法维护三个指针：prev、cur、next。先保存 cur->next，再令 cur->next = prev，然后依次前移，最后新头为 prev。时间复杂度 O(n)，额外空间 O(1)。递归法更简洁但需要 O(n) 调用栈，在资源受限的嵌入式系统中通常不优先。

Node *reverse(Node *head)
{
    Node *prev = NULL;
    while (head != NULL) {
        Node *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

5. 如何判断单链表是否有环？如何找到环入口？

答案： 使用快慢指针：慢指针每次一步，快指针每次两步；若相遇则存在环，若快指针到达 NULL 则无环。相遇后将一个指针放回头节点，两个指针都每次走一步，再次相遇的位置就是环入口。时间复杂度 O(n)，额外空间 O(1)。

6. 如何找到单链表的中间节点和倒数第 k 个节点？

答案： 中间节点可用快慢指针，快指针两步、慢指针一步。倒数第 k 个节点用前后双指针：前指针先走 k 步，然后两者同步前进，当前指针到尾时后指针即为目标。需先规定 k 从 1 开始还是从 0 开始，并处理 k <= 0、链表长度不足等情况。

7. 栈和队列分别有什么特点和典型应用？

答案： 栈是后进先出（LIFO），基本操作为压栈和出栈，典型应用有函数调用、表达式求值、括号匹配和深度优先搜索。队列是先进先出（FIFO），典型应用有消息缓冲、任务调度、生产者消费者和广度优先搜索。两者都可用数组或链表实现，核心操作通常应为 O(1)。

8. 如何用两个栈实现队列？复杂度是多少？

答案： 入队时压入输入栈；出队时若输出栈为空，就把输入栈元素逐一弹出并压入输出栈，再从输出栈弹出。单次搬运可能为 O(n)，但每个元素最多进入和离开两个栈一次，所以一系列操作的均摊复杂度为 O(1)。两个队列实现栈也可做到，但操作方式和代价不同。

9. 什么是循环队列？如何判断队满和队空？

答案： 循环队列把固定数组首尾逻辑相连，通过下标取模复用空间。常见方案预留一个元素：head == tail 表示空，(tail + 1) % capacity == head 表示满，此时实际容量是 capacity - 1。也可以额外保存元素个数或满标志以使用全部空间。若容量为 2 的幂，可在满足无符号和边界条件时用位与代替取模。

10. 什么是双端队列？

答案： 双端队列（Deque）允许在队头和队尾进行插入与删除。用循环数组实现时四种基本操作都可以为 O(1)。它可用于滑动窗口最大值、任务窃取、0-1 BFS 等。它不是“两个普通队列简单拼接”，实现时仍要正确维护首尾位置、容量和空满状态。

11. 二叉树有哪些常见遍历方式？

答案： 深度优先遍历包括前序（根-左-右）、中序（左-根-右）和后序（左-右-根），可用递归或显式栈实现；层序遍历使用队列做广度优先搜索。二叉搜索树的中序遍历结果是非递减序列。嵌入式中树深不可控时，递归可能造成栈溢出，应考虑迭代方式。

12. 什么是二叉搜索树（BST）？其查找复杂度如何？

答案： 对任一节点，左子树键值小于（或按约定不大于）节点，右子树键值大于（或不小于）节点，且子树也满足该性质。查找、插入、删除的复杂度是 O(h)，h 为树高；平衡时为 O(log n)，退化成链表时最坏为 O(n)。重复键如何放置必须统一约定。

13. BST 删除节点分哪几种情况？

答案： 无子节点时直接删除；只有一个子节点时用该子节点替代；有两个子节点时，通常用右子树最小节点（中序后继）或左子树最大节点（中序前驱）替换，再删除被移动的节点。实现时要正确更新父节点或通过“指向指针的指针”处理根节点变化。

14. AVL 树和红黑树有什么区别？

答案： AVL 树要求任一节点左右子树高度差不超过 1，平衡更严格，查询通常较好，但插入删除可能需要更多旋转和高度维护。红黑树用颜色规则维持近似平衡，最长路径有界，更新操作通常更高效，标准库关联容器常用。两者的查找、插入和删除最坏均为 O(log n)。

15. 什么是堆？它和“动态内存堆”是一回事吗？

答案： 数据结构中的堆是一棵满足堆序性质的完全二叉树，常用数组存储；最大堆父节点不小于子节点，最小堆相反。插入和删除堆顶是 O(log n)，读取堆顶是 O(1)。它与程序内存布局中的 heap（动态分配区）只是同名概念，并非一回事。

16. 如何用数组表示二叉堆？

答案： 若数组从下标 0 开始，节点 i 的左子节点是 2*i+1，右子节点是 2*i+2，父节点是 (i-1)/2。插入时把元素放到末尾并向上调整；删除堆顶时用末尾元素覆盖根，缩小长度后向下调整。计算子节点下标时应防止整数溢出并先判断是否在有效长度内。

17. 建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)？

答案： 从最后一个非叶节点开始做自底向上的下沉调整时，大多数节点靠近叶子，高度很小。将各高度节点的调整代价求和得到 O(n)。若把 n 个元素逐个插入空堆，上界则是 O(n log n)。这是“操作次数 × 单次最坏复杂度”直接相乘可能不够精确的典型例子。

18. 哈希表的基本原理是什么？

答案： 哈希函数把键映射到桶下标，通过桶直接定位数据。哈希分布良好且负载因子合理时，查找、插入和删除平均为 O(1)；大量冲突或遭遇恶意输入时最坏可达 O(n)。设计时需保证相等的键得到相同哈希值，并处理扩容、删除标记和并发安全。

19. 哈希冲突有哪些解决方法？

答案： 常见方法有链地址法和开放寻址法。链地址法每个桶保存链表或其他容器，删除直观但有指针开销；开放寻址把元素放在表内，通过线性探测、二次探测或双重哈希寻找空位，缓存局部性较好，但对负载因子敏感，删除通常需要墓碑标记。嵌入式固定容量场景可选择无需动态分配的开放寻址。

20. 什么是负载因子？为什么哈希表需要扩容？

答案： 负载因子通常为元素数量除以桶数量。它变大后冲突概率和探测长度上升，性能会退化，因此通用哈希表在超过阈值时扩容并重新哈希。扩容可能产生瞬时 O(n) 延迟和额外内存峰值，实时系统可预先分配足够容量、限制最大元素数或采用增量重哈希。

21. 图可以用哪些方式存储？

答案： 邻接矩阵占用 O(V²) 空间，判断两点是否相连为 O(1)，适合稠密小图。邻接表占用约 O(V+E)，适合稀疏图，遍历某节点邻边高效。有向图、无向图、带权图会影响边的记录方式；嵌入式实现还可用静态边数组和索引，避免大量小块动态内存。

22. BFS 和 DFS 有什么区别？

答案： BFS 使用队列逐层搜索，在无权图中可以求最少边数路径，时间复杂度为 O(V+E)；DFS 使用递归或栈深入搜索，适合连通性、拓扑排序、环检测等，时间复杂度同样为 O(V+E)。两者都需要访问标记，否则有环图可能无限遍历。

23. 什么是拓扑排序？什么情况下不存在拓扑序？

答案： 拓扑排序把有向无环图（DAG）的顶点排成线性顺序，使每条边 u -> v 中 u 都在 v 前。可使用 Kahn 入度算法或 DFS 后序实现。如果处理完的节点数小于总节点数，说明图中存在有向环，拓扑序不存在。它常用于依赖管理、任务编排和构建系统。

24. Dijkstra 算法解决什么问题？有什么限制？

答案： Dijkstra 求单源到其他节点的最短路径，使用邻接表和最小堆时常见复杂度为 O((V+E) log V)。它要求边权非负；存在负权边时结果可能错误，应考虑 Bellman-Ford 等算法。无权图最短路直接使用 BFS 即可，不必使用更复杂的 Dijkstra。

25. 快速排序的原理和复杂度是什么？

答案： 选择枢轴，将小于和大于枢轴的元素分区，再递归处理两侧。平均时间 O(n log n)，最坏 O(n²)，递归栈平均 O(log n)；通常是原地排序但不稳定。随机选枢轴、三数取中、处理重复元素的三路划分以及小区间改用插入排序，都可改善实际性能。

26. 归并排序有什么特点？

答案： 将序列分成两半分别排序，再合并两个有序序列。时间复杂度始终为 O(n log n)，数组版本通常需要 O(n) 额外空间，并且容易实现为稳定排序。它适合链表排序和外部排序。对于 RAM 紧张的 MCU，要评估临时缓冲区是否能接受。

27. 冒泡、选择、插入排序各有什么特点？

答案： 三者平均/最坏通常为 O(n²)。冒泡排序通过相邻交换，可稳定但实际用途有限；选择排序每轮选最值，交换次数少但通常不稳定；插入排序把元素插入已排序区，稳定、原地，对小规模或近乎有序数据很高效，常作为高级排序的小区间优化。

28. 什么是稳定排序？为什么有时很重要？

答案： 稳定排序保证关键字相等的元素在排序前后的相对顺序不变。例如先按姓名排序，再稳定地按部门排序，可以保留同部门内的姓名顺序。归并、插入和合理实现的冒泡通常稳定；堆排序、选择排序和普通快速排序通常不稳定。是否需要稳定性取决于数据语义，而非排序速度本身。

29. 如何在 O(n) 时间、O(1) 额外空间内找出数组中出现次数超过一半的元素？

答案： 使用 Boyer-Moore 投票算法：维护候选值和计数，相同加一、不同减一，计数归零时更换候选。若题目不保证一定存在，还需第二遍统计候选出现次数进行验证。算法的本质是不同元素两两抵消，时间 O(n)，额外空间 O(1)。

30. 嵌入式系统选择数据结构时应额外考虑什么？

答案： 除大 O 外，还要考虑最坏执行时间、固定内存上限、碎片、缓存局部性、对齐、并发访问、断电恢复和实现复杂度。实时路径通常更偏好静态数组、环形缓冲区、对象池和有明确上界的算法；避免不可控递归和频繁动态分配。最终选择应以数据规模上限和实测为依据，而不是机械追求理论上更低的平均复杂度。

面试作答建议

讲一个数据结构时，尽量回答四点：核心不变量、主要操作复杂度、边界条件、为什么适合当前场景。若需要手写代码，先明确空输入、容量、所有权和错误返回值，再开始写主体逻辑。