CS 数据结构期末备考指南
数据结构课（Data Structures）是 CS 专业最重要的必修课之一，也是 GPA 竞争最激烈的课程之一。期末考试的题型虽然千变万化，但核心考点高度集中。
这篇指南按照考试频率，拆解每种数据结构的高频题型和解题框架。
准备策略：考前 2 周怎么分配时间
Week 2（考前 2–14 天）：
- 把课程覆盖的所有数据结构列清单（链表/栈/队列/树/图/哈希表）
- 每种数据结构：看 1 次讲义核心定义 + 做 2–3 道 Past Exam 题
Week 1（考前 1–7 天）：
- 专注高频题型的手写代码练习（不用 IDE，直接在白纸上写）
- 完整做 1–2 套历年考卷（计时）
考前 1–2 天：
- 只回顾自己错的题目，不做新题
- 整理 Big-O 速查表（下文有模板）
一、链表（Linked List）
高频题型
1. 单链表反转（极高频）
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
2. 找链表中点（Floyd 快慢指针）
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow 停在中点（偶数长度时在前半段末）
3. 检测环（Cycle Detection）
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
4. 合并两个有序链表
def merge_sorted_lists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
Big-O 速查
| 操作 | 单链表 | 双链表 |
|---|---|---|
| Access（索引） | O(n) | O(n) |
| 头部插入/删除 | O(1) | O(1) |
| 尾部插入 | O(n)（无 tail 指针）/ O(1) | O(1) |
| 搜索 | O(n) | O(n) |
二、栈（Stack）和队列（Queue）
高频题型
1. 用两个栈实现队列
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x):
self.in_stack.append(x)
def pop(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack.pop()
2. 括号匹配（Valid Parentheses）
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack
三、二叉树（Binary Tree）
高频题型
1. 三种遍历（前/中/后序）
前序（Root-Left-Right）：
def preorder(root):
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
中序（Left-Root-Right）——BST 中序遍历得到有序序列：
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
2. 二叉搜索树（BST）的插入和查找
def bst_insert(root, val):
if not root: return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return root
3. 二叉树的最大深度
def max_depth(root):
if not root: return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
4. 判断 BST 合法性
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root: return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.val) and
is_valid_bst(root.right, root.val, max_val))
Big-O 速查
| 操作 | 平均（平衡 BST） | 最坏（退化链表） |
|---|---|---|
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
四、图（Graph）
BFS 和 DFS 代码模板
BFS（适合最短路、层序遍历）：
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node) # 处理当前节点
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
DFS（适合连通分量、拓扑排序、路径搜索）：
def dfs(graph, node, visited=None):
if visited is None: visited = set()
visited.add(node)
print(node) # 处理当前节点
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
考试常考场景
- 连通分量数量：DFS/BFS 遍历所有节点
- 是否有环（有向图）：DFS + 颜色标记（WHITE/GRAY/BLACK）
- 拓扑排序：Kahn 算法（BFS + 入度）或 DFS 后序逆序
- 最短路：Dijkstra（加权无负边）/ BFS（无权图）
Big-O 速查
| 算法 | 时间 | 空间 |
|---|---|---|
| BFS/DFS | O(V + E) | O(V) |
| Dijkstra（优先队列） | O((V+E) log V) | O(V) |
五、哈希表（Hash Table）
高频题型
1. Two Sum（经典哈希表应用）
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
2. 判断字符串异位词（Anagram）
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
Big-O 速查
| 操作 | 平均 | 最坏（哈希冲突严重） |
|---|---|---|
| 搜索 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
六、堆（Heap）
核心概念
- 最小堆（Min-Heap）：父节点 ≤ 子节点，堆顶是最小值
- 最大堆（Max-Heap）：父节点 ≥ 子节点，堆顶是最大值
- Python 的
heapq是最小堆
高频应用
import heapq
# 获取数组中 K 个最大值
def k_largest(nums, k):
return heapq.nlargest(k, nums)
# 最小堆操作
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heapq.heappop(heap)) # 输出 1（最小值）
Big-O 速查
| 操作 | 时间 |
|---|---|
| 插入（heappush） | O(log n) |
| 删除堆顶（heappop） | O(log n) |
| 建堆（heapify） | O(n) |
考试失分点总结
- 递归没有 base case：每道树/链表递归题先写
if not root: return ... - 忘记初始化 visited 集合：图算法必须跟踪已访问节点
- BST 验证只比较父节点：要传递 min/max 范围，不只是和父节点比
- Big-O 分析遗漏空间复杂度：递归调用栈也算空间（深度 O(n) 或 O(log n)）
- 哈希表冲突处理：考试可能问 Chaining vs Open Addressing 的原理
如果你正在准备数据结构期末考，或者作业卡在某个具体实现上，欢迎联系我们的 CS 辅导团队进行一对一的代码讲解和题目精讲。
相关院校数据结构辅导指南： UNSW COMP1511 · Monash · UCLA · UIUC · UToronto
