数据结构试题集(包含答案 - 完整版) 下载本文

11111111125125333434343456426426426

2、设一个无向图的邻接矩阵如下图所示: (1)画出该图;

(2)画出从顶点0出发的深度优先生成树;

?01110?10100??11011??10101?00110??00011?0100?0??0?? 1?1??0??答案: (1)图形态 (2)深度优先搜索树

132325454

43、写出下图中全部可能的拓扑排序序列。

15236 答案: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)关键路径:

顶点v0v1v2v3v4v5ve032668vl032668v023v13v42v5v3v242

5、已知有向图G如下所示,根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。(给出求解过程)

v04v24v32v49512427v1

答案: 终点 v1 v2 v3 v4 vj s 从v0到各终点的d值和最短路径的求解过程 i=1 i=2 i=3 i=4 12 (v0,v1) 12 (v0,v1) 7 (v0,v4,v1) 4 (v0,v2) 9 (v0,v3) 8 7 7 (v0,v2,v3) (v0,v4,v3) (v0,v4,v3) 5 (v0,v4) 5 (v0,v4) v2 v4 v1 v3 {v0,v2} {v0,v4} {v0,v4,v1} {v0,v4,v3} 6、已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)

v08v2242v6v3756v448v17v58v7 答案:prim算法求最小生成树如下:

v0v06v44v57v6v06v44v57v22v6v06v44v5v32v22v67v06v44v5v32v22v67v06v45v7v224v5v327v6v06v45v74v17v56v4

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 (2)求出关键路径; V2a1a416a24a35V4a62V6V3a94a51V5a79a87V8a114V9汇点V7a102V1源点

答案:(1)求ve和vl (2)关键路径

事件vevl100*266*346458577*671071616*81414*91818*v16v21v57v849v72v9如下所示的有向图,回答下面问题:

v1v2 (1)该图是强连通的吗?若不是,给出强连通分量。

v4v3(2)请给出图的邻接矩阵和邻接表表示。

答案:(1) 是强连通图 (2) 邻接矩阵和邻接表为:

0010100001011000v1v2v3v4v2v3v1v3v4

??112610??1?89?????9、已知图G的邻接矩阵A=128??2?, 试画出它所表示的图G,并根据Prim??69??4????10?24???算法求出图的的最小生成树(给出生成过程)。

答案:

(1)图形态: (2)prim算法求最小生成树:

v112102v54v3189v4v118v3v5v22v5v324v4v2v11v2v118v3v2v118v2

10、如下图所示的AOV网,写出其中三种拓扑排序序列。

v0v2v1v3v4v5v6v7

11、已知图G如下,根据克鲁斯卡尔算法求图G的一棵最小生成树。(要求给出构造过程)

答案:kruskal算法的最小生成树