全库自测与掌握检查

使用方法

先闭卷作答，再核对要点。每题 4 分，共 100 分；达到 80 分才算通过，并且第 3、8、12、15、19 题（复杂度、可变性、哈希、堆、图）不得为 0。完成 依赖任务调度器 的测试也是必需证据。

评分不是为了背术语，而是确认你能从操作选择结构、维护不变量、解释成本并承认工程边界。

闭卷题

抽象与复杂度

1. 区分 ADT、具体数据结构和算法，并用队列举例。
2. 为工具注册表写三条不变量、一条失败后置条件。
3. 为什么 O(1) 不表示一条机器指令？平均、最坏和摊还分别回答什么？
4. list.append 为何常写“摊还 O(1)”？这是否保证每次耗时相同？
5. sys.getsizeof(list) 为什么不是所有嵌套元素的总内存？怎样获取更有意义的测量证据？

线性结构与状态

6. Python list 的按下标读、中间插入、成员查找各是什么常见成本模型？
7. 链表“插入 O(1)”隐含什么前提？为什么普通 Python 工程通常不手写链表？
8. 画出 a = [[1]]; b = a.copy(); b[0].append(2) 的引用关系，并写最终 a。
9. iterable、iterator、generator 有何关系？为什么生成器可能只能消费一次？
10. bisect_left 与 bisect_right 对重复值返回的边界不同在哪里？insort 总体为什么仍为 O(n)？

栈、队列、哈希与优先级

11. 栈、FIFO 队列、有界 deque 各适合什么 Agent 场景？内存 deque 缺少哪些可靠队列语义？
12. 字典/集合平均 O(1) 的限制是什么？为什么可变列表不能作键，hash() 不能作持久 ID？
13. 字典保持插入顺序是否等于按键排序？集合输出如何变成确定性结果？
14. 去重与业务幂等有什么区别？为什么单进程 set 不能保护多实例写操作？
15. 堆维护什么不变量？为什么它不是完整排序列表？同优先级 payload 如何避免 TypeError？
16. 数值优先级能否绕过依赖？什么是低优先级饥饿？

树、图与工程组合

17. 树的根、叶、深度、子树分别是什么？DFS 与 BFS 的辅助结构有何不同？
18. 图遍历为什么要在入队/入栈时维护 visited？邻接表和矩阵如何选择？
19. “A 依赖 B”在前驱表和后继表中分别怎样表示？Kahn 拓扑推进的入度如何变化？
20. 图中有环是否表示任何节点都不能执行？为什么 blocked 节点不一定都是环成员？
21. 组合 dict + indegree + adjacency + heap 时，哪个是真相源、哪些是派生索引？
22. 无界消息历史、seen set 和 ready heap 各需要什么容量/清理策略？
23. 如何设计同一输入的确定性调度输出？至少列三项规则。
24. 性能变慢时，为什么不应只看到双层循环就重写？给出证据链。
25. 向量数据库为什么不能由本课程的 list/dict/heap 直接替代？

核对要点

展开核对

1. ADT 规定操作语义；结构是表示；算法实现操作。队列可由 deque 或持久消息系统实现。
2. 键唯一、键与对象名称一致、辅助索引同步；失败后所有索引保持调用前状态。
3. Big O 描述随规模增长；平均依赖分布/假设；最坏取最高成本；摊还把一串操作总成本平均。
4. 动态数组偶尔扩容；连续操作总成本可平均，但单次可能扩容。
5. 它只计对象直接占用；记录版本和工作负载，使用 tracemalloc/进程指标并解释范围。
6. 常见模型分别为 O(1)、O(n)、O(n)。
7. 已持有插入位置节点；查节点仍可能 O(n)，Python 对象/引用开销和边界 bug 常抵消价值。
8. 两个外层列表共享内层列表；最终 a == [[1, 2]]。
9. iterable 产生 iterator；iterator 用 next 消费；generator 是保存状态的 iterator，耗尽后不自动重置。
10. left 在等值区左侧、right 在右侧；定位 O(log n)，列表移动 O(n)。
11. 回退、任务 FIFO、最近窗口；缺持久化、确认、租约、重试、恢复和多机一致性。
12. 平均并非最坏保证；键需稳定哈希/相等；内置 hash 不承诺跨进程稳定。
13. 不是排序；使用稳定可比较键显式 sorted，或独立保序结构。
14. 去重识别重复标识；幂等保证重复业务执行无额外副作用，需要持久原子记录。
15. 顶部为最小且父子满足堆序；其余不全排序；加入唯一序号/稳定 ID 打破平局。
16. 不能；只在 ready 中比较。持续高优先级到达可能让低级任务永不执行。
17. DFS 用栈，BFS 用队列；两者都需节点/深度上限。
18. 防环和多路径重复；稀疏图通常邻接表，稠密且频繁查边才考虑矩阵。
19. 前驱表 A: {B}；后继表 B: {A}。完成前驱后将后继入度减一。
20. 无关 DAG 分量可先推进；下游可能只依赖环，并非环路径成员。
21. Task 映射是真相源，其余可由它重建；更新需单一入口和不变量。
22. 明确条目/字节上限、拒绝/淘汰/持久化/背压语义及审计影响。
23. 稳定 ID、固定边方向、平局键、不依赖 set 顺序、相同输入和版本。
24. 先记录规模、操作频率和基线，用 profiler/timeit/tracemalloc 定位，改热点并同负载复测。
25. 专门索引还涉及近似检索、过滤、持久化、分片、召回/延迟权衡与并发更新。

现场任务 A：有界事件窗口

实现一个本地 EventWindow：

• 只保留最近 100 条 (timestamp, event_id, category)；
• event_id 在当前窗口唯一；
• 可按 category 统计计数；
• 可用二分返回闭区间时间事件；
• 事件按 timestamp 非递减，等时间按 event_id；
• 添加失败后，deque/list、seen set 和 Counter 保持原样；
• 至少 12 项测试覆盖容量淘汰、重复、乱序、时间边界、输入不修改和确定性。

先写结构选择卡和不变量，再实现。解释为什么淘汰事件必须同时从 seen 与计数器移除，为什么这仍不是审计日志。

现场任务 B：迁移设计

现有程序每次用 list 扫描 100 万工具调用，只保留最近结果并频繁按 ID 查询。写一份迁移设计：

1. 给出当前主要操作和复杂度；
2. 选择真相源、按 ID 索引和容量窗口；
3. 定义多结构更新失败时的一致性；
4. 说明何时单进程结构不再足够；
5. 给出基准数据生成、性能测量和回归验证方法；
6. 列出你有意不解决的问题。

不得编造“快多少倍”；没有真实测量只能给增长模型和实验计划。

最终掌握标准

• 能从操作、规模、顺序、重复、容量和并发选择结构。
• 能解释时间/空间、平均/最坏/摊还，而不把 Big O 当秒表。
• 能处理可变性、浅拷贝、迭代器耗尽和迭代时修改。
• 能正确使用 deque、dict/set/Counter、bisect、heapq。
• 能写树 DFS/BFS 与 DAG 拓扑推进，并准确解释环。
• 能为组合结构定义真相源、派生索引和不变量。
• 依赖任务调度器 24 项测试通过，且能解释复杂度。
• 能明确内存示例不具备生产持久化、并发、恢复和权限语义。

未达标时回到对应独立条目重做练习，不用继续增加高级树和竞赛算法掩盖基础缺口。

下一步

• 回到 数据结构基础目录。
• 数据交换进入 JSON；向量与索引进入 向量基础 和 向量数据库。
• 工作流执行与恢复进入 工作流自动化。

参考资料

本页整合各节的掌握检查；具体事实和版本来源见对应课程条目。获取日期：2026-07-14。