第七章测试1.
在无向图中定义顶点的度为与它相关联的（ ）的数目。
A:权值 B:顶点 C:边 D:权
答案:C
2.
具有 n 个顶点且每一对不同的顶点之间都有一条边的无向图被称为（ ）。
A:无向强连通图 B:无向树图 C:无向连通图 D:无向完全图 3.
一个有 n 个顶点的无向图最多有（ ）边。
A:n B:n(n-1)/2
C:2n
D:n(n-1) 4.
具有 6 个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
A:6
B:5
C:8
D:7
5.
图的简单路径是指（ ）不重复的路径。
A:顶点
B:边
C:权值 D:边与顶点均
6.
在一个具有 n 个顶点的有向图中，若所有顶点的出度之和为 s，则所有顶点的入度之和为（ ）。
A:s
B:n
C:s+1
D:s-1
7.
在下列有关图的说法中正确的是（ ）。
A:在图结构中，顶点可以没有任何前驱和后继 B:在无向图中，边的条数是结点度数之和 C:在有向图中，各顶点的入度之和等于各顶点的出度之和 D:具有 n 个顶点的无向图最多有 n(n-1)条边，最少有 n-1 条边 8.
对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接矩阵表示，则该矩阵中的非零元素个数是（ ）。
A:e B:e^2 C:2e D:n^2
9.
无向图的邻接矩阵是一个（ ）。
A:零矩阵 B:对角矩阵 C:上三角矩阵 D:对称矩阵 10.
有 n 个顶点和 e 条边的无向图采用邻接矩阵存储，零元素的个数为（ ）。
A:n^2-2e
B:2e C:e D:n^2-e 11.
从邻接矩阵
可知，该有向图共有（ ）条有向边。
A:4
B:3
C:2
D:9 12.
带权有向图G用邻接矩阵 A 存储，则顶点 i 的入度等于A中（ ）。
A:第i列非∞且非0的元素个数 B:第 i 行非∞的元素之和 C:第 i 列非∞的元素之和 D:第i行非∞且非0的元素个数 13.
下列说法中正确的是（ ）。
A:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 B:一个图的邻接矩阵表示不唯一，邻接表表示也不唯一 C:一个图的邻接矩阵表示不唯一，邻接表表示唯一 D:一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 14.
用邻接表存储图所用的空间大小（ ）。
A:只与图的顶点数有关 B:只与图的边数有关系 C:与边数的平方有关 D:与图的顶点数和边数都有关 15.
在下列有关图的存储结构的说法中错误的是（ ）。
A:对同一个有向图来说，邻接表中边结点数与逆邻接表中边结点数相等 B:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用 C:用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关 D:邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方） 16.
设图有n个顶点和e条边，采用邻接矩阵时，遍历图时的顶点所需时间为（）。
A:O(ne) B:O(e) C:O(n^2)
D:O(n)
17.
设图有n个顶点和e条边，采用邻接表时，遍历图的顶点所需时间为（）。
A:O(n+e) B:O(e) C:O(n^2)
D:O(ne) 18.
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A:—棵树 B:有回路 C:连通图 D:强连通图 19.
如果一个连通网络 G 中各边权值互不相同， 权值最小的边一定包含在 G 的( )生成树中。
A:广度优先 B:最小 C:深度优先 D:任何 20.
任何一个连通图的最小生成树（ ）。
A:有一棵或多棵 B:可能不存在 C:一定有多棵 D:只有一棵 21.
Dijkstra 算法是（ ）来求出图中从某顶点到其余顶点最短路径的。
A:按长度递减的顺序求出图的某项点到其余顶点的最短路径 B:按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C:通过深度优先遍历求出图的某顶点到其余顶点的所有路径 D:通过广度优先遍历求出图的某顶点到其余顶点的最短路径 22.
已知一个带权有向图如图所示，依据Dijkstra算法求从顶点1到其余各顶点的最短路径的顺序应是（ ）。
A:5 4 6 3 2
B:2 5 4 6 3 C:2 5 3 4 6
D:2 3 5 4 6
23.
如果一个有向图具有拓扑有序序列，并且顶点按拓扑有序序列编号， 那么它的邻接矩阵必定为（ ）。
A:三对角矩阵 B:上三角矩阵 C:下三角矩阵 D:对称矩阵 24.
若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该有向图是一个（ ） 。
A:含有顶点数大于 1 的强连通分量 B:含有多个入度为 0 的顶点的图 C:强连通图 D:DAG图 25.
在如图所示的 AOE 网中， 关键路径长度为（ ）。
A:13 B:23 C:16 D:22
