发布时间 : 星期三 文章第七章 图更新完毕开始阅读ff5e30e19b89680203d825c8
PE N PA L T M PE 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113
（1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五 （14分）】 34．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边 的两个端点和其权值，共11行。请你： （1）．采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出存
储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 （2）．分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的 生成树。 （3）．按prim算法列表计算，从顶点1始求最小生成树，并图示该树。 【北京工业大学 1999 四(20分)】
35．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】
16 21 2153 d 8 1 b 5 114 19e 5 c a 43614 2 f 6 7 h 3 633 5618 第36题图
36．设无向网G 如上： 第35题图 （1）． 设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G 的邻接表结构: （2）．写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的顶点序列： 按Prim算法求出网G的一棵最小生成树。【北京科技大学 2001 五 (12分)】
1234
37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A，A，A，A。 1 2 5 1 3 8 1 4 3 2 4 6 2 3 2 3 4 4 3 5 1 3 6 10 4 5 7 4 6 11 5 6 15 ?02?????016????5?04???3??0?? A=
【北京邮电大学2001四、5(5分）】
38．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
（1）．该带权有向图的图形； （2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）．以顶点V1为起点的深度优先周游生成树； （4）．由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】
(顶点边)（出边表）6 b e 5 h 2 233429625?1V15 4 9 8 3 2 2 c 4 2V22 i 9 336?a z f
2 1 6 4 4 3V3?1 2 3 9 j d g V44303842?235
110618? 5V5第39题图
6V6?
39．用最短路径算法，求如下图中a到z的最短通路。【西南财经大学 1999 四】
40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。
V1?02???3?V2??032?????V3?4?0?4????V4?1??01??V5??1??03???V6???25?0?
601105301562316787102036154683 第41题图 【北京邮电大学 2002 四、1 （10分）】
41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】
42．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。
【东南大学 2000 四（10分）】
43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写
出生成过程。【吉林大学 1999 一、2 (4分)】 45b 615 4 340ABE 28ace 2120 2015CD35301254109
44．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。【同济大学 1998 一 (12分 )】 45．已知一图如下图所示：
（1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序； （3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】 2 V1 V3 V5 3 3 V7 10 1 7 3 2 1 4 2 8
3 6 5 4 V6 6 V8 V4 V2 5 第46题图 第45题图 46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因
【西北大学 2000 二、8 (5分)】
48．下图是带权的有向图G的邻接表表示法，求：
（1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列；
（3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。
【青岛海洋大学 1999 四（10分）】
49．对有五个结点{ A,B, C, D, E}的图的邻接矩阵，
?010030?10???0????????60020??????10?0???????500?? （1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。
【华南师范大学 1999 三 (20分)】
50．何为AOE网的始点和终点，一个正常的AOE网是否只有一个始点和一个终点？
【首都经贸大学 1997 一、4 （4分）】
51．下表给出了某工程各工序之间的优先关系和各工序所需时间
（1）．画出相应的AOE网 （2）．列出各事件的最早发生时间,最迟发生时间 （3）．找出关键路径并指明完成该工程所需最短时间. 【武汉交通科技大学 1996 二、6 (7分)】
工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 -- -- A,B B C,D B E G,I E I F,I H,J,K L G 52．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。【北京轻工业学院 1997 四 （15分）】