2.11 综合练习

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

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

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

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

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

---

基础练习

练习 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章 排序与查找