CSP-S 卷
复刻
① 本卷为客观题单卷，合计 37 题 · 74 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。
判 分 报 告
客 观 题
以下哪个结构可以用来存储图（ ）
C：邻接矩阵。邻接矩阵（O(V²) 空间、O(1) 判边）和邻接表（O(V+E) 空间）都可存图；栈/队列/二叉树不能直接存图结构。
是一个非连通无向图（没有重边和自环），共有 条边，则该图至少有（ ）个顶点
A：9。非连通图加最少的顶点数：n 顶点非连通图最少边数 = n-1 即可连通；28 条边的图至少 9 顶点（连通子图 8 顶点最多 28 条边 K8=28）。
具有 个顶点、 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。
A：Θ(n+e)。邻接表 DFS 每结点访问一次、每边检查一次，O(n+e)。
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么， 个顶点的二分图至多有（ ）条边。
A：144。n 顶点二分图最大边数 = ⌊n/2⌋·⌈n/2⌉ = 12·12 = 144。
是一个非连通简单无向图（没有自环和重边），共有 条边，则该图至少有（ ）个点。
C：10。n 顶点非连通图边数最多 = C(n-1,2)（K_{n-1}）+0（孤立点）；36=C(n-1,2) → n-1=9 → n=10。
有如下的有向图，结点为 A、B、……、J，其中每条边的长度都标在图中。则结点 A 到结点 J 的最短路径长度为（ ）。
B：二进制加法 01000000=64。详见 2021-S-Q2 已修。
强连通图的性质不包括（ ）。
B：任意两个顶点之间都有边相连——错误。强连通只要求路径可达，不要求直接有边（路径可经中间顶点）；C 是强连通定义。
以下连通无向图中，（ ）一定可以用不超过两种颜色进行染色。
A：完全三叉树。二叉树/三叉树可二色染色；平面图需四色定理。
假设有一个包含 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）
D：边数是奇数。欧拉图要求所有顶点度数为偶数且连通（A、B 正确），存在欧拉回路（C 正确），边数可奇可偶。
设有一个有 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 的环？
C：630。10 顶点完全图长度 4 的环数 = C(10,4)×3! / 2 = 210×3 = 630（4 个顶点选法 × 3! 排列 / 2 正反方向）。
如图是一张包含 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（ ）
C：3。删一条边使图有拓扑序（消除某环路）；3 条候选边。
对于一个包含 个结点和 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？
D：以上都不对。DAG 拓扑序数可多种（具体依赖图），A 错（仅特定图）、B 错（最多 n!）、C 错（n-m 无意义）。
一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历。（ ）
对。图不管是否连通，都可对每个连通分量分别执行 DFS：从一个未访问顶点深搜完整个分量，再找下一个未访问顶点开新一轮，直至全部访问。
一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。（ ）
对。以人为顶点、两人之间认识为边，社交网络中人与人的关系可抽象成无向图，图中连通块即社交圈子，用图表达社交网络完全可行。故对，故对。
一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。
错。城际交通可能双向通行、多方式并线，抽象后不一定是简单有向图；且简单图丢失了距离、容量等信息，不足以完整表达交通网络。故说法错误。
邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑，同一个图可以同时维护两种存储形式。
对。同一张图可以同时维护邻接表和邻接矩阵两种存储：遍历顶点的边用邻接表更快、判断两点是否相邻用矩阵更快，以空间换时间完全可行，故对。
如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。
错。简单图不含车道数、方向限制、交通容量等细节，仅表示城市间的连通关系，无法满足车道级导航的需求，抽象成简单图信息不足，故错。
下列选项中，哪个不可能是下图的深度优先遍历序列()。
B：DFS 能走就走：B 中 5→7→8→9 可走通，回溯后 1→2，而 2 的未访问邻点 3 应先于 4 访问，B 却先 4 后 3，破坏回溯顺序。
邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。
错。不能说邻接表总比邻接矩阵复杂度低：判断两点是否有边矩阵 O(1) 更快，稠密图矩阵空间也更省，笼统说法错误；两者各有适用场景。
下⾯哪⼀个可能是下图的深度优先遍历序列（ ）。
B：B 的深搜 1→5→8→9，回溯到 8 访问 7，再回溯到 1 访问 4，最后从未访问的 6 出发走 3、2；A 在 6 后应访 9 而非 8，C、D 也有类似跳步错误。
使⽤邻接矩阵存储⼀个有 个顶点、 条边的图，对该图进⾏⼀次完整的 遍历，时间复杂度为 。
错。邻接矩阵存图时 BFS 判断相邻要扫整行，复杂度 O(V²)，不是 O(V+E)；O(V+E) 是邻接表的复杂度；故用邻接矩阵做 BFS 应为 O(V²)。
⼀个简单⽆向图 有 条边，且每个顶点的度数都为 ，则图 的顶点个数为（ ）。
C：每点度数均为 4，由度数和等于 2 倍边数得 4V=2×36=72，故顶点数 V=18；由握手引理：度数和等于 2 倍边数，故选 C。
下⾯哪⼀个可能是下图的深度优先遍历序列（ ）。
B：按 DFS 回溯规则：A 在 4 之后应先访问其未访问邻点 7 而非 8；C 在 3 后应继续访问可达点 1；D 在 5 后应访问 4；只有 B 符合。
在无向连通图中删除一条边，该图就一定变成非连通图。
错。删除非桥边后图依然连通，只有删除桥（割边）才会使无向连通图变得不连通；桥是使图断开的关键边；非桥边不在任何割集上。故说法错误。
在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。
对。DFS 中每个顶点总是优先选择编号更小的未访问邻点，选择规则固定，从指定起点出发的遍历序列唯一；邻接表按编号升序排列时序列确定。
在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。
对。无向连通图中从任意顶点做 DFS 会访问所有可达顶点，得到的生成树覆盖图中全部顶点；生成树是连通图边数最少的子图。故正确，故对。
从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 个序列中符合广度优先的序列有几个？（ ）
{v1 v2 v3 v4 v5}，{v1 v2 v4 v3 v5}，{v1 v4 v2 v3 v5}，{v1 v2 v4 v5 v3}
B：图中 v1 的邻点是 v2、v4，第二层是 v5、v3。BFS 要求第一层先于第二层：序列 1 把第二层的 v3 放在第一层 v4 之前，不符合；序列 2、3、4 均满足，共 3 个。
简单有向图有 n 个顶点和 e 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 u 的度的时间复杂度一样。（ ）
错。邻接矩阵求 u 的度要扫一行 O(n)；邻接表无向图数 u 的链表即可 O(deg(u))，有向图求入度还需遍历所有弧，二者复杂度不同。
用下面的邻接表结构保存一个有向图 G，InfoType 和 VertexType 是定义好的类。设 G 有 个顶点、 条弧，则求图 G 中某个顶点 u（其顶点序号为 ）的度的算法复杂度是（ ）。
01typedef struct ArcNode{ 02 int adjvex; // 该弧所指向的顶点的位置 03 struct ArcNode *nextarc; // 指向下一条弧的指针 04 InfoType *info; // 该弧相关信息的指针 05} ArcNode; 06typedef struct VNode{ 07 VertexType data; // 顶点信息 08 ArcNode *firstarc; // 指向第一条依附该顶点的弧 09} VNode, AdjList[MAX_VERTEX_NUM]; 10typedef struct{ 11 AdjList vertices; 12 int vexnum, arcnum; 13 int kind; // 图的种类标志 14} ALGraph;
B：邻接表求出度只需数顶点 u 的弧链表长度，最坏 O(e)；求入度要扫描各顶点弧链表统计指向 u 的弧，也以弧数 e 为主，故度为 O(e)。
下面关于图的说法正确的是（ ）。
D：有向图中每条边贡献一个出度和一个入度，故所有顶点入度出度之和等于边数的两倍；A、B、C 对环与强连通的表述不严谨或不完整，故选 D。
图的存储和遍历算法，下面说法错误的是（ ）。
B：图的 DFS 借助栈（递归或显式栈）实现，与二叉树先序遍历原理一致，B 说原理不同是错的；A、C、D 均正确，故选 B。故 B 正确。
如下图所示的邻接矩阵（inf 表示无穷大），表示的是下列哪个选项中的图？
A：由邻接矩阵读出：0 连 2（权 12）、3（权 30）；1 无边；2 连 4（权 32）等（对称补全），对照选项只有甲满足这些带权边。
非连通图不能使用广度优先搜索算法进行遍历。（ ）
错。非连通图可以分别对每个连通分量各做一次 BFS，把所有分量遍历完即可访问全部顶点，因此非连通图同样能 BFS 遍历。故说法正确。
使⽤邻接矩阵表达 个顶点的有向图 ，则该矩阵的大小为（ ）
B：n×n。邻接矩阵按行、列各对应一个顶点，共 n 行 n 列 n² 个元素；有向图同样如此，只是 a[i][j] 与 a[j][i] 表示两条方向相反的边，矩阵不再对称。
使⽤邻接表表达⼀个⽆向简单图，图中包含 v 个顶点、e 条边，则该表中边节点的个数为（ ）。
C：2×e。无向图中每条边会在两个端点的邻接链表中各存一个边节点，所以边节点总数是 2e；有向图的边只存一次，才是 e 个节点。
可以使⽤深度优先搜索算法判断图的连通性。
A：正确。从任一顶点 DFS，若访问顶点数等于总顶点数则图连通；若存在未访问顶点，说明有顶点无法到达，图不连通，DFS 与 BFS 判断能力相同。
对于⼀个具有 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩为（ ）。
B：n×n。邻接矩阵行、列各对应一个顶点，共 n² 个元素；无向图的矩阵虽沿对角线对称，存储时仍按完整的 n×n 分配。