CSP-J 卷
复刻
① 本卷为客观题单卷，合计 24 题 · 48 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。
判 分 报 告
客 观 题
有 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
A：9。n 个顶点无向图连通的最小边数 = n-1（生成树），故 10 顶点至少 9 条边；最少 9 条就是生成树。
在无向图中，所有顶点的度数之和等于（ ）。
B：图的边数的两倍。无向图每条边贡献 2 个端点的度数，故度数和 = 2×边数。
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）
C：栈。「FILO」后进先出是栈；队列是 FIFO。
对于有 个顶点、 条边的无向连通图 ()，需要删掉（ ）条边才能使其成为一棵树。
D：m-n+1。树有 n-1 条边，需删 m-(n-1)=m-n+1 条；连通图删去非树边得到生成树。
以 a 为起点，对右边的无向图进行深度优先遍历，则 b、c、d、e 四个点中有可能作为最后一个遍历到的点的个数为（ ）。
B：2。深度优先遍历从 a 出发，最后被访问的点是 dfs 路径末端。具体哪个点为最后访问取决于图结构与邻接顺序（无图无法精确），按官方答案为 2 个点可作末端。
考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A：N-1。N 顶点有向连通图最少边数 = N-1（生成树），邻接矩阵每条边对应一个非零元素。
考虑一个有向无环图，该图包含 4 条有向边：(1,2), (1,3), (2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）
B：1,2,3,4。DAG 边 (1,2)(1,3)(2,4)(3,4)，拓扑序需 1 在 2/3 前、2/3 在 4 前；只有 1,2,3,4 满足；A 反序错、C/D 顺序错。
如图是一张包含 个顶点的有向图。如果要删除其中一些边，使得从节点 到节点 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？
D：4。最少删除边集切断 1→7 路径（最小割），按图结构有 4 种方案。
深度优先搜索（DFS，Depth First Search 的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。（ ）
A：正确。DFS 沿一条分支递归深入到底再回溯，配合 visited 标记保证每个节点只访问一次，是图与树的经典遍历算法。
下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。
A：DFS 走到 8 后应继续沿边深入其未访问邻点 9，A 却跳到 6，违反能走就走的原则，故 A 不可能是该图的 DFS 序列，故选 A。
邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。
A：正确。CCF 官方答案判正确。邻接表遍历单点所有边对出边 O(deg(u)) 比邻接矩阵扫描 O(V) 更低；邻接矩阵判两点是否有边 O(1) 比邻接表扫描 O(deg(u)) 更低；两个比较均成立。
在⽆向图中，所有顶点的度数之和等于边数的两倍。
对。无向图中每条边给两个端点的度各贡献 1，故所有顶点度数之和等于边数的两倍；这是握手引理在图论中的直接应用；该性质对任何无向图均成立。
下列选项中，哪个不可能是下图的广度优先遍历序列（ ）。
B：BFS 按层次遍历，6 所在层在 8 之前，B 把 8 排在 6 前面，不符合层次顺序，故 B 不可能是 BFS 序列。故 B 错误。
一个连通的简单有向图，共有条边，则该图至少有（ ）个顶点。
B：连通简单有向图 28 条边，5 个顶点最多 5×4=20 条边放不下，6 个顶点最多 6×5=30 条边，故至少 6 个顶点，故选 B。
在无权图中从起点执行 BFS 时，某个顶点第一次被访问到的层数等于起点到该顶点经过的最少边数。
对。BFS 按层扩展，顶点第一次被访问时的层数等于起点到该顶点的最少边数，即最短路径长度；这也是 BFS 求无权图最短路的原理，故对。
假设 是图的顶点个数， 是图的边数，为求解某一问题有下面四种不同时间复杂度的算法。对于 的稀疏图而言，下面四个选项中哪一项的渐近时间复杂度最小？（ ）
A：O(m√(log n · log log n))。m=Θ(n) 稀疏图下 A 项渐近最小（亚线性复杂度）。
图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？（ ）
B：BFS 按层扩展，先访问的顶点先扩展其邻点，需用先进先出的队列存放待访问结点，配合访问标志数组防止重复入队；栈、堆、哈希表都不符合。
G 是一个非连通无向图，共有 条边，则该图至少有（ ）个顶点。
D：非连通则至少两个连通分量。9 个顶点可分成 K8（C(8,2)=28 条边）加 1 个孤立顶点；8 个顶点非连通最多 C(7,2)=21 条边，故最少 9 个顶点。
给定一个简单有向图 G，判断其中是否存在环路的下列说法哪个最准确？（ ）
D：DFS 判返祖边、BFS 做拓扑排序都能判有向图环，复杂度同为 O(n+e)，谁更快取决于图的形态与环的位置，无法一概而论，选不确定。
一个简单无向图有 个结点、 条边。再增加多少条边可以成为完全图。（ ）
B：10 个结点的简单无向完全图每对顶点之间都有一条边，共 C(10,2)=45 条；现有 30 条边，还需再增加 45−30=15 条。
如下图所示的邻接表结构，表示的是下列哪个选项中的图？
C：由邻接表读出：V1 连 V4、V2；V2 连 V5、V3、V1；V3 连 V5、V4、V2；V4 连 V1、V3；V5 连 V2、V3，对照四个图只有选项丙满足。
一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（ ）。
D：迷宫内与起点连通的结点经 S 中转必与终点连通（连通性不要求路径不相交），但连通块内可能含环（如 lollipop 结构），不能抽象成无向无环图，D 错误；A、B、C 均正确。
对⼀个包含 个顶点、 条边的图，执⾏⼴度优先搜索，其最优时间复杂度是（ ）。
B：O(V+E)。BFS 每个顶点入队一次、邻接表中每条边被检查一次，最优与最坏均为 O(V+E)；稠密图下等价于 O(V²)。
个顶点的无向完全图，有棵生成树。
A：正确。Cayley 公式：n 个顶点的无向完全图 Kₙ 的生成树数量为 nⁿ⁻²，如 K₃ 有 3 棵生成树，K₄ 有 16 棵。