数据结构：练习题及解析

1什么是数据结构

数据结构是在内存中组织数据的一种方式，使某些操作很快：查找一个项目、添加一个、删除一个。

没有哪种结构在所有操作上都快。选择一种结构就是选择哪些操作应该开销小。它们的开销用大 O 表示，其中 n 为项目数。

两个基本的构件是数组和链表。

数组把项目存储在一整块内存里，一个接一个。计算机可以算出第 i 个项目在哪里，所以读取 a[i] 只需 O(1)。在前面插入意味着移动每一个项目：O(n)。

链表把每个项目存储在一个节点里，节点带有指向下一个节点的指针。最后一个指针为 null。在头部（h）插入只改变一个指针：O(1)。但要到达第 i 个项目，你必须沿着 i 个指针走：O(n)。

双向链表还带有指向前一个节点的指针，所以你可以双向行走。

2栈和队列

栈像一摞盘子：你只在顶部添加和移除。最后进入的项目最先出来：LIFO（后进先出）。

• push 把一个项目放在顶部，pop 移除顶部的项目，peek 读取顶部而不移除它。它们都是 O(1)。
• 用途：编辑器的撤销功能、程序的调用栈、检查括号是否匹配、深度优先搜索。

队列像收银台前的队伍：你在队尾加入，在队首离开。最先进入的项目最先出来：FIFO（先进先出）。

• enqueue 在队尾添加，dequeue 从队首移除。两者都是 O(1)。
• 用途：打印任务、等待处理的消息、广度优先搜索。

双端队列（deque）允许在两端添加和移除。优先队列总是先移除优先级最高的项目；它通常用堆来实现。

3树、堆、哈希表和图

树有一个最顶端的节点，即根。其他每个节点恰好有一个父节点。没有子节点的节点是叶子。有 n 个节点的树有 n − 1 条边。

在二叉树中，每个节点最多有两个子节点。二叉搜索树（BST）增加了一条规则：左子树中的键比该节点小，右子树中的键比它大。

在 BST 中查找沿着一条路径向下，所以开销是 O(高度)。平衡树（AVL、红黑树）使高度保持在 log₂ n 附近。按排序顺序插入键会形成高度为 n 的链。

堆是一种二叉树，其中每个父节点都比它的子节点小（最小堆）或大（最大堆）。最小值或最大值在根处，插入和移除的开销为 O(log n)。

哈希表存储键值对。哈希函数把键变成下标，所以插入和查找平均只需 O(1)。两个键得到同一个下标称为冲突，用链地址法（每个槽一个链表）或开放寻址法（尝试另一个槽）解决。

图有由边连接的顶点，边可以有方向或权重。它可以存为邻接矩阵（O(V²) 内存），或邻接表（O(V + E)）。

4分步方法

题目常常描述一个任务，问哪种结构合适，或者问某些操作之后结构是什么样子。

1. 找出必须快的操作：按位置访问、按键访问、最新的项目、最旧的项目、最小的项目，或一个范围。
2. 把它与某种结构对应起来：下标 → 数组，键 → 哈希表，最新 → 栈，最旧 → 队列，最小或最大 → 堆，有序或范围 → 平衡搜索树。
3. 检查任务所需的其他操作的开销，用大 O 表示。
4. 对于跟踪题，一次执行一个操作，并写下每一步之后的状态。
5. 用该结构的规则检查最终状态：LIFO、FIFO、BST 的顺序或堆的顺序。

5例题讲解

跟着每一步走。打开下一步之前，先试着预测它。

6常见错误

• 混淆 LIFO 和 FIFO。栈返回最新的项目，队列返回最旧的。
• 以为链表可以按下标快速访问。它必须从头部走起。
• 以为 BST 总是 O(log n)。只有平衡树才是；按排序顺序插入会得到 O(n)。
• 忘了哈希表中的冲突。O(1) 是平均情况，不是最坏情况。
• 混淆各种遍历。先序：节点在最前。中序：节点在中间。后序：节点在最后。
• 对大型稀疏图使用邻接矩阵。这会浪费 O(V²) 的内存。

7考试题是什么样的

• 简单：关键术语和事实。LIFO 和 FIFO，什么是节点、根或叶子，BST 的规则，哈希函数的作用。
• 中等：应用概念。哪种结构适合某项任务、push 和 pop 或 BST 插入的结果、树的遍历、使用线性探测的哈希表、用大 O 表示的开销。
• 困难：案例与分析。平衡树、数组中的堆、B 树、字典树、并查集、布隆过滤器，以及 LRU 缓存之类的设计。

对于从下标 0 开始存放在数组中的堆，下标 i 的子节点在 2i + 1 和 2i + 2，它的父节点在 ⌊(i − 1) / 2⌋。