发布时间 : 星期日 文章专升本数据结构考前必看更新完毕开始阅读878c518bd4d8d15abe234e9c
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网。
在网中，若从顶点i到顶点j有一条有向路径，则i是j 的前驱 AOV网是一种有向无环图。
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图。
1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={
（1）边集E中
2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。 【答案】
【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则 n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。
3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题： （1）图中有多少条边?
（2）任意两个顶点i和j是否有边相连? （3）任意一个顶点的度是多少? 【答案】
（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。 （2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。 （3）任意一个顶点vi的度是第i行或第i列上非0元的个数。
4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。
【答案】邻接矩阵如下： 邻接表如下：
0 1 0 1 0 0
0 0 1 0 1 0 0 0 0 0 0
1
0 1 0 0 1
0
逆邻接表如下： 十字链表如下：
深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF
5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。
【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。
【答案】该无向图如下所示：
深度优先搜索生成树为： 广度优先搜索生成树为：
6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。
【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。 【答案】
【解析】Kruscal算法的操作步骤： 首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。 【答案】
7． 写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。
【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j);
（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0);
（3）计算e(i),l(i)：设ai由弧
e(i)=ve(j)
l(i)=vl(k)-dut(
（4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】
顶点 ve 活动 e l vl l-e V0 0 a0 0 0 0 0 v1 2 a1 0 4 2 4 v2 4 a2 0 1 5 1 v3 10 a3 2 9 10 7 v4 7 a4 2 2 7 0 v5 9 a5 4 5
10 1 v6 14 a6 7 7 14 0 a7 7 10 3 a8 4 5 1 a9 10 10
0 a10 9 10 1 关键路径为：a0->a4->a6->a9 8． 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。
【解析】解题关键是弄清拓扑排序的步骤
（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465
9．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。
【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值，或者是D[j]与vj到vk弧上的权值之和，其中D[j]是已经找到的从v到vj的最短路径。 【答案】S是已找到最短路径的终点的集合。
从v1到各终点的D值和最短路径的求解 终点 i=2 i=4 i=5 i=6 i=3 v2 5 5 (v1,v2) (v1,v2) v3 4 (v1,v3) v4 32767 32767 32767 9 (v1,v2,v5,v4) v5 32767 32767 6 (v1,v2,v5) v6 32767 32767 12 9 9 (v1,v2,v6) (v1,v2,v5,v6) (v1,v2,v5,v6) vj v3 v2 v5 v4 v6 S {v1,v3} {v1,v2} {v1,v2,v5} {v1,v2,v5,v4} {v1,v2,v5,v6}
10．利用Floyd算法求下图中各对顶点之间的路径。
【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，．．．，vk）和(vk，．．．，vj)分别是从