2-41
具有5个顶点的有向完全图有多少条弧？(2分)
A.10
B.16
C.20
D.25
作者
DS课程组
单位
浙江大学
2-42
在N个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍？(2分)
A.1
B.2
C.(N−1)/2
D.N−1
作者
DS课程组
单位
浙江大学
2-43
对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？(2分)
A.N−1
B.N
C.N+1
D.N/2
作者
DS课程组
单位
浙江大学
2-44
具有N（N>0）个顶点的无向图至少有多少个连通分量？(2分)
A.0
B.1
C.N−1
D.N
作者
DS课程组
单位
浙江大学
2-45
具有N（N>0）个顶点的无向图至多有多少个连通分量？(2分)
A.0
B.1
C.N−1
D.N
作者
DS课程组
单位
浙江大学
2-46
一个有N个顶点的强连通图至少有多少条边？(2分)
A.N−1
B.N
C.N+1
D.N(N−1)
作者
DS课程组
单位
浙江大学
2-47
如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为多少？(3分)
A.7
B.8
C.9
D.10
作者
DS课程组
单位
浙江大学
2-48
对于有向图，其邻接矩阵表示比邻接表表示更易于：(2分)
A.求一个顶点的入度
B.求一个顶点的出边邻接点
C.进行图的深度优先遍历
D.进行图的广度优先遍历
作者
DS课程组
单位
浙江大学
2-49
对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：(1分)
A.N−1
B.N
C.(N−1)2
D.N2
作者
DS课程组
单位
浙江大学
2-50
若一个有向图用邻接矩阵表示，则第i个结点的入度就是：(1分)
A.第i行的元素个数
B.第i行的非零元素个数
C.第i列的非零元素个数
D.第i列的零元素个数
作者
DS课程组
单位
浙江大学
2-51
下面关于图的存储的叙述中，哪一个是正确的？(1分)
A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
作者
DS课程组
单位
浙江大学
2-52
关于图的邻接矩阵，下列哪个结论是正确的？(1分)
A.有向图的邻接矩阵总是不对称的
B.有向图的邻接矩阵可以是对称的，也可以是不对称的
C.无向图的邻接矩阵总是不对称的
D.无向图的邻接矩阵可以是不对称的，也可以是对称的
作者
DS课程组
单位
浙江大学
2-53
设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为：(2分)
A.O(N)
B.O(N2)
C.O(N+E)
D.O(N×E)
作者
DS课程组
单位
浙江大学
2-54
在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？(2分)
A.1/2
B.1
C.2
D.4
作者
DS课程组
单位
浙江大学
2-55
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的多少倍？(2分)
A.1/2
B.1
C.2
D.4
作者
DS课程组
单位
浙江大学
2-56
在任一有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是：(1分)
A.相等
B.大于等于
C.小于等于
D.不确定
作者
DS课程组
单位
浙江大学
2-57
设无向图的顶点个数为N，则该图最多有多少条边？(1分)
A.N−1
B.N(N−1)/2
C.N(N+1)/2
D.N2
作者
DS课程组
单位
浙江大学
2-58
如果G是一个有36条边的非连通无向图，那么该图顶点个数最少为多少？(3分)
A.7
B.8
C.9
D.10
作者
陈越
单位
浙江大学
2-59
如果G是一个有21条边的非连通无向图，那么该图顶点个数最少为多少？(3分)
A.7
B.8
C.9
D.10
作者
陈越
单位
浙江大学
2-60
如果G是一个有15条边的非连通无向图，那么该图顶点个数最少为多少？(3分)
A.7
B.8
C.9
D.10
作者
陈越
单位
浙江大学
2-61
给定一个有向图的邻接表如下图，则该图有__个强连通分量。
(3分)
A.4 {{0, 1, 5}, {2}, {3}, {4}}
B.3 {{2}, {4}, {0, 1, 3, 5}}
C.1 {0, 1, 2, 3, 4, 5}
D.1 {0, 5, 1, 3}
作者
陈越
单位
浙江大学
2-62
给定有向图的邻接矩阵如下：
顶点2（编号从0开始）的出度和入度分别是：(1分)
A.3, 1
B.1, 3
C.0, 2
D.2, 0
作者
陈越
单位
浙江大学
2-63
已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：(4分)
A.10
B.11
C.13
D.15
作者
考研试卷
单位
浙江大学
2-64
设无向图为 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。则每个顶点的度依次为：(2分)
A.2, 1, 1, 1
B.1, 1, 2, 1
C.3, 2, 3, 2
D.2, 3, 2, 3
作者
魏宝刚
单位
浙江大学
2-65
对于给定的有向图如下，其邻接表为：
(2分)
A.
B.
C.
D.
作者
魏宝刚
单位
浙江大学
2-66
对于给定的有向图如下，其逆邻接表为：
(2分)
A.
B.
C.
D.
作者
魏宝刚
单位
浙江大学
2-67
给出如下图所示的具有 7 个结点的网 G，哪个选项对应其正确的邻接矩阵？
(2分)
A.
B.
C.
D.
作者
魏宝刚
单位
浙江大学
2-68
下列说法不正确的是：(2分)
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.遍历的基本算法有两种：深度遍历和广度遍历
C.图的深度遍历是一个递归过程
D.图的深度遍历不适用于有向图
作者
DS课程组
单位
浙江大学
2-69
图的深度优先遍历类似于二叉树的：(1分)
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
作者
DS课程组
单位
浙江大学
2-70
在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：(2分)
A.O(N)
B.O(N+E)
C.O(N2)
D.O(N2×E)
作者
DS课程组
单位
浙江大学
2-71
用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？(2分)
A.无序的
B.拓扑有序
C.逆拓扑有序
D.以上都不对
作者
DS课程组
单位
浙江大学
2-72
在图中自a点开始进行深度优先遍历算法可能得到的结果为：
(2分)
A.a, b, e, c, d, f
B.a, c, f, e, b, d
C.a, e, b, c, f, d
D.a, e, d, f, c, b
作者
DS课程组
单位
浙江大学
2-73
在图中自d点开始进行深度优先遍历算法可能得到的结果为：
(2分)
A.d,a,c,f,e,b
B.d,a,e,b,c,f
C.d,e,a,c,f,b
D.d,f,c,e,a,b
作者
DS课程组
单位
浙江大学
2-74
给定无向图G，从V0出发进行深度优先遍历访问的边集合为： {(V0,V1), (V0,V4), (V1,V2), (V1,V3), (V4,V5), (V5,V6)}。则下面哪条边不可能出现在G中？(3分)
A.(V0,V2)
B.(V0,V6)
C.(V1,V5)
D.(V4,V6)
作者
DS课程组
单位
浙江大学
2-75
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：
(2分)
A.V1,V2,V3,V5,V4
B.V1,V3,V4,V5,V2
C.V1,V4,V3,V5,V2
D.V1,V2,V4,V5,V3
作者
DS课程组
单位
浙江大学
2-76
已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：
（感谢湘潭大学朱江老师斧正）
(2分)
A.V1,V2,V3,V4,V5,V6
B.V1,V2,V4,V5,V6,V3
C.V1,V3,V5,V2,V4,V6
D.V1,V3,V5,V6,V2,V4
作者
DS课程组
单位
浙江大学
2-77
如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：(2分)
A.连通图
B.完全图
C.有回路的图
D.一棵树
作者
DS课程组
单位
浙江大学
2-78
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：
(2分)
A.V1,V5,V4,V7,V6,V2,V3
B.V1,V2,V3,V4,V7,V6,V5
C.V1,V5,V4,V7,V6,V3,V2
D.V1,V5,V6,V4,V7,V2,V3
作者
陈越
单位
浙江大学
2-79
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：
(2分)
A.V1,V5,V4,V7,V6,V2,V3
B.V1,V5,V4,V7,V6,V3,V2
C.V1,V2,V3,V4,V7,V6,V5
D.V1,V5,V6,V4,V7,V2,V3
作者
陈越
单位
浙江大学
2-80
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：
(2分)
A.V1,V2,V3,V4,V7,V6,V5
B.V1,V5,V4,V7,V6,V2,V3
C.V1,V5,V6,V4,V7,V2,V3
D.V1,V5,V4,V7,V6,V3,V2
作者
陈越
单位
浙江大学
