16.1 图的基本概念·选择题讲评
6 点无向图有两个连通分量，生成森林有几条边？
考研计算机 408 全程课 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 章9第 2 章8第 3 章14第 4 章20第 5 章7第 6 章21第 7 章20第 8 章21第 9 章25第 10 章9第 11 章8第 12 章12第 13 章16第 14 章23第 15 章15第 16 章21第 17 章9第 18 章10第 19 章8第 20 章1第 21 章4第 22 章4第 23 章6第 24 章2第 25 章1第 26 章3第 27 章14第 28 章14第 29 章18第 30 章8第 31 章19第 32 章13第 33 章16第 34 章3第 35 章6第 36 章8第 37 章8第 38 章9第 39 章7第 40 章8第 41 章8第 42 章19第 43 章19第 44 章9第 45 章10第 46 章4第 47 章4第 48 章4第 49 章4第 50 章16第 51 章20第 52 章16第 53 章12第 54 章14第 55 章25第 56 章14第 57 章10第 58 章4第 59 章6
第 1 页 · 正面（题目）
26.1 图的基本概念·综合题讲评
判断 4,4,1,1,0 是否为5点简单图度序列？
36.2.1 邻接矩阵法
4点无向完全图矩阵有多少个1？
46.2.2 邻接表法
顶点0邻接表为[3,1,2]，若按存储顺序BFS，第一层访问顺序如何？
56.2.3 十字链表、邻接多重表
说明删除 A→B 时需更新哪些链？
66.2.5 图的基本操作
设计 removeVertex(v) 的三组测试：孤点、普通点、与所有点相连的点，并检查边数变化。
76.2 邻接矩阵法、邻接表法·选择题讲评
稀疏有向图频繁枚举入边，应如何设计？
86.2 邻接矩阵法、邻接表法·综合题讲评
将有向表0:[1,2],1:[2],2:[]写成矩阵，并求各点入出度？
96.3.1 图的广度优先遍历
网格每步代价1，如何求最少步？
106.3.2 图的深度优先遍历
有向边0→1,1→2,2→0，用三色DFS在哪条边发现环？
第 1 页 · 背面（答案）
答案否：度4的两个点必须连接所有其他点，使度0顶点矛盾。
答案6-2=4。说明每个分量分别是一棵树。
答案3、1、2；换排序会改变序列。
答案12，因为6条边各出现两次。
必须给出逐步状态、算法不变量和边界检查。
答案：A 的出边链和 B 的入边链，并释放唯一弧结点。
答案行矩阵011/001/000，出度2,1,0；入度0,1,2。
答案可同时维护正向和逆向邻接表，空间仍 O(V+E)。
答案处理2→0时0仍为灰色，发现回边。
答案把格子作顶点做BFS，入队时标记并记录前驱。
第 2 页 · 正面（题目）
116.3 图的广度优先遍历、图的深度优先遍历·选择题讲评
邻接顺序反转，BFS距离会变吗？
126.3 图的广度优先遍历、图的深度优先遍历·综合题讲评
判断边01,12,23,30,02的图？
136.4.1 最小生成树
边01:1,12:2,02:2,23:5，MST权多少？
146.4.2 最短路径问题_BFS算法、最短路径问题_Dijkstra算法、最短路径问题_Floyd算法
边0→1=4,0→2=10,1→2=-6应选什么算法？
156.4.3 有向无环图描述表达式
为 (a*b)+(a*b)+c 画DAG，？
166.4.4 拓扑排序
课程A、B均为C前置，C为D前置，列出全部拓扑序？
176.4.5 关键路径
若存在两条长度均10的关键路径，只缩短其中一条1单位，总工期如何？
186.4 最小生成树、最短路径问题_BFS算法·选择题讲评
稠密图全源最短路且无负环，常选什么？
196.4 最小生成树、最短路径问题_BFS算法·综合题讲评
把边1→3改为1，重新求0到3？
206.1.1 图的基本概念
5 个顶点的简单无向图最多多少边？
第 2 页 · 背面（答案）
答案否，0-1-2-0构成三角形奇环。
答案不会；同长度路径的父结点和访问次序可能改变。
答案不能用Dijkstra；可用Bellman-Ford，若全源也可Floyd且检查负环。
答案8，前3点选两条权1、2边，再接23。
答案A B C D与B A C D。
答案只保留一个乘法结点，并被两个位置引用。
答案Floyd，O(V³)并能处理负边。
答案仍可能是10，由另一条决定。
答案10。若连通，最少边4；写出两种能取等号的图。
答案路径0-1-3，距离3；写出被更新的d和parent。