发布时间 : 星期三 文章第七章 图更新完毕开始阅读ff5e30e19b89680203d825c8
【东南大学 1994 一、2 （8分） 1998 一、6（8分）】
12．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？
【清华大学 1999 一、5 （2分）】
13．假定Ｇ＝（V，E）是有向图，V＝｛1,2，．．．,N｝，N＞＝1，G以邻接矩阵方式存储，G的邻接矩阵为A，即Ａ是一个二维数组，如果i到j有边，则A[i,j]=1，否则A[i,j]=0，请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O(n*n)。
【吉林大学 1998 三(16分)】
14． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。 【天津大学 1999 一】 15．下面的邻接表表示一个给定的无向图
（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分))
1 2 5 6 7 3 4 8 2 5 1 3 6 4 7
8 9 10 9
15题图 14题图 16题图 16．给出图G：
（1）．画出G的邻接表表示图； （2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。 【南开大学 1997 五 (14分)】
17．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。
234?1 5?1342 124? 31235? 4 524? 【北京轻工业学院 1998 八 （6分）】
18．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？
【北京航空航天大学 1998 一、7 （4分）】 19．解答下面的问题 （1）．如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权值占2个字节。下图采用哪种表示法所需的空间较多？为什么?
2 9 8 7 10 5
20 4 1 1 10 5 6
10 2 3 3 2 6 11 4 3 15 3 5
19题图 20题图
（2）．写出下图从顶点1开始的DFS树。【西安电子科技大学 2000计应用 六 （10分）】 20．如下所示的连通图，请画出： （1）．以顶点①为根的深度优先生成树；（5分） （2）．如果有关节点，请找出所有的关节点。（5分）【清华大学 1998 七 （10分）】 21．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A ,B ,?，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件). （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列.
【北京科技大学 1999 五 2000 五 （12分）】 22．已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。【燕山大学 2000 五 （5分）】 234?v1
5?1v2
5?1v3
v416?
v523? v64?
第22题图 第23题图 23．已知某图的邻接表为
（1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（2分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（2分） （6）．写出将无向图的邻接表转换成邻接矩阵的算法。（8分） 【山东大学 1998 六、18分】
A 2 24．考虑右图：
5 D 6 4 C (1)从顶点A出发，求它的深度优先生成树
B E 1 (2)从顶点E出发，求它的广度优先生成树
3 5 3 （3）根据普利姆(Prim) 算法， 1 F G 求它的最小生成树【上海交通大学 1999 六 (12分)】
25.在什么情况下，Prim算法与Kruskual算法生成不同的MST？
【西安电子科技大学 2000计应用 一、11 （5分）】 26．下面是求无向连通图最小生成树的一种方法。
将图中所有边按权重从大到小排序为（e1,e2,?,em）
i:=1
WHILE (所剩边数 >=顶点数)
BEGIN
从图中删去ei
若图不再连通，则恢复ei i:=i+1 END.
试证明这个算法所得的图是原图的最小代价生成树。【北京邮电大学 1999 五 （10分）】
27．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学 1999 九 （8分）】
20 1 4 1 9 4 2 5 11 9 7 8 6 2 6 14 6 3 10 5 3 10 2 5
4 4 6 5 18
27题图 28题图
28．G=(V,E)是一个带有权的连通图,则：
（1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。【北方交通大学 1993 二 （12分）】 29．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。
5
21 7818 22 5 1 6 12 8323 85 15 8 3 4 7 643325 7 6 24 10 7420 3
4765第29图 6【吉林大学 2000 一、3 (3分)】 30.求出下图的最小生成树。【合肥工业大学 1999 四、2 （5分）】 第30题图 31．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。
【浙江大学 1994 五 (8分)】 第32题图
32．请看下边的无向加权图。 （1）．写出它的邻接矩阵（ 5分） （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分）
辅助数组内各分量值：【华北计算机系统工程研究所 1999 四 （20分）】 Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U V.-U 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)