Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:

世界六大城市交通里程表(单位:百公里)

PE N PA L T M PE N PA L T M 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 109 82 81 21 124 109 58 55 108 32 82 58 3 97 92 81 55 3 95 89 21 108 97 95 113 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 11 195 c 4 e a 43614 6 7 h 3 2 f 633 56 18 第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分)】

12

37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A，A，34

A，A。

?02?????016????5?04???3??0? A=?

【北京邮电大学2001四、5(5分）】

38．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

（1）．该带权有向图的图形； （2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）．以顶点V1为起点的深度优先周游生成树； （4）．由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】

(顶点边)（出边表）b 6 e 5 h 2 1V1233429625?3 2 5 4 9 8 a 2 c 4 f 2 i 9 z

2V2336?2 1 6 4 1 4 3 d g 9 j 2 3V3? 第39 题图

V44303842?235

1018?16V5 5 6V6?

39．用最短路径算法，求如下图中a到z的最短通路。【西南财经大学 1999 四】

40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。

V1?02???3?V2??032?????V3?4?0?4????V4?1??01??V5??1??03???V6???25?0?

第41题图

【北京邮电大学 2002 四、1 （10分）】

41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】 42．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。

【东南大学 2000 四（10分）】

43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源

点，并写出生成过程。【吉林大学 1999 一、2 (4分)】

15

第43题图

第42题图

44．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 45A3B40E2120 2015CD353020

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为终点，给出所有事件允许发生的最早时间和最晚时间，并

46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因

【西北大学 2000 二、8 (5分)】

48．下图是带权的有向图G的邻接表表示法，求：

（1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。

给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】

2 V1 V3 V5 V7 3 3 10

1 7 4 1 3 2 8 3 6 5 4 6 V8 V6 V4 V2 5

第46题图 第45题图

【青岛海洋大学 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．下表给出了某工程各工序之间的优先关系和各工序所需时间