1ADT：值、操作与语义契约
闭卷重建ADT：值、操作与语义契约的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2表示不变量与封装边界
闭卷重建表示不变量与封装边界的ADT、表示不变量、操作与复杂度。
3渐进复杂度与增长率
闭卷重建渐进复杂度与增长率的ADT、表示不变量、操作与复杂度。
4最坏、均摊与期望成本
闭卷重建最坏、均摊与期望成本的ADT、表示不变量、操作与复杂度。
5空间复杂度与内存布局
闭卷重建空间复杂度与内存布局的ADT、表示不变量、操作与复杂度。
6选择结构的决策表
闭卷重建选择结构的决策表的ADT、表示不变量、操作与复杂度。
7实验：契约与操作计数器
闭卷重建实验：契约与操作计数器的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：表示不变量描述每个公开操作前后内部状态必须满足的条件，封装阻止调用者绕过操作破坏它；实验：给动态数组写0≤size≤capacity及有效区间不变量并在每次扩缩容后断言；边界：只在构造时检查不够；返回内部可变引用也会让外部破坏不变量。
机制：ADT定义值集合、操作、前置条件、后置条件和可观察行为，实现可以替换而不改变调用者语义；实验：为栈写push/pop/top/isEmpty契约并用两个不同内部实现互测；边界：接口相同不代表语义相同，空结构行为、元素身份与异常保证必须写清。
机制：最坏成本约束单次操作，均摊成本约束操作序列，期望成本依赖随机变量和概率假设；实验：对倍增动态数组用聚合法计算n次append总搬移次数；边界：均摊O(1)不代表每次O(1)，期望O(1)也不等于对抗输入下有确定上界。
机制：O、Ω、Θ分别给渐进上界、下界和紧确界，忽略常数是比较增长率而非否认常数成本；实验：给三段循环逐层计数原始操作并化简到紧确界；边界：把最坏O(n)写成所有输入都需要n步，或把两个连续循环相乘，都是常见错误。
机制：按操作频率、顺序需求、键分布、更新模式、内存局部性和并发边界选择结构，而不是背万能结构；实验：给日志缓冲、LRU缓存和路由前缀三个场景写操作权重再选结构；边界：只看单个操作的Big-O会忽略构建成本、常数、缓存和迭代语义。
机制：空间分析区分输入、辅助空间、容量冗余、对象头与指针；连续布局和节点布局影响缓存与碎片；实验：比较n个整数在数组和双链表中的有效载荷与结构开销；边界：只数元素数量会漏指针、对齐和递归栈，Python对象成本也不能直接套C数组。
机制：实现可插拔计数器包装器，验证两个栈实现行为一致并统计操作序列成本；实验：覆盖正常序列、空结构、重复值和长序列测试；边界：测试最终值不足以证明契约，异常类型、状态是否改变和迭代顺序也要验收。