内容发布更新时间 : 2024/4/19 8:22:54星期一 下面是文章的全部内容请认真阅读。

(1)请画出该AOE图。

(2)计算完成整个计划需要的时间。 (3)求出该AOE网的关键路径。 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝

6 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 5 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 9 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 7 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 4 ∝ 判断题

1．求最小生成树的Prim算法在边较少、结点较多时效率较高。（ ） 2．图的最小生成树的形状可能不唯一。（ ）

3．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )

4． 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( ) 5． 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。( ) 6． 有回路的图不能进行拓扑排序。( )

7． 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。( )

8. 用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可。( )

9. 在AOE网中一定只有一条关键路径。( )

10. 缩短关键路径上活动的工期一定能够缩短整个工程的工期。( )

m

11. 连通分量是无向图中的极小连通子图。( ) 12. 强连通分量是有向图中的极大强连通子图。( )

算法设计题

1．试以邻接矩阵为存储结构实现图的基本操作：InsertVex (G,v)、InsertArc (G,v,w)、DeleteVex (G,v)和DeleteArc (G,v,w)。

2． 试以邻接表为存储结构实现算法设计题1中所列图的基本操作。 3．试以十字链表为存储结构实现算法设计题1中所列图的基本操作。 4．试以邻接多重表为存储结构实现算法设计题1中所列图的基本操作。 5．试写一算法由图的邻接链表存储得到图的十字链表存储。

6．写一算法，由依次输入图的顶点数目、边的数目、各顶点的信息和各条边的信息建立无向图的邻接多重表。

7．试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

假设分别基于下述策略： （1）图的深度优先搜索; （2）图的宽度优先搜索。

8．试修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子－兄弟链表）。

9．以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法。

10．给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连结，边上的权Wij表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在那个村庄，才能使离医院最近的村庄到医院的路程最短？试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。

12 6 2 1 5 2 9 4 4 10 4 7 6 3 6 2

3 景点不少于10个。以图中顶点表示校内各景点。

１１.假设Ｇ采用邻接表存储，设计一个算法，判断无向图Ｇ是否连通。若连通则返回１；否则返回0。 １２. 假设Ｇ采用邻接表存储，设计一个算法，判断无向图Ｇ中顶点i到顶点j是否有路径，若有则返回１，否则返回0。

上机实习题目

设计一个校园导游程序，为来访的客人提供各种信息查询服务。

基本要求：

（1）设计你所在学校的校园平面图，所含场所不少于10个。以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意场所相关信息的查询。

（3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。

选作：

（1）提供图中任意场所得问路查询，即求任意两个场所之间的所有路径。 （2）校园导游图的场所与道路的修改与扩充功能。

习题答案

1. C

4. C

5. A

6. A

9. AC 11. CB

12. A

13. D

2. 1;0 3. 1

,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6 5.求矩阵第i列非零元素之和

6. 将矩阵第i行全部置为零

9.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）； 遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过 的结点。

10．邻接矩阵 邻接表

11．一个结点可能有若干个前驱，也可能有若干个后继 12．2 13．唯一

26157197421543428649 (2)完成整个计划需要18天。

(3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）