第14章 · 数据结构与算法 · 阶段测试题答案¶
一 · 单选 (8 题)¶
1.1 B - 二分查找 O(log n) 仅限有序数组。
1.2 A - 哈希表平均 O(1)。
1.3 C - 红黑树是平衡二叉搜索树。
1.4 B - BFS 用队列, DFS 用栈。
1.5 A - 动态规划: 拆子问题 + 状态转移。
1.6 C - 归并排序稳定 O(n log n)。
1.7 B - Trie 用于前缀匹配。
1.8 A - Dijkstra 处理非负权图最短路。
二 · 多选 (4 题)¶
2.1 ABD - 都是 O(n log n) 排序。
2.2 ABC - 树遍历方式。
2.3 ABD - 都是图算法。
2.4 ABD - C 错: 冒泡 O(n²)。
三 · 简答 (5 题)¶
3.1 复杂度对比¶
| 操作 | 数组 | 链表 | 哈希 | 树 |
|---|---|---|---|---|
| 查 | O(1) | O(n) | O(1) | O(log n) |
| 插 | O(n) | O(1) | O(1) | O(log n) |
| 删 | O(n) | O(1) | O(1) | O(log n) |
3.2 LRU Cache¶
实现: 哈希表 + 双向链表 - get(key): 哈希查 → 移到链表头 → 返回值 - put(key, value): 加入 → 超容移除尾节点
复杂度: O(1) get/put
3.3 动态规划¶
核心: 把大问题拆成子问题, 记下子问题解(记忆化) 步骤: 1. 定义 dp[i] / dp[i][j] 2. 找状态转移方程 3. 初始化 + 遍历顺序
例子: 斐波那契 dp[n] = dp[n-1] + dp[n-2], 优化空间 O(1)。
3.4 Dijkstra¶
算法: 1. 初始化 dist[s]=0, 其他 = ∞ 2. 优先队列取最小 dist 节点 u 3. 松弛 u 的邻居 v: dist[v] = min(dist[v], dist[u]+w(u,v)) 4. 直到队列空
复杂度: O((V+E) log V) (堆优化) 限制: 不能有负权边
3.5 并查集¶
应用: 连通分量 / Kruskal / 朋友圈 优化: 路径压缩 + 按秩合并 → 接近 O(1)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
四 · 编程 (2 题)¶
4.1 Top-K (LeetCode 347)¶
from collections import Counter
import heapq
def topKFrequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)