CSP-J 卷

有 $10$ 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

在无向图中，所有顶点的度数之和等于（ ）。

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）

对于有 $n$ 个顶点、$m$ 条边的无向连通图 ($m > n$)，需要删掉（ ）条边才能使其成为一棵树。

以 a 为起点，对右边的无向图进行深度优先遍历，则 b、c、d、e 四个点中有可能作为最后一个遍历到的点的个数为（ ）。

考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

考虑一个有向无环图，该图包含 4 条有向边：(1,2), (1,3), (2,4)和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

如图是一张包含 $7$ 个顶点的有向图。如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？

深度优先搜索（DFS，Depth First Search 的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。（ ）

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。

在⽆向图中，所有顶点的度数之和等于边数的两倍。

下列选项中，哪个不可能是下图的广度优先遍历序列（ ）。

一个连通的简单有向图，共有$28$条边，则该图至少有（ ）个顶点。

在无权图中从起点执行 BFS 时，某个顶点第一次被访问到的层数等于起点到该顶点经过的最少边数。

假设 $n$ 是图的顶点个数，$m$ 是图的边数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面四个选项中哪一项的渐近时间复杂度最小？（ ）

图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？（ ）

G 是一个非连通无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

给定一个简单有向图 G，判断其中是否存在环路的下列说法哪个最准确？（ ）

一个简单无向图有 $10$ 个结点、$30$ 条边。再增加多少条边可以成为完全图。（ ）

如下图所示的邻接表结构，表示的是下列哪个选项中的图？

一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，则下面说法错误的是（ ）。

对⼀个包含 $V$ 个顶点、$E$ 条边的图，执⾏⼴度优先搜索，其最优时间复杂度是（ ）。

$n$个顶点的无向完全图，有$n^{(n-2)}$棵生成树。