发布时间 : 星期二 文章太原理工大学数据结构试题库及答案更新完毕开始阅读
int arcs[N][N]; }graph;
void funtion(int i,graph *g){ int j;
printf(\ visited[i]=TRUE;
for(j=0;j
if((g->arcs[i][j]==1)&&(!visited[j])) function(j,g); }
答案：实现图的深度优先遍历算法
五、综合题
1、已知图G的邻接矩阵如下所示：
（1）求从顶点1出发的广度优先搜索序列； （2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。
??615????6?5?3??????15?564???? ?5?5??2???36??6???????426???答案：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6
(2)最小生成树（prim算法）
11111111125125333434343456426426426
2、设一个无向图的邻接矩阵如下图所示： （1）画出该图；
（2）画出从顶点0出发的深度优先生成树；
?0?1??1??1?0???00111100?01000??10110??
01011?01101??00110??01答案：(1)图形态 (2)深度优先搜索树
32325454
3、写出下图中全部可能的拓扑排序序列。
152364 答案：1，5，2，3，6，4 1，5，6，2，3，4 5，1，2，3，6，4
5，1，6，2，3，4 5，6，1，2，3，4 4、AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）
3v0v132v3v42v52324v2 答案：(1)最早发生时间和最迟发生时间： (2)关键路径：
顶点v0v1v2v3v4v5ve032668vl032668v02v3v2432v13v42v5
5、已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。（给出求解过程）
v04v24v3951242v17v42
从v0到各终点的d值和最短路径的求解过程 答案： 终点 i=1 v1 v2 v3 v4 vj s 12 (v0,v1) 4 (v0,v2) 9 (v0,v3) 5 (v0,v4) v2 {v0,v2} i=2 12 (v0,v1) 8 (v0,v2,v3) 5 (v0,v4) v4 {v0,v4} i=3 7 (v0,v4,v1) 7 (v0,v4,v3) v1 {v0,v4,v1} i=4 7 (v0,v4,v3) v3 {v0,v4,v3} 6、已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）
v08v2242v6v3756v448v17v58v7 答案：prim算法求最小生成树如下：
v0v06v44v57v6v22v06v44v57v6v22v06v44v5v32v67v22v06v44v5v32v67v06v45v7v224v5v327v6v06v45v74v17v56v4
7、已知有向图如下所示，请写出该图所有的拓扑序列。
v2v3v1v4v5v8v6v7
答案：拓扑排序如下：
v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8
v1, v2, v6, v4, v5, v3, v7, v8 v1, v2, v6, v4, v5, v7, v3, v8 v1, v6, v2, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v7, v3, v8 8、如下图所示的AOE网，求：
（1）求事件的最早开始时间ve和最迟开始时间vl；
事件 1 2 3 4 5 6 7 8 9 Ve Vl V2a1a416a24a35V4a62V6V3a94a51V5a79a87V8a114V9汇点 V7 （2）求出关键路径； a102V1源点
答案：(1)求ve和vl (2)关键路径
事件vevl100*266*346458577*671071616*81414*91818*v16v21v57v849v72v9如下所示的有向图，回答下面问题：
v1v2
（1）该图是强连通的吗？若不是，给出强连通分量。 （2）请给出图的邻接矩阵和邻接表表示。
答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：
0010100001011000v1v2v3v4v2v3v1v3v4v4v3
??112610??1?89????9、已知图G的邻接矩阵A=?128??2?，试画出它所表示的图G，并根据Prim算
???69??4???10?24???法求出图的的最小生成树（给出生成过程）。 答案：
(1)图形态： (2)prim算法求最小生成树：