2、扑排序向前递推到ve(6),最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0);（3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立e(i)=ve(j)l(i)=vl(k)-dut()（4）找出e(i)-l(i)=0的活动既是关键活动。【答案】关键路径为：a0->a4->a6->a97.1 选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（ B ）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)2．设无向图的顶点个数为n，则
3、该图最多有（ B ）条边。A）n-1B）n(n-1)/2C）n(n+1)/2D）n23．连通分量指的是（ B ）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图4．n个结点的完全有向图含有边的数目（ D ）A）n*nB）n（n+1）C）n/2D）n*（n-1）5．关键路径是（ A ）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）AOV网中从源点到汇点的最短路径6．有向图中一个顶点的度是该顶点的（ C ）A）入度B）出度C）入
4、度与出度之和D）（入度+出度）/27．有e条边的无向图，若用邻接表存储，表中有（ B ）边结点。A）eB）2eC）e-1D）2(e-1)8．实现图的广度优先搜索算法需使用的辅助数据结构为（ B ）A）栈B）队列C）二叉树D）树9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（A ）A）栈B）队列C）二叉树D）树10．存储无向图的邻接矩阵一定是一个（ C ）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵11．在一个有向图中所有顶点的入度之和等于出度之和的（ B ）倍A）1/2B）1C）2D）412．在图采用邻接表存储时，求最小生成树
5、的Prim算法的时间复杂度为（ B ）A）O(n)B）O(n+e)C）O(n2)D）O(n3)13．下列关于AOE网的叙述中，不正确的是（ B ）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成14．具有10个顶点的无向图至少有多少条边才能保证连通（ A ）A）9B）10C）11D）127.2 填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。【答案】22．具有
