数据结构与算法1000问：基础、线性结构与树

本篇迁移数据结构与算法题库首批 10 道基础问题。重点放在概念、复杂度、嵌入式场景和实现取舍。

1. 数据结构和算法是什么关系？

答案： 数据结构组织和保存数据，算法定义如何处理这些数据。数据结构影响操作成本，算法则决定如何利用这些结构完成任务。同一种数据结构可以支持多种算法；同一算法也可能基于不同数据结构实现，复杂度随之变化。

2. O(n)、O(log n)、O(n²) 在实际运行时差多少？

答案： Big-O 描述输入规模增大时资源消耗的增长阶，不直接给出绝对耗时。假设 n=1000：

• O(log₂n) 约 10 次数量级操作。
• O(n) 约 1000 次。
• O(n²) 约 1,000,000 次。

实际运行还受常数因子、缓存局部性、内存分配、编译优化和输入分布影响。嵌入式系统还要关注 WCET（最坏执行时间）和内存上界，不能只看平均复杂度。

3. 什么是空间换时间？嵌入式中有什么例子？

答案： 通过额外存储预先保存结果或索引，减少重复计算或查找。例如：

• 用查表（LUT）替代高成本的实时三角函数或非线性换算。
• 用位图记录资源占用状态，快速判断某项是否已使用。
• 用环形缓冲区缓存 UART/CAN 数据，减少频繁搬移。
• 用哈希表保存 ID 到配置项的映射，减少线性扫描。

代价是 RAM/Flash 占用、初始化时间和数据一致性维护。MCU 选型时必须把内存预算纳入设计。

4. 数组 O(1) 随机访问，链表为什么还有用？

答案： 数组通过下标直接计算元素地址，随机访问通常为 O(1)，但中间插入/删除可能需要移动大量元素。链表不支持 O(1) 随机访问，但在已知节点位置时，插入/删除只需调整指针，操作本身为 O(1)。

实际系统还要考虑缓存局部性：数组连续存储，通常更利于 CPU Cache；链表节点分散，指针追踪会产生缓存未命中。因此链表并不天然更快。

5. 单向、双向和循环链表如何选择？

答案：

• 单向链表：每个节点只有 next，内存开销较低，适合单向遍历。
• 双向链表：有 prev/next，支持双向遍历和已知节点的快速删除，但每个节点多一个指针。
• 循环链表：尾节点指向头节点，适合循环遍历和调度场景。

嵌入式并非“最常用某一种链表”就能覆盖全部场景。固定长度队列、环形缓冲区和静态数组往往更可预测；需要动态增删节点时才考虑链表，并注意内存碎片和生命周期管理。

6. 动态数组为什么常按倍数扩容？

答案： 若每次只增加一个元素，连续追加 n 个元素可能触发 O(n²) 总搬移。采用倍增扩容（例如容量不足时翻倍），虽然单次扩容仍可能搬移 O(n) 元素，但多次扩容的总搬移量为 O(n)，因此追加操作的摊还复杂度为 O(1)。

嵌入式项目若禁止运行时动态分配，可以在启动时一次性分配固定容量，或使用静态数组与明确的容量上限。

7. 栈为什么是后进先出？函数调用栈说明了什么？

答案： 栈（Stack）遵循 LIFO：最后压入的元素最先弹出。函数调用具有嵌套关系：调用者暂停，进入被调用函数；被调用函数返回后，恢复调用者，因此局部变量、返回地址和保存的寄存器上下文适合按栈帧管理。

flowchart TB
  A[main 栈帧] --> B[函数 A 栈帧]
  B --> C[函数 B 栈帧]
  C --> D[函数 B 返回并弹栈]
  D --> E[恢复函数 A]
  E --> F[函数 A 返回]

递归层数过深会耗尽栈空间；嵌入式需评估最大调用深度、中断栈和任务栈余量。

8. 队列在嵌入式系统中有什么用途？环形缓冲区怎么实现？

答案： 队列遵循 FIFO，常用于 UART 接收缓存、生产者—消费者任务通信、事件排队和 CAN 报文缓冲。环形缓冲区用固定数组和读写索引实现队列，索引到末尾后回绕到数组起点，避免每次出队都移动数据。

flowchart LR
  A[生产者 / ISR 写入] --> B[写索引 head]
  B --> C[固定数组 Ring Buffer]
  C --> D[读索引 tail]
  D --> E[消费者任务读取]

实现时必须定义满/空判定策略、并发访问保护、溢出处理和内存屏障要求。ISR 与任务共享时，不应仅凭“两个索引”就假定所有平台上天然无竞争。

9. 优先队列与普通队列有什么区别？

答案： 普通队列按进入顺序出队；优先队列按优先级或键值出队。优先队列常用堆实现，插入和取出最大/最小元素通常为 O(log n)，查看队首为 O(1)。

它可用于事件调度、路径搜索和任务管理，但实时操作系统的任务调度通常还涉及抢占、截止时间、优先级继承/天花板和中断约束，不能直接把一个普通优先队列等同于完整 RTOS 调度器。

10. 二叉树前序、中序、后序遍历有什么区别？

答案：

• 前序：根 → 左 → 右。
• 中序：左 → 根 → 右。
• 后序：左 → 右 → 根。

对二叉搜索树（BST），中序遍历可得到按键值排序的序列，因为左子树键值小于根、右子树键值大于根（假设采用该排序约定）。BST 若按有序数据依次插入，可能退化为链表，查找从平均 O(log n) 退化为 O(n)；AVL、红黑树等通过平衡规则限制高度。

flowchart TD
  A[根 8] --> B[左 3]
  A --> C[右 10]
  B --> D[左 1]
  B --> E[右 6]
  C --> F[右 14]

复杂度与嵌入式实现检查

• 明确 n 的定义：报文数、节点数、数组长度还是采样窗口。
• 计算最坏情况，而不只看平均复杂度。
• 评估 RAM、栈、Flash、堆碎片和静态内存上限。
• 对中断与多任务共享的数据结构定义并发模型。
• 对固定容量结构定义满载、溢出、恢复和诊断策略。

Flomo 原始来源

• 数据结构与算法 1000 个问题：https://v.flomoapp.com/mine/?memo_id=MjQ1NzM1Mjc4