1图模型与边语义
闭卷重建图模型与边语义的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2邻接矩阵与邻接表
闭卷重建邻接矩阵与邻接表的ADT、表示不变量、操作与复杂度。
3BFS与最短边数
闭卷重建BFS与最短边数的ADT、表示不变量、操作与复杂度。
4DFS、时间戳与边分类
闭卷重建DFS、时间戳与边分类的ADT、表示不变量、操作与复杂度。
5连通分量与可达性
闭卷重建连通分量与可达性的ADT、表示不变量、操作与复杂度。
6拓扑排序与依赖环
闭卷重建拓扑排序与依赖环的ADT、表示不变量、操作与复杂度。
7实验：图容器与BFS/DFS
闭卷重建实验：图容器与BFS/DFS的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：矩阵查询单边O(1)但占O(V²)，邻接表占O(V+E)且遍历邻居高效；实验：对稀疏与稠密图计算两种表示空间和扫描成本；边界：用Python对象估算内存时要含列表/整数对象开销，理论项数不等于字节。
机制：有向/无向、带权/无权、简单图/多重图决定邻接与算法；顶点标签不等于连续索引；实验：把课程依赖、道路和社交关注分别建模并说明边方向；边界：无向边存两条邻接记录但仍是一条逻辑边，入度出度也不能混。
机制：DFS沿一条路径深入再回溯，颜色和发现/完成时间支持环检测与拓扑性质；实验：用显式栈模拟递归DFS并输出进入退出事件；边界：只在弹栈时标记会重复展开；有向图灰边才表示当前递归路径成环。
机制：BFS用FIFO按距离层扩展，首次发现即确定无权图最短边数并设置父节点；实验：逐队列运行BFS输出距离、父树和不可达顶点；边界：入队时不标记会让同一顶点重复入队，带负/任意权图也不能直接用BFS。
机制：DAG可按入度为0逐步删除或DFS逆完成序得到拓扑序，处理数不足V说明有环；实验：对课程先修图输出稳定拓扑序并报告环；边界：拓扑序通常不唯一；用队列或堆会影响稳定顺序但不改变合法性。
机制：无向图每次从未访问点遍历得到一个分量，有向图的强连通需更强算法；实验：枚举无向分量并为多次可达查询预处理分量ID；边界：弱连通不能替代强连通，孤立顶点也是单独分量。
机制：实现邻接表、加边、BFS距离/父树、迭代DFS和Kahn拓扑；实验：覆盖孤立点、平行输入去重、非连通和有向环测试；边界：顶点合法性、无向边双写和遍历邻居顺序必须固定。