2.11 综合练习

第二章真正要训练的不是"说出某个数据结构的名字"，而是：

根据操作需求选择结构，并审查 agent 的选择是否合理。

提交练习时，请尽量使用下面格式。

任务：
数据规模：
高频操作：
- 操作 1：
- 操作 2：
- 操作 3：

候选结构：
选择：
放弃其他结构的理由：
时间复杂度：
空间复杂度：
agent 输出审查：
- 可接受：
- 需修改：
- 仍需澄清：

---

🚨 常见陷阱清单

以下是第二章各节中提到的 常见陷阱，整理成系统性清单。每个陷阱都对应一个审查口诀。

---

陷阱 1：用 list.pop(0) 做队列出队

问题代码	真实代价	正确替代
tasks.pop(0)	Θ(n) 移动全部剩余元素	deque.popleft() Θ(1)

审查口诀：看到队列用 list，先问 pop(0) 出现几次？
诊断信号：需求说"按提交顺序处理"、"先进先出"、"排队"。

---

陷阱 2：用 list 做成员查询

问题代码	真实代价	正确替代
if x in items: (items 是 list)	Θ(n) 逐个比较	set 或 dict 期望 Θ(1)

审查口诀：代码里有 x in list，先问这是循环内还是循环外？
诊断信号：需求说"判断是否存在"、"去重"、"检查是否已注册"。

扩展场景：

def has_common(a, b):
    for x in a:           # 外层循环 Θ(n)
        if x in b:        # 内层查询 Θ(m)
            return True
    return False

如果 b 是 list，总复杂度是 Θ(n × m)。改成 b_set = set(b)，变成 Θ(n + m)。

---

陷阱 3：每轮重新排序代替优先队列

问题代码	真实代价	正确替代
while tasks: tasks.sort(...) pop(0)	Θ(n log n × n) ≈ Θ(n² log n)	heapq 每次 Θ(log n)

审查口诀：看到循环里排序，先问"是不是每次只取最大或最小？"

诊断信号：需求说"每次处理最紧急任务"、"取最高优先级"、"截止时间最早先处理"。

---

陷阱 4：用链表但忽略查找成本

错误说法	真实情况
"链表插入是 Θ(1)"	已知位置后插入才是 Θ(1)；先要找位置则整体 Θ(n)

审查口诀：看到"用链表因为插入快"，先问"插入位置怎么得到？"

诊断信号：需求没有明确说"已经持有节点"，而是"按值插入"、"在某条件后插入"。

---

陷阱 5：哈希表的 Θ(1) 误解

错误说法	正确理解
"哈希表查找永远 Θ(1)"	期望 Θ(1)，最坏可退化到 Θ(n)（极端冲突或恶意输入）

审查口诀：看到"O(1) 所以最好"，先问"期望还是最坏？"

注意点：

• Python dict/set 要求 key 可哈希（不可变）
• 哈希表不擅长范围查询、按序遍历、取最大最小
• 装载因子过高会触发扩容（摊还代价）

---

陷阱 6：有序数组只看查找不看插入

错误说法	真实情况
"bisect 找位置 Θ(log n)"	找位置 Θ(log n)，但插入要移动元素 Θ(n)

审查口诀：看到"有序 + bisect"，先问"插入多还是查找多？"

诊断信号：数据几乎不更新（静态），适合有序数组；频繁插入删除，需要平衡树或跳表。

---

陷阱 7：缓存不一致

问题代码	风险
只在新增时更新计数缓存	删除/修改时忘记同步，缓存与原数据漂移

审查口诀：看到"缓存更快"，先问"哪些操作会让它失效？"

必须回答的五个问题：

1. 缓存的 key 是什么？
2. 缓存的 value 是什么？
3. 哪些操作会让缓存失效？
4. 缓存和原始数据的不变量是什么？
5. 缓存空间代价是否可接受？

---

陷阱 8：混淆摊还、期望和最坏

错误说法	正确说法
"append 是 Θ(1)"	摊还 Θ(1)，单次最坏可触发 Θ(n) 扩容
"摊还就是平均运气"	摊还不依赖概率，是一串操作的确定性总成本分摊

审查口诀：看到"O(1)"，先问"单次最坏、摊还还是期望？"

---

陷阱 9：手写数据结构却不如内置结构

错误做法	问题
Python 里手写链表替代 list	通常比内置 list 慢（对象开销、缓存不友好）
手写 BST 却没实现平衡	最坏 Θ(n)，不如直接用 dict 或数据库

审查口诀：看到手写数据结构，先问"内置结构为什么不够用？"

---

陷阱 10：忘记维护组合结构的不变量

问题代码	风险
favorite_ids = set() + favorite_order = []	删除时只更新一个，另一个遗留

审查口诀：看到多个结构组合，先问"它们之间必须保持什么关系？"

---

📋 陷阱自查表

在提交代码或审查 agent 输出前，用这张表快速检查：

检查点	风险信号	是否需要修正？
是否 pop(0)	队列用 list	□ 是 □ 否
是否 x in list (循环内)	成员查询用 list	□ 是 □ 否
是否循环内排序	优先队列被写成重复排序	□ 是 □ 否
是否说"链表插入 Θ(1)" 未提查找	只看插入忽略查找成本	□ 是 □ 否
是否说哈希表"永远 Θ(1)"	混淆期望和最坏	□ 是 □ 否
是否用 bisect 但频繁插入	有序数组频繁移动元素	□ 是 □ 否
是否有缓存但无失效逻辑	缓存不一致	□ 是 □ 否
是否混淆摊还/期望/最坏	复杂度类型不清	□ 是 □ 否
是否手写数据结构无必要	过度实现	□ 是 □ 否
是否多结构组合无同步逻辑	不变量未维护	□ 是 □ 否

---

基础练习

练习 2.1：结构识别

为下面场景选择一个最自然的数据结构，并说明理由：

场景	推荐结构	理由
判断一个用户名是否已经注册
撤销最近一次编辑
按提交顺序处理任务
反复取截止时间最早的任务
按学号查学生信息
按成绩区间查学生

要求：每一行都写出至少一个主要操作和复杂度。

---

练习 2.2：Python 隐藏成本

分析下面代码的时间复杂度，并指出隐藏成本：

def remove_seen(items):
    result = []
    for item in items:
        if item not in result:
            result.append(item)
    return result

请回答：

1. item not in result 的复杂度是多少？
2. 最坏情况下总复杂度是多少？
3. 如果要保持原顺序，如何改写？
4. 改写后额外空间是多少？

---

练习 2.3：栈还是队列

下面三个需求分别适合栈、队列还是优先队列？

1. 代码编辑器撤销操作。
2. 系统按到达顺序发送邮件。
3. 每次处理最紧急的报警。

请写出每个结构的核心操作，并用 Python 给出 3 行以内的示例代码。

---

进阶练习

练习 2.4：审查 agent 的推荐

某 agent 对"课程报名系统"给出建议：

使用一个列表保存所有报名记录。报名时 append，退课时遍历列表删除，查询某个学生是否报名某门课时也遍历列表。列表简单可靠，因此是最佳选择。

系统需求：

• 学生数最多 50,000。
• 课程数最多 1,000。
• 每天报名和退课约 20,000 次。
• 查询"某学生是否报名某课"每天约 500,000 次。
• 老师需要查看某门课的报名名单。

请回答：

1. agent 的方案哪里可能慢？
2. 写出操作需求表。
3. 设计一个数据结构组合。
4. 说明每个操作的复杂度。
5. 写一段提示词，要求 agent 重新比较候选方案。

---

练习 2.5：有序需求

一个系统保存商品价格。需要支持：

1. 按商品 id 查价格。
2. 修改商品价格。
3. 找出价格在 [low, high] 之间的商品。

请回答：

1. 只用 dict 能高效支持全部操作吗？
2. 哪个操作需要有序结构？
3. 如果商品数量只有 500，简单扫描是否可以接受？
4. 如果商品数量是 500 万，应该怎样重新设计？
5. 你会怎样让 agent 分别给出小规模和大规模方案？

---

练习 2.6：优先队列改写

下面代码每次取最高优先级任务：

def run(tasks):
    result = []
    while tasks:
        tasks.sort(key=lambda t: t["priority"], reverse=True)
        result.append(tasks.pop(0))
    return result

请回答：

1. 为什么重复排序低效？
2. 如果任务运行中不会新增，是否可以先排序一次？
3. 如果任务运行中会不断新增，为什么优先队列更自然？
4. 用 heapq 改写为最小优先级先出。
5. 如果优先级相同，如何保持先加入先出？

---

挑战练习

练习 2.7：数据结构选择卡

选择一个真实任务，例如：

• 收藏文章系统
• 消息通知中心
• 课程报名系统
• 在线题库错题本
• 热门搜索词统计
• 简易任务调度器

完成一张数据结构选择卡：

任务：
数据规模：
高频操作：
边界情况：
候选结构 1：
候选结构 2：
候选结构 3：
最终选择：
复杂度分析：
空间代价：
实现风险：

然后让 coding agent 给出一个方案。你需要提交一份审查记录：

1. agent 是否先列操作需求？
2. agent 是否说明放弃其他结构的理由？
3. agent 的复杂度分析是否准确？
4. agent 是否忽略 Python 具体结构的隐藏成本？
5. 你最终接受、修改或拒绝了哪些部分？

---

练习 2.8：复杂度审计报告

找一段你或 agent 写过的 Python 代码，要求其中至少出现三种结构：

• list
• dict
• set
• deque
• heapq
• 自定义类或节点结构

提交一份复杂度审计报告：

代码片段：
输入规模定义：
核心操作：
逐行成本：
整体时间复杂度：
额外空间复杂度：
隐藏成本：
可以接受的原因 / 不可接受的原因：

报告必须指出至少一个隐藏成本，例如：

• x in list
• pop(0)
• 切片复制
• 循环里排序
• 循环里复制字典或集合
• 维护两个结构但忘记同步删除

---

练习 2.9：反驳一个看似专业的建议

某 agent 给出如下建议：

为了让系统性能最好，所有查询都应该使用哈希表，因为哈希表查询是 O(1)。如果还需要排序，就查询后再排序即可。

请写一段反驳，必须包含：

1. O(1) 是什么意义下的说法。
2. 哪些查询不是哈希表擅长的。
3. "查询后再排序"在什么情况下会变慢。
4. 至少一个需要有序结构的具体场景。
5. 一个更专业的提示词，要求 agent 重新比较 dict、有序列表、堆和数据库索引。

评分重点：不是说"哈希表不好"，而是能说清它的适用边界。

---

练习 2.10：小型设计答辩

设计一个"在线课堂互动系统"的数据结构方案。系统支持：

1. 学生加入课堂。
2. 学生提交问题。
3. 老师按提交顺序查看问题。
4. 老师可以把某些问题标为高优先级。
5. 系统显示每个学生提交了多少问题。
6. 下课后导出所有问题记录。

请准备一份答辩稿：

我的结构组合：
每个结构负责什么：
核心不变量：
每个操作复杂度：
为什么不用单个 list：
为什么不用单个 dict：
如果规模扩大 100 倍，哪里会先出问题：
我会让 agent 帮我检查什么：

这个练习不要求唯一答案。关键是你的取舍必须可审查。

---

练习 2.11：贯穿案例复盘

回到本章贯穿案例：在线课堂互动系统。

请把下面七个子需求分别映射到本章学过的数据结构，并写出理由：

子需求	你的结构选择	主要操作	复杂度	放弃其他结构的理由
学生加入课堂，不能重复加入
按学生 id 查询学生信息
保存所有问题，课后按提交顺序导出
学生撤回自己最近一次问题
老师按提交顺序处理普通问题
紧急问题优先处理
按时间段导出问题记录

然后写一段 200 字以内的总结：

这个系统不能只用一个 list 的原因是：
这个系统不能只用一个 dict 的原因是：
最需要维护的不变量是：
我最担心 agent 写错的是：

评分重点：能否把现实需求翻译成结构信号，而不是机械背结构名字。

---

评分标准

维度	合格表现	不合格表现
操作建模	能列出高频操作、规模和约束	只写结构名字
经典知识	能说明接口、不变量和复杂度	只说"这个更快"
Python 理解	能识别 list、dict、set、deque、heapq 的适用边界	把所有结构都当列表
取舍说明	能说明为什么不用其他结构	没有比较
Agent 审查	能指出 agent 输出的遗漏、误判或隐藏成本	直接复制 agent 答案

---

小结

第二章的核心不是"哪个数据结构最好"，而是：

• 先看操作需求。
• 再看规模和频率。
• 再比较候选结构。
• 最后审查实现和复杂度。

当 agent 能快速写代码时，这套判断更重要。代码能跑只是第一层；数据组织是否正确，才决定它能不能在真实规模下工作。

---

上一节：2.10 从接口到缓存

下一章：第3章 排序与查找