习题6
一、单项选择题
1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( )。
A. s B. s-1 C. s+1 D. n
2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( )。
A. s B. s-1 C. s+1 D. 2s
3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。
A. n B. e C. n+e D. 2e
4. 在一个具有n个顶点的无向完全图中，所含的边数为( )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
5. 在一个具有n个顶点的有向完全图中，所含的边数为( )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。
A. k B. k+1 C. k+2 D. 2k
7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。
A. 0 B. 1 C. n D. n+1
8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。
A. k B. 1 C. k-1 D. k+1
9. 若要把n个顶点连接为一个连通图，则至少需要( )条边。
A. n B. n+1 C. n-1 D. 2n
10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。
A. n B. n?e C. e D. 2?e
11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。
A. n B. n?e C. e D. 2?e
12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。
A. n B. n?e C. e D. 2?e
13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为( )。
A. n B. 2n C. e D. 2e
14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。
A. 1 B. 2 C. 3 D. 4
15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为( )。
A. k1 B. k2 C. k1-k2 D. k1+k2
16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为( )。
A. k1 B. k2 C. k1-k2 D. k1+k2
17. 对于一个无向图，下面( )种说法是正确的。
A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和 C. 每个顶点的入度为0 D. 每个顶点的出度为0
18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。
A. 出边数 B. 入边数 C. 度数 D. 度数减1
19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( )。
A. A,B,C,F,D,E B. A,C,F,D,E,B C. A,B,D,C,F,E D. A,B,D,F,E,C
20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为( )。
A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,C,B,F,D,E
21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为( )。
A. 1,2,5,4,3 B. 1,2,3,4,5 C. 1,2,5,3,4 D. 1,4,3,2,5
22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为( )。
A. 1,2,3,4,5 B. 1,2,4,3,5 C. 1,2,4,5,3 D. 1,4,2,5,3
23. 由一个具有n个顶点的连通图生成的最小生成树中，具有( )条边。
A. n B. n-1 C. n+1 D. 2?n
24. 已知一个有向图的边集为{
A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 二、填空题
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 5. 表示图的两种存储结构为__________和__________。 6. 在一个连通图中存在着________个连通分量。
7. 图中的一条路径长度为k，该路径所含的顶点数为________。
8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。
9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________?________。
10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。
11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。
12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。
13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。
14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。
15. 一个图的边集为{
16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。
17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。
18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。
19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。
20. 假定一个有向图的边集为{
1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。
2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边
结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。 0 0 1 2 1 4 6 5 3 4 5 7 9
8
6 2 3 7 8 (a) (b)
图6-11
3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。
4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 (a) (b)
图6-12
5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。
6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。
60 V1 V3 50 45 52
42 65 V4 V7 V2
50 30 40 V5 V6
70 图6-13
7. 图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。
V5 100 60 30 V0 V4 ∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞ 10 20 10 ∞ ∞ ∞ 50 ∞ ∞ V1 ∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60 5 V3 50 ∞ ∞ ∞ ∞ ∞ ∞ V2
四、算法设计题
1. 编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degree1(Graph & ga, int numb)
2. 编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。 int degree2(Graph & ga, int numb)
3. 编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。 int degree3(GraphL & gl, int numb)
4. 编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。 int degree4(GraphL & gl, int numb)
(a) 有向带权图
(b) 带权邻接矩阵 图6-14 有向带权图及其邻接矩阵
8. 图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。
v4 a3=2 a7=6 v2 a1=3 a4=1 v7 a8=8 a11=7 v1 a2=4 v5 a5=3 a9=4 v3 a6=5 a13=10 v8 a12=4 v1001 a14=1v11 a15=6 v6 a10=2 v9 图6-15
相关推荐：
loading