数据结构练习 第七章 图.doc

数据结构练习 第七章 图
一、选择题

1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
2. 设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。
A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1
3．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。
A. n-1 B. n C. n+1 D. 2n-1
4．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。
A. n，e B e，n C 2n，e D n，2e
5．设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。
A. n(n-1) B. n+1 C. n D. n(n+1)
6．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。
A .n B. e C. 2n D. 2e
7．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。
A. n B. n-1 C. m D. m-1
8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。
A. abedfc B. acfebd C. aebdfc D. aedfcb
9．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。
A. O(n+e) B. O(n2) C. O(ne) D. O(n3)
10．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。
A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和
C. 第i行0元素的个数之和 D. 第i列0元素的个数之和
11．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。
A. 2n B. n C. n/2 D. n(n-1)
12．设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。
A. n B. n-1 C. 2n D. 2n-1
13．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2
C．n(n+1)/2 C．0
14．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。
A. 1，2，3，4 B. 2，3，4，1 C. 1，4，2，3 D. 1，2，4，3
15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A．n B．2n C．n-1 D．n+1
16．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A．2 B．1 C．3 D．4
17．在用邻接表表示图时, 对图进行深度优先搜索遍历的算法的时间复杂度为______。
A. Ｏ(n) B. Ｏ(n+e) C. Ｏ(n2)　 D. Ｏ(n3)
(b) 在用邻接表存储图时，故整个算法的时间复杂度为O(n+e)。如果用邻接矩阵表示图，则算法的时间复杂度就是O(n2)。
18．一个具有n个顶点的无向连通图，它所包含的连通分量数为（　　　）
A.0 B.1 C.n D.不确定
19．下列说法中不正确的是（　　　）
A.无向图的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索算法
20．邻接矩阵为对称矩阵的图是( )
A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图
21．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )
A.n-1 B.n C.n+1 D.
22．有4个顶点的无向完全图的边数为( )
A.6 B.12 C.16 D.20
23．设图的邻接矩阵为，则该图为( )
A.有向图 B.无向图 C.强连通图 D.完全图
24．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ）
A．n B.n-1 C.n+1 D.2(n-1)
25．关于无向图的邻接矩阵的说法中正确的是（ ）
A．矩阵中非全零元素的行数等于图中的顶点数
B.第i行上与第i列上非零元素总和等于顶点Vi的度数
C.矩阵中的非零元素个数等于图的边数
D.第i行上非零元素个数和第i列上非零元素个数一定相等
26．有n个结点的有向完全图的弧数是（　　）
A.n2 B.2n C.n(n-1) D.2n(n+1)
27．设图的邻接链表如题12图所示，则该图的边的数目是（　）

题12图
A.4 B.5 C.10 D.20
28．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（　　）
A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历
29．具有n个顶点的无向图，若要连通全部顶点，至少需要（　　）
A.（n-1）条边 B. n条边 C. n(n-1)条边 D. n(n-1)/2条边
30．一个带权的无向连通图的最小生成树（　　　）
A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在
31．下列有关图遍历的说法中不正确的是（　　）
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
32．设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。
A．O（nlog2e） B．O（n+e） C．O(ne) D．O(n2)
33．在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
A．3 B．2 C．1 D．1/2
34．图中有关路径的定义是（ A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
35．要连通具有n个顶点的有向图，至少需要（B）条边。
A．n-l B．n C．n+l D．2n
36．一个有n个结点的图，最少有（B ）个连通分量，最多有（ D ）个连通分量。
A．0 B．1 C．n-1 D．n
37．在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C ）倍。
A．1/2 B．2 C．1 D．4
38．用邻接表存储图所用的空间大小（A）。
A.与图的顶点数和边数都有关 B.只与图的边数有关
C.只与图的顶点数有关 D.与边数的平方有关
39．图的BFS生成树的树高比DFS生成树的树高（ A ）
A.小或相等 B.小 C.大或相等 D.大
40．下列说法不正确的是（C ）。
A．图的遍历是从给定的源点出发每个顶点仅被访问一次
B．遍历的基本方法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
41．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ 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
42．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3)
43．在有向图的邻接表存储结构中，顶点v在链表中出现的次数是(B )。
A.顶点v的度 B. 顶点v的出度 C. 顶点v的入度 D. 依附于顶点v的边数
44．(1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示）
(3). Floyed求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
上面不正确的是（ C ）。
A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)
45．当各边上的权值(A )时，BFS算法可用来解决单源最短路径问题。
A．均相等 B．均互不相等 C．不一定相等
46．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。
A．G中有弧<Vi，Vj> B．G中有一条从Vi到Vj的路径
C．G中没有弧<Vi,Vj> D．G中有一条从Vj到Vi的路径
47．关键路径是AOE网中( B )
A.从始点到终点的最短路径 B.从始点到终点的最长路径
C.从始点到终点的边数最多的路径 D.从始点到终点的边数最少的路径
48．下列关于AOE网的叙述中，不正确的是（ B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动若提前完成，那么整个工程将会提前完成
49．下列有关图的说法错误的是（C ）
A．在有向图中，出度为0的结点称为叶子。
B．用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。
C．按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。
D．若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列。
50．n个顶点的无向图的邻接表最多有( B )个表结点。
A． n2 B．n(n-1) C． n(n+1) D． n(n-1)/2
51．设无向图的顶点个数n，则该无向图最多有（B ）条边
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0
52．采用邻接表存储的图，其DFS类似于二叉树的（ B ）
A．中序遍历 B．先序遍历 C．后序遍历 D．按层次遍历
53．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A )。
A．逆拓扑有序 B．拓扑有序 C．无序的
54．要连通具有n个顶点的有向图，至少需要（B ）条边。
A．n-l B．n C．n+l D．2n
55. 下列说法不正确的是（ C ）。
A．图的遍历是从给定的源点出发每个顶点仅被访问一次
B．遍历的基本方法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
56. 图的BFS生成树的树高比DFS生成树的树高（ A ）
A.小或相等 B.小 C.大或相等 D.大
57. 设无向图的顶点个数为n，则该图最多有（B ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0
58. 在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s ，则所有顶点的入度数之和为 (    A   ) 。
 A. s       B.s-1       C. s+1       D. n
59. 在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s ，则所有顶点的度数之和为 (    D   ) 。
 A. s       B. s-1       C. s+1       D.2s
60. 在一个具有 n 个顶点的无向图中，若具有 e 条边，则所有顶点的度数之和为 (    D   ) 。
 A.n      B. e       C. n+e         D.2e
61. 在一个具有 n 个顶点的无向完全图中，则所含的边数为 (C      ) 。
 A.n       B. n(n-1)       C.n(n-1)/2       D.n(n+1)/2
62. 在一个具有 n 个顶点的有向完全图中，则所含的边数为 (    B   ) 。
 A.n       B.n(n-1)       C. n(n-1)/2       D.n(n+1)/2
63. 在一个无权图中，若两顶点之间的路径长度为 k ，则该路径上的顶点数为 (      B ) 。
  A.k       B.k+1       C.k+2       D.2k
64. 对于一个具有 n 个顶点的无向连通图，它包含的连通分量的个数为 (    B   ) 。
 A. 0        B.1       C.n       D.n+1
65. 若一个图中包含有 k 个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用 (  A      ) 次深度优先搜索遍历的算法。
  A. k       B. 1         C.k-1        D.k+1
66. 若要把 n 个顶点连接为一个连通图，则至少需要 (      C ) 条边。
 A. n       B. n+1        C. n-1        D. 2n
67. 在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为 (     D  ) 。
 A. n       B .n* e       C.e       D. 2 *e
68. 在一个具有 n 个顶点和 e 条边的有向图的邻接矩阵中，表示边存在的元素个数为 (    C   ) 。
  A. n        B. n* e       C. e       D.2 * e
69. 在一个具有 n 个顶点和 e 条边的无向图的邻接表中，边结点的个数为 (     D  ) 。
 A.n       B. n* e       C. e       D.2*e
70. 在一个具有 n 个顶点和 e 条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为 (  A     ) 。
 A.n        B.2n       C. e       D. 2e
71. 在一个无权图的邻接表表示中，每个边结点至少包含 (     B  ) 域。
 A.1       B. 2       C. 3       D. 4
72. 对于一个有向图，若一个顶点的度为 k1 ，出度为 k2 ，则对应邻接表中该顶点单链表中的边结点数为 (      B ) 。
 A. k1       B. k2       C. k1-k2        D. k1+k2
73. 对于一个有向图，若一个顶点的度为 k1 ，出度为 k2 ，则对应逆邻接表中该顶点单链表中的边结点数为 (C      ) 。
 A.k1       B. k2       C. k1-k2        D.k1+k2
74. 对于一个无向图，下面 (A      ) 种说法是正确的。
 A． 每个顶点的入度等于出度         B． 每个顶点的度等于其入度与出度之和
 C． 每个顶点的入度为 0             D． 每个顶点的出度为 0
75. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的 (      A ) 。
 A. 出边数        B. 入边数       C. 度数       D. 度数减 1
76. 若一个图的边集为 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，则从顶点 A 开始对该图进行深度优先搜索，得到的顶点序列可能为 (      B ) 。
  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
77. 若一个图的边集为 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，则从顶点 A 开始对该图进行广度优先搜索，得到的顶点序列可能为 (  D     ) 。
 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
78. 若一个图的边集为 {<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>} ，则从顶点 1 开始对该图进行深度优先搜索，得到的顶点序列可能为 (   A    ) 。
  A. 1,2,5,4,3            B. 1,2,3,4,5   C .1,2,5,3,4            D.1,4,3,2,5
79. 若一个图的边集为 {<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>} ，则从顶点 1 开始对该图进行深度优先搜索，得到的顶点序列可能为 (   C    ) 。
  A. 1,2,3,4,5            B. 1,2,4,3,5         C. 1,2,4,5,3            D. 1,4,2,5,3
80. 由一个具有 n 个顶点的连通图生成的最小生成树中，具有 (    B   ) 条边。
 A. n          B. n-1       C. n+1       D. 2n
81. 已知一个无向图的边集为 {(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8} ，则该图的最小生成树的权为 (     C  ) 。
A.43       B. 16        C． 18        D． 23
82. 已知一个无向图的边集为 {(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8} ，则该图的最小生成树的边集为 (  D     ) 。
 A.{(0,1)3,(0,2)5,(0,3)6,(3,4)8}     B.{(0,1)3,(0,2)5,(0,3)6,(2,3)2}
 C. {(2,3)2,(0,2)5,(3,4)8,(0,3)6}     D. {(2,3)2,(0,2)5,(3,4)8,(0,1)3}
83. 已知一个有向图的边集为 {<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>} ，则由该图产生的一种可能的拓扑序列为 (      A ) 。
 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．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。e， 2e
2．AOV网是一种___________________的图。有向无回路
3．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。n(n-1)/2 n(n-1)
4. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。d/2
5．已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是 ，BFS遍历的输出序列是 。(1，3，4，5，2)，(1，3，2，4，5)

6．设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。出度，入度
7．设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。e=d
8．设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。(1，4，3，2)
9．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。A[i][j]=1
10．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。等于
11．在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。可以随机访问到任一个顶点的简单链表
12．设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。O(n2)， O(n+e)
13．设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为_________________________。124653
14．设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_________________。8

15．设有向图中不存在有向边<Vi,Vj>，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。0
16．设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。n-1
17．设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。n(n-1)，n(n-1)/2
18．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。(1，3，2，4，5)
19．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。n-1
20．表示图的三种存储结构为 、 和 。邻接距阵、邻接表、边集数组
21．对用邻接距阵表示的具有n个顶点和e条边的图形进行任一种遍历时，其时间复杂度为__________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为______________。O(n2) ， O(e)
22．在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于___0_____。
23．对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为____O(n2)____。
24．一个具有4个顶点的无向完全图有_______6_____条边。
25．一个有向图G中若有孤<Vi，Vj>、<Vj，Vk>和<Vi，Vk>，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为__Vi VjVk__________。
26．具有n个顶点的连通图至少需有______n-1____条边。
27．在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__1________。
28．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为__简单回路_____。
29．一个具有10个顶点的完全无向图中有___45____条边。
30．有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的____入度____。
31．一个具有n个顶点的有向完全图的弧数为____n(n-1)___。
32．在一个图中，所有顶点的度数之和等于所有边数的________倍。2
33．表示图的三种存储结构为________、________和________。邻接矩阵、邻接表、逆邻接表
34．在一个图中，所有顶点的度数之和等于所有边数的________倍。2
35．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。n(n-1)/2、n(n-1)
36．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。n-1
37．对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为________。n*n ( 或 n行n列 )
38．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为________和________条。e、2e
39．在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。出边、入边
40．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为________和________条。e、e
41．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为________、________和________。O(n)、O(e/n)、O(e)
42．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为________、________和________。O(n2)、O(n)+O(e)、O(e)+O(n)
43．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为________。O（n2）、O（e）
44．对于下面的无向图G1，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为____________，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为____________。014253、012345
45．对于下面的有向图G2，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为____________，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为____________。ABCDE、ABCED
46．对于下面的带权图G3，其最小生成树的权为________。22
47．对于下面的带权图G3，若从顶点v0出发，则按照普里姆算法生成的最小生成树中，依次得到的各条边为_______________。(0,1)5，(1,3)3，(3,2)6，(1,4)8
48．对于下面的带权图G3，若按照克鲁斯卡尔算法产生最小生成树，则得到的各条边依次为_______________。(1,3)3，(0,1)5，(3,2)6，(1,4)8

49．假定用一维数组d[n]存储一个AOV网中用于拓扑排序的顶点入度，则值为0的元素被链接成为一个________。链栈
50．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。n、n-1
51．在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是____________；二是_________；三是___________。边结点、邻接点域、权域、链域；
52. 在一个无向图的的邻接表中，若表结点的个数是m，则图中边的条数
是 条。m/2
53. 若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有 棵树。n-e
54. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。n
55. 如果具有n个顶点的图是一个环，则它有 棵生成树。n
56. 构造n个结点的强连通图，至少有______条弧。n
57. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的顶点总数为______。n n (邻接表边结点个数为2e)
58. 在n个顶点的非空无向图中，最多有 个连通分量。n
59. 求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。克鲁斯卡尔
60. n个顶点的无向连通图用邻接矩阵表示时，该矩阵至少有 个非零元素。2(n-1)
61. 在拓扑分类中，拓扑序列的最后一个顶点必定是 的顶点。出度为0
62. AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。(1）活动 （2）活动间的优先关系（3）事件（4）活动 边上的权代表活动持续时间
63. 如果一个有向图中没有 ，则该图的全部顶点可能排成一个拓扑序列。环（或回路）
64. 在一个图中，所有顶点的度数之和等于所有边数的 ________ 倍。2
65. 在一个具有 n 个顶点的无向完全图中，包含有 ________ 条边，在一个具有 n 个顶点的有向完全图中，包含有 ________ 条边。n(n-1)/2   n(n-1)
66. 已知一个连通图的边集为 {(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2} ，则度为 3 的顶点个数有 ________ 个。4
67. 假定一个有向图的顶点集为 {a,b,c,d,e,f} ，边集为 {<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>} ，则出度为 0 的顶点个数为 ________ ，入度为 1 的顶点个数为 ________ 。2   4
68. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要 ________ 条边。n-1
69. 表示图的两种存储结构为 __________ 和 __________ 。邻接矩阵   邻接表
70．在一个连通图中存在着 ________ 个连通分量。1
71. 图中的一条路径长度为 k ，该路径所含的顶点数为 ________ 。k+1
72. 若一个图的顶点集为 {a,b,c,d,e,f} ，边集为 {(a,b),(a,c),(b,c),(d,e)} ，则该图含有 ________ 个连通分量。3
73. 一个图的边集为 {<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6>} ，则从顶点 V 0 到顶点 V 4 共有 ________ 条简单路径。4
74. 一个图的边集为 {<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,