第六章的练习题
一、选择题
1．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn； 3．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n 4．n个结点的完全有向图含有边的数目（ ）。
A．n*n B．n（n＋１） C．n／2 D．n*（n－l） 5．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A．0 B．1 C．n-1 D．n
6．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4
7．一个图中包含K个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先搜索遍历算法。
A．1 B．K-1 C．K D．K+1 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网
9． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；如果是无向图，则共有（③）条边。
①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 10．对某个无向图的邻接矩阵来讲，（ ）。
A．第i行上的非零元素个数和第i列的非零元素的个数一定相等 B．矩阵中的非零元素个数等于图中的边数
C．第i行上，第i列上非零元素总数等于顶点vi的度数 D．矩阵中非全零行的行数等于图中的顶点数
11．无向图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 12. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
?0A???1??01010?1??0??
A．5个 B．4个 C．3个 D．2个
第12题图 第13题图
abdefc13.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。
①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 14．下面哪一方法可以判断出一个有向图是否有环（回路）： A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 15.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 16．一个有向无环图的拓扑排序序列（ ）是唯一的。 A．一定 B．不一定
17. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧
二、填空题
1. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______ 2．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
3. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 4．在有n个顶点的有向图中，每个顶点的度最大可达______。 5．N个顶点的连通图的生成树含有______条边。
6．有N个顶点的有向图，至少需要量______条弧才能保证是连通的。 7．右图中的强连通分量的个数为______个。
8．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
9．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。
10. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
11. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
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. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。
14．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。
15.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。
16．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
17．在 AOV网 中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。 18. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈；
（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；
（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。
三、应用题
1． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出从面点1开始的深度，广度优先遍历的结果。
5 2 1 6 7 9 3 4 8
2．下面的邻接表表示一个给定的无向图
（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。
3．设G=(V,E)以邻接表存储，如图所示，试画出从顶点1出发的图的深度优先和广度优先生成树。
12345234?44?35?11123224?5?4．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
1 20 11 9 6 14 6 10 10 4 5 18
2 5 6 3
第4题 第五题
5．请看无向加权图。 （1）写出它的邻接矩阵；
（2）按Prim算法求从顶点1出发的最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。 辅助数组内各分量值：
Y Closedge Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost 2 3 4 5 6 7 8 U V-U
Adjvex Lowcost Adjvex Lowcost Adjvex Lowcost
6．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)
PE N PA L T M
PE 109 82 81 21 124 N PA L T M
109 82 81 21 124 58 55 108 32 58 3 97 92 55 3 95 89 108 97 95 113 32 92 89 113 （1）画出这六大城市的交通网络图; （2）画出该图的邻接表表示法;
（3）画出该图按权值递增的顺序来构造的最小(代价)生成树.
7．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：由顶点V1到顶点V3的最短路径。
(顶点边)（出边表）233336?429625?
1
V12V2V3? 3 4V4230338542? 110618?5V5
6V6?
8．已知图的邻接矩阵为：
V1 V2 V3 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
V4 V5 V6 V7 V8 V9
0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 0 0 0 0 0
0 0 1 0 0 0 0
1 0 1 1 0 0 0
0 0 0 0 1 1 0
V10 0
当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历； （2）以顶点V1为出发点的唯一的广度优先遍历； （3）该图唯一的拓扑有序序列。
四、算法题
1．编写图的创建算法（邻接矩阵和邻接表，分无向、有向和带权图）。 2．读懂图的遍历算法。
搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新幼儿教育练习题（第6章） 全文阅读和word下载服务。
相关推荐：
夏の樱