发布时间 : 星期一 文章第7章 图练习题及答案更新完毕开始阅读839f0d4abdeb19e8b8f67c1cfad6195f302be844
第七章 图
一、单选题
（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A．1/2 B. 1 C. 2 D. 4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。
A．14 B. 28 C. 56 D. 112 （ A ）一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn； （ C ）5. 有8个结点的有向完全图有 条边。
A．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 8. 下面关于求关键路径的说法不正确的是（ C ）。 A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历
?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??的结点序列是（ D ）
A． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0
1 3 4 2 5 6
10、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>，<4,2>}，则数据结构A是（ C ）。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合
（ C ）11. 已知图的邻接矩阵同上题9，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6
12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ D ）
A．0 1 3 2 B. 0 2 3 1
C. 0 3 2 1 D. 0 1 2 3
（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是
A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
（ A ）14. 深度优先遍历类似于二叉树的
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ D ）15. 广度优先遍历类似于二叉树的
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ D ）16、下面结构中最适于表示稀疏无向图的是。
A．邻接矩阵 B．逆邻接表 C．十字链表 D．邻接表 （ B ）17、下列哪一种图的邻接矩阵是对称矩阵？
A．有向图 B．无向图 C．AOV网 D．AOE网 18、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( Ｄ ) A．e B．2e C．n2－e D．n2－2e 19、下列关于无向连通图特性的叙述中，正确的是 （A）
I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1
A.只有I B. 只有II C.I和II D.I和III
20、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( Ｃ )
A．O(n) B．O(e) C．O(n+e) D．O(n*e) 21、无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
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
22、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。
A．G中有弧
径
23、下面哪一方法可以判断出一个有向图是否有环（回路）( B) A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 24、下列关于AOE网的叙述中，不正确的是（ B ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
25、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分
别为（ D ）。
(A) n，e (B) e，n (C) 2n，e
(D) n，2e
二、填空题
1. 图有 邻接矩阵 、邻接表 、十字链表、邻接多重表等存储结构，其中邻接矩阵 、邻接表既用于存储有向图，也用于存储无向图。 遍历图 深度优先遍历、 广度优先遍历 等方法。
2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。
3. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)，若采用邻接表存储，则空间复杂度为O(n+e)。
5. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为O(n+e)。
6. 设有一稀疏图G，则G采用 邻接表 存储较省空间，设有一稠密图G，则G
采用邻接矩阵存储较省空间。
7. n个顶点的连通无向图，其边的条数至少为__ n-1____。若用n表示图中顶点数目，则有___ n(n-1)/2____条边的无向图成为完全图。
8. 具有8个顶点的有向完全图有 56条弧。具有10个顶点的无向图，边的总数最多为_ 45_。
9. 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。 10. G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。 11. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列存放被访问的结点以实现遍历。
12. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是___广度优先遍历___
13. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_；对于有向图来说等于该顶点的_出度_。 14. 已知一无向图
G=（V，E），其中
V={a,b,c,d,e }
E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先遍历方法。
三、判断题
1、(? )在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。
2、(√ )用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
3、(× )拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 4（× ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。 5、(√ )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。
6．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ × ） 7. 有e条边的无向图，在邻接表中有e个结点。（ × ）
8. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ × ） 9．强连通图的各顶点间均可达。（ √ ）
10．连通分量指的是有向图中的极大连通子图。（ × ）
11．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（ × ）