第七章 图
一．选择题
1．n个顶点，e条边的有向图的邻接矩阵中非零元素有      个。
A.n            B.2e            C.e             D.n+e
2．用邻接表存储图所用的空间大小（）
A．与图的顶点数和边数都有关
B．只与图的边数有关
C．只与图的顶点数有关
D．与边数的平方有关
3．有 n 条边的无向图的邻接表存储法中，链边中结点的个数是（ ）个。
A．n    　　　B．2n    　　　　C．n/2  　  　　D．n*n
4．一个带权无向连通图的最小生成树（ ）。
A．有一棵或多棵 .    B．只有一棵    C．一定有多棵    D．可能不存在
5．若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(      )次深度优先搜索遍历的算法。
A．k              B．1            C．k-1          D．k+1
二．如下所示有向图：
1．请给出每个顶点的度，入度和出度。
2．请画出其邻接矩阵、邻接表、逆邻接表、十字链表。
 
三．试对下图所示的AOE网络，解答下列问题。
1．求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]。
2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。
3．指出哪些活动加速可使整个工程提前完成。
 
四．写出下图所示的AOV网的所有拓扑有序序列。
 


参 考 答 案
第七章 图
一．选择题
1． C
2． A
3． B
4． A
5． A
二．如下所示有向图：
1．                                                         
    度    入度    出度
A    3    1    2
B    2    1    1
C    3    2    1
D    2    1    1






2．
邻接矩阵                                       
邻接表                       
  逆邻接表
  十字链表（略）
三．
1．                                                        
事件    A    B    C    D    E    F
ve(i)    0    3    2    6    6    8
vl(i)    0    4    2    6    7    8
2．                                                         
活动    a1    a2    a3    a4    a5    a6    a7    a8
ee(i)    0    0    3    3    2    2    6    6
el(i)    1    0    4    4    2    5    6    7
el(i)-ee(i)    1    0    1    1    0    3    0    1
3．a2，a5，a7  
四．
ABCDEF
ABCEDF
ACBDEF
ACBEDF
ACEBDF