一、选择题
1、下面关于工程计划的事件结点网络的叙述中, 哪一个是不正确的? （1） 关键活动不按期完成就会影响整个工程的完成时间。 （2） 何一个关键活动提前完成, 那么整个工程将会提前完成。 （3） 有的关键活动都提前完成, 那么整个工程将会提前完成。 （4） 某些关键活动若提前完成, 那么整个工程将会提前完成。 （5） 任何一个关键活动延迟将会导致整个工程延迟。
2、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 （每小题1分，共5分）
（1） 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。
（2） 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ C ）。 （3） 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。
（4） 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。 【供选择的答案】 A：① n B：① e/2
② n+1 ② e
③ n-1 ③ 2e
④ n+e ④ n+e ④ 按层次遍历
C~D：① 中序遍历 ② 前序遍历
③ 后序遍历
E：① 求关键路径的方法 ③ 深度优先遍历算法
② 求最短路径的Dijkstra方法 ④ 广度优先遍历算法（p194）
二、判断题
3、判断下列叙述的对错。如果正确，在题前的括号内填入“”，否则填入“”。 （1）用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与
图中的顶点个数有关，而与图的边数无关。
（2） 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
1
（3） 有回路的有向图不能完成拓扑排序。
（4） 有n （n≥1） 个顶点的无向连通图最少有n-1条边。 （5） 有n （n≥1） 个顶点的有向强连通图最少有n条边。（P192）
四、填空题
4、填空题 （每小空1分，共5分）
在一个无向图中所有顶点的度数之和等于所有边数的（ A ）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ B ）倍。
若已给出一个有向图的邻接矩阵，则计算第i个顶点的入度的方法是（ C ），删除所有从第i个顶点发出的边的方法是（ D ）。
在无向图的邻接矩阵A中，若A[i][j] = 1，则A[j][i] = （ E ）。
五、简答题
5、用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？（p177）
6、对于如右图所示的有向图，试写出：
（1） 从顶点①出发进行深度优先搜索所得到的深度优先生成树； （2） 从顶点②出发进行广度优先搜索所得到的广度优先生成树；（p178）
7、以右图为例，按Dijkstra算法计算得到的从顶点①到其它各个顶点的最短路径和最短路径长度。
2
8、若用一个连通图来表示一个通信网络, 如图所示。
其中, 顶点表示网络中的通信站点, 边表示网络中的通信线路, 则 （1） 画出从顶点①出发的深度优先生成树；
（2） 在原来的图中补充几条边, 使其中某一站点失效时整个通信网络仍然保持畅通。 （3） 指出图中哪几个顶点是关节点（即万一它失效则通信网络将发生故障）。
9、试对下图所示的AOE网络
（1） 这个工程最早可能在什么时间结束。
（2） 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 （3） 求每个活动的最早开始时间e（ ）和最迟开始时间l（ ）。
（4） 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整
个工程提前完成。（p191）
10、一项工程由六个子工程p1， p2， ， p6组成。这些子工程之间有下列关系：p1 < p2， p3 < p6， p4 < p3， p2 < p6， p4 < p5， p1 < p3， p5 < p6。符号“<”表示“领先于”的关系。例如，p2 < p6表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。
六、算法设计题
11、设有一个有向图存储在邻接表中。试设计一个算法，按深度优先搜索策略对其进行拓扑排序。（190）
3
因篇幅问题不能全部显示，请点此查看更多更全内容