第7章图练习题与答案 联系客服

发布时间 : 星期五 文章第7章图练习题与答案更新完毕开始阅读a120a10f29ea81c758f5f61fb7360b4c2f3f2a2f

WORD格式可编辑

第七章图

一、单选题

(C)1.在一个图中,所有顶点的度数之和等于图的边数的倍。

A.1/2B.1C.2D.4

2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(B)

倍。

A.1/2B.1C.2D.4

(B)3.有8个结点的无向图最多有条边。

A.14B.28C.56D.112

(A)一个n个顶点的连通无向图,其边的个数至少为()。

A.n-1B.nC.n+1D.nlogn; (C)5.有8个结点的有向完全图有条边。

A.14B.28C.56D.112

(B)6.用邻接表表示图进行广度优先遍历时,通常是采用来实 现算法的。

A.栈B.队列C.树D.图

(A)7.用邻接表表示图进行深度优先遍历时,通常是采用来实 现算法的。

A.栈B.队列C.树D.图

8.下面关于求关键路径的说法不正确的是(C)。

A.求关键路径是以拓扑排序为基础的

B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相

C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与

该活动的持续时间的差

D.关键活动一定位于关键路径上

9.已知图的邻接矩阵如下,根据算法思想,则从顶点0出发,按深度优先遍历

0111101 1001001 1000100 1100110 1011010 0001101 1100010

的结点序列是(D)

A.0243156B.0135642C.0423165D.0

专业知识 整理分享

WORD格式可编辑

134256

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.0243165B.0135642C.0123465D.01 23456

3.已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结

点序列是(D)

A.0132B.0231 C.0321D.0123

(A)13.已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优 先遍历的结点序列是

A.0321B.0123 C.0132D.0312

(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条边的无向图的邻接矩阵中,零元素的个数为(D)

2

2

-eD.n-2eA.eB.2eC.n

19、下列关于无向连通图特性的叙述中,正确的是(A)

I.所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一 个顶点的度为1

A.只有IB.只有IIC.I和IID.I和III

专业知识 整理分享

WORD格式可编辑

20、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi

相关的所有弧的时间复杂度是(C) 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,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a ,e,d,f,c,b

22、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出 现的是(D)。

A.G中有弧B.G中有一条从Vi到Vj的路径 C.G中没有弧D.G中有一条从Vj到Vi的路

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

二、填空题

4.图有邻接矩阵、邻接表、十字链表、邻接多重表等存储结构,其中邻接矩

阵、邻接表既用于存储有向图,也用于存储无向图。 遍历图深度优先遍历、广度优先遍历等方法。

5.有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的出

度。

6.拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。 7.n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为O(n2),若采

用邻接表存储,则空间复杂度为O(n+e)。

8.n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为

O(n);若采用邻接表存储,该算法的时间复杂度为O(n+e)。

2

9.设有一稀疏图G,则G采用邻接表存储较省空间,设有一稠密图G,则G

专业知识 整理分享

WORD格式可编辑

采用邻接矩阵存储较省空间。

10.n个顶点的连通无向图,其边的条数至少为__n-1____。若用n表示图中顶

点数目,则有___n(n-1)/2____条边的无向图成为完全图。

11.具有8个顶点的有向完全图有56条弧。具有10个顶点的无向图,边的总

数最多为_45_。

12.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于1。 13.G是一个非连通无向图,共有28条边,则该图至少有_9_个顶点。

14.为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,

还需_队列存放被访问的结点以实现遍历。

15.一无向图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)}, 则采用的遍历方法是___广度优先遍历___

16.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说

等于该顶点的_度_;对于有向图来说等于该顶点的_出度_。

17.已知一无向图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,则该图必是连通图。(×)

10.有e条边的无向图,在邻接表中有e个结点。(×)

11.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。(×)

9.强连通图的各顶点间均可达。(√)

10.连通分量指的是有向图中的极大连通子图。(×)

11.任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。(×)

专业知识 整理分享