数据结构基础练习
判断题：
1. 在 n 个结点的无向图中，若边数 > n-1，则该图必是连通图。（ ）
答：FALSE(该图可能包含多个连通子图，但其本身可以是不连通的。因为图的定义是：如果
对于图中任意两个顶点 v 、v ∈E，v 和 v 都是连通的，则称 G 是连通图(Connected
Graph)。)
2.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。（ ）
答：FALSE(邻接表也可存储无向图)
3.图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。( )
答：TRUE
4.有回路的图不能进行拓扑排序。( )
答：TRUE
5.任何 AOV 网拓扑排序的结果都是唯一的。( )
答：FALSE(拓扑排序不一定唯一，只要满足偏序关系即可。)
6.在 AOV-网中，如果得到的拓扑有序序列中顶点个数小于网中顶点数 n，则说明网中存在环，
不能求关键路径。( )
答：TRUE
7.图的邻接矩阵中矩阵元素的行数只与顶点个数有关（ TRUE ）
8.图的邻接矩阵中矩阵中非零元素个数与边数有关（TRUE ）
9.在拓扑排序序列中，任意两个相继结点 V i 和 Vj 都存在从 V i 到 Vj 的路径（FALSE ）
10.若一个图的邻接矩阵为对称矩阵，则该图必为无向图。（TRUE ）
11.任一 AOE 网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条（ TRUE ）
12.在有向图中，入度为 0 的结点称为叶子结点（或叶子）（ FALSE ）
单选题：
13.在一个图中，所有顶点的度数之和等于所有边数的( ① )倍，在一个有向图中，所有顶点
的入度之和等于所有顶点出度之和的( ② )倍。
A. 1/2 B. 2 C. 1 D. 4
答：① B ② C
14.具有 n 个顶点的有向图最多有( )条边。
A．n B. n(n-1) C. n(n+1) D.
答：B
15.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要( )条边。
A. n B. n+1 C. n-1 D. n/2
答：C
16.一个有 n 个顶点的无向连通图，它所包含的连通分量个数为( )。
A．0 B. 1 C. n D. n+1
答：B
17. n 个顶点的强连通图至少有( )条边。
A. n B. n-1 C. n+1 D. n(n-1)
答：A
18. 在一个具有 n 个顶点的有向图中，若所有顶点的出度之和为 s，则所有顶点的入度之和
为( )。
A．s B. s-1 C. s+1 D. n
答：A
19. 对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为
资源评论
