CSP-S 卷

以下哪个结构可以用来存储图（ ）

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

具有 $n$ 个顶点、$e$ 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，$24$ 个顶点的二分图至多有（ ）条边。

$G$ 是一个非连通简单无向图（没有自环和重边），共有 $36$ 条边，则该图至少有（ ）个点。

有如下的有向图，结点为 A、B、……、J，其中每条边的长度都标在图中。则结点 A 到结点 J 的最短路径长度为（ ）。

强连通图的性质不包括（ ）。

以下连通无向图中，（ ）一定可以用不超过两种颜色进行染色。

假设有一个包含 $n$ 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）

设有一个有 $10$ 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 $4$ 的环？

如图是一张包含 $6$ 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 $6$ 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（ ）

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

一个图，不管是否连通，都可以使用深度优先搜索算法进行遍历。（ ）

一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。（ ）

一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。

邻接表和邻接矩阵都是图的存储形式。为了操作时间复杂度考虑，同一个图可以同时维护两种存储形式。

如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。

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

邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。

下⾯哪⼀个可能是下图的深度优先遍历序列（ ）。

使⽤邻接矩阵存储⼀个有 $V$ 个顶点、$E$ 条边的图，对该图进⾏⼀次完整的 $BFS$ 遍历，时间复杂度为 $O(V+E)$ 。

⼀个简单⽆向图 $G$ 有 $36$ 条边，且每个顶点的度数都为 $4$，则图 $G$ 的顶点个数为（ ）。

下⾯哪⼀个可能是下图的深度优先遍历序列（ ）。

在无向连通图中删除一条边，该图就一定变成非连通图。

在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。

在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。

从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 $4$ 个序列中符合广度优先的序列有几个？（ ）

{v1 v2 v3 v4 v5}，{v1 v2 v4 v3 v5}，{v1 v4 v2 v3 v5}，{v1 v2 v4 v5 v3}

简单有向图有 n 个顶点和 e 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 u 的度的时间复杂度一样。（ ）

用下面的邻接表结构保存一个有向图 G，InfoType 和 VertexType 是定义好的类。设 G 有 $n$ 个顶点、$e$ 条弧，则求图 G 中某个顶点 u（其顶点序号为 $k$）的度的算法复杂度是（ ）。

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;

下面关于图的说法正确的是（ ）。

图的存储和遍历算法，下面说法错误的是（ ）。

如下图所示的邻接矩阵（inf 表示无穷大），表示的是下列哪个选项中的图？

非连通图不能使用广度优先搜索算法进行遍历。（ ）

使⽤邻接矩阵表达 $n$ 个顶点的有向图 ，则该矩阵的大小为（ ）

使⽤邻接表表达⼀个⽆向简单图，图中包含 v 个顶点、e 条边，则该表中边节点的个数为（ ）。

可以使⽤深度优先搜索算法判断图的连通性。

对于⼀个具有 $n$ 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩为（ ）。