第七章图试题
一、单项选择题
1.在无向图中定义顶点的度为与它相关联的（）的数目。
A. 顶点
B. 边
C. 权
D. 权值
2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。
A. 顶点序列
B. 边序列
C. 权值总和
D. 边的条数
3.图的简单路径是指（）不重复的路径。
A. 权值
B. 顶点
C. 边
D. 边与顶点均
4.设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. n(n-1)
5.n个顶点的连通图至少有（）条边。
A. n-1
B. n
C. n+1
D. 0
6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。
A. 3
B. 2
C. 1
D. 1/2
7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。
A. 上三角矩阵
B. 稀疏矩阵
C. 对角矩阵
D. 对称矩阵
8.图的深度优先搜索类似于树的（）次序遍历。
A. 先根
B. 中根
C. 后根
D. 层次
9.图的广度优先搜索类似于树的（）次序遍历。
A. 先根
B. 中根
C. 后根
D. 层次
10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，
判断一条边的两个端点是否在同一个连通分量上。
A. 位向量
B. 堆
C. 并查集
D. 生成树顶点集合
11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能
在图中构成（）。
A. 重边
B. 有向环
C. 回路
D. 权值重复的边
12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是
（）。
A. 非零
B. 非整
C. 非负
D. 非正
13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少
有（）子女。
A. 1
B. 2
C. 3
D. 0
14.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为
（）。
A. O(nlog2e)
B. O(n+e)
C. O(ne)
D. O(n2)
15.设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为
（）。
A. O(nlog2e)
B. O(n+e)
C. O(ne)
D. O(n2)
16.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（）。
A. G1是G2的子图
B. G2是G1的子图
C. G1是G2的连通分量
D. G2是G1的连通分量
17.有向图的一个顶点的度为该顶点的（）。
A. 入度
B. 出度
C. 入度与出度之和
D. (入度﹢出度))／2
18.一个连通图的生成树是包含图中所有顶点的一个（）子图。
A. 极小
B. 连通
C. 极小连通
D. 无环
19.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。
A. n-1
B. n n(n-1)/2 D. n(n-1)
20.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。
A. 某个最小
B. 任何最小
C. 广度优先
D.深度优先
21.对于具有e条边的无向图，它的邻接表中有（）个边结点。
A. e-1
B. e
C. 2(e-1)
D. 2e
22.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。
A.1, 4, 5
B. 1, 2, 3, 5
C. 1, 4, 3, 5
D. 1, 2, 4, 3, 5
23.具有n个顶点的有向无环图最多可包含（）条有向边。
A. n-1
B. n
C. n(n-1)/2
D.n(n-1)
24.一个有n个顶点和n条边的无向图一定是（）。
A. 连通的
B. 不连通的
C. 无环的
D. 有环的
25.在n个顶点的有向无环图的邻接矩阵中至少有（）个零元素。
A. n
B. n(n-1)/2
C. n(n+1)/2
D. n(n-1)
26.对于有向图，其邻接矩阵表示比邻接表表示更易于（）。
A. 求一个顶点的度
B. 求一个顶点的邻接点
C. 进行图的深度优先遍历
D. 进行图的广度优先遍历
27.在一个有向图的邻接矩阵表示中，删除一条边
A. O(1)
B. O(i)
C. O(j)
D. O(i+j)
28.与邻接矩阵相比，邻接表更适合于存储（）图。
A. 无向
B.连通
C.稀疏
D. 稠密图
29.设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是
（）。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n2)
30.为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（）。
A. 栈
B. 队列
C. 二叉树
D. 树
参考答案： 1. B 2. A 3. B 4. B 5. A
6. B
7. D
8. A
9. D 10. C
11.C 12. C 13. B 14. B 15. D
16. A 17. C 18. C 19. B 20. A
21. D 22. D 23. C 24. D 25. C
26. A 27. A 28. C 29. A 30. B
二、填空题
1.图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷________集合。
2.用邻接矩阵存储图，占用存储空间数与图中顶点个数________关，与边数________关。
3.n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。
4.n (n﹥0) 个顶点的连通无向图最少有________条边。
5.若3个顶点的图G的邻接矩阵为
?
?
?
?
?
?
?
?
?
?
1
1
1
，则图G一定是________向图。
6.n (n﹥0) 个顶点的连通无向图各顶点的度之和最少为________。
7.设图G = (V, E)，V = {V0, V1, V2, V3}, E = {(V0, V1), (V0, V2), (V0, V3), (V1,
V3)}，则从顶点V0开始的图G的不同深度优先序列有________种，例如______________。
8.设图G = (V, E)，V = {P, Q, R, S, T}, E = {
从顶点P出发，对图G进行广度优先搜索所得的所有序列为__________和___________。
9.n (n﹥0) 个顶点的无向图中顶点的度的最大值为________。
10.在重连通图中每个顶点的度至少为________。
11.在非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有
________个子女。
12.(n﹥0) 个顶点的连通无向图的生成树至少有________条边。
13.101个顶点的连通网络N有100条边，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各
10条，则网络N的最小生成树各边的权值之和为_________。
14.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个
________上，才有可能加入到生成树中。
15.深度优先生成树的高度比广度优先生成树的高度________。
16.求解带权连通图最小生成树的Prim算法适合于________图的情形，而Kruskal算法适合于
________图的情形。
17.求解最短路径的Dijkstra算法适用于各边上的权值________的情形。若设图的顶点数为n，则该
算法的时间复杂度为________。
18.若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则
在相应的邻接矩阵中所有________元素将集中到对角线以上。
参考答案： 1. 非空 2. 有, 无 3. n(n-1)/2, 0
4. n-1
5. 有
6. 2(n-1)
7. 4，V0V1V3V2（或V0V2V1V3, V0V2V3V1, V0V3V1V2）
8. PQRST和PRQTS 9. n-1 10. 2
11. 2 12. n-1 13. 550
14. 连通分量15. 高16. 稠密，稀疏
17. 非负，O(n2) 18. 非零（或值为1的）
三、判断题
1.一个图的子图可以是空图，顶点个数为0。
2.存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。
3.一个有1000个顶点和1000条边的有向图的邻接矩阵是一个稀疏矩阵。
4.对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。
5.有n (n≥1) 个顶点的无向连通图最少有n-1条边。
6.有n (n≥1) 个顶点的有向强连通图最少有n条边。
7.图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。
8.如果无向图中各个顶点的度都大于2，则该图中必有回路。
9.如果有向图中各个顶点的度都大于2，则该图中必有回路。
10.图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求
解。
11.图的广度优先搜索（breadth first search）算法不是递归算法。
12.有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。
13.对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路
径。
14.对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小
排列到一个拓扑有序的序列中。
15.有回路的有向图不能完成拓扑排序。
16.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
17.用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。
18.对于AOE网络，加速任一关键活动就能使整个工程提前完成。
19.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。
20.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样
的桥上的关键活动就能使整个工程提前完成。
21.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数
有关，而与图的边数无关。
22.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
23.邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平
方）
24.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。
25. 连通分量是无向图中的极小连通子图。
26. 强连通分量是有向图中的极大强连通子图。
27. 在AOE 网络中一定只有一条关键路径。
参考答案： 1. 否
2. 否
3. 是
4. 是
5. 是
6. 否
7. 是
8. 是
9. 否 10. 是 11. 是 12. 否 13. 否 14. 否 15. 是 16. 否 17. 是 18. 否 19. 是 20. 是 21. 是 22. 否 23. 是 24. 是
25. 否
26. 是
27. 否
四、运算题
1. 设连通图G 如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先
搜索的结果。
2. 设连通图G 如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜
索的结果。
3. 设连通图G 如图所示。试画出从顶点V0出发的深度优先生成树，指出图G 中哪几个顶点是关节点（即
万一它失效则通信网络将发生故障）。
4. 设连通图G 如图所示，
(1) 如果有关节点，请找出所有的关节点。 (2) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？
V 4 6
V 4 6
V 4
6⑩ ① ② ③ ④ ⑤ ⑥ ⑦
⑧
⑨
Y I 1
n 0k kj
ik ij b a c -==Y
5. 对于如图所示的有向图，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树
6. 设有向图G 如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS 生成森林
和BFS 生成森林。
7. 表示图的另一种方法是使用关联矩阵INC[ ][ ]。其中，一行对应于一个顶点，一列对应于一条边。
因此，如果边j 依附于顶点i ，则INC[i][j]=1。如果ADJ 是图G =（V, E ）的邻接矩阵，INC 是关联矩阵，试说明在什么条件下将有ADJ = INC ?INCT -I ，其中，INCT 是矩阵INC 的转置矩阵，I 是单位矩阵。两个n ?n 的矩阵的乘积C = A ?B 定义为
公式中的 定义为按位加，
定义为按位乘。 设无向图G 如图所示。试画出该图的邻接矩阵和关联矩阵。
8. 设有一个连通网络如图所示。试按如下格式，应用Kruskal 算法给出在构造最小生成树过程中顺序选出的各条边。
I 1 V 7
65①
② ③ ④ ⑤
第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。
数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：
第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。
A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量
1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧
关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）
数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧
(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径
习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n
11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。
习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。