好文档 - 专业文书写作范文服务资料分享网站

数据结构试题集(含答案) 

天下 分享 时间: 加入收藏 我要投稿 点赞

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

36

顶点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算法求最小生成树如下:

37

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如下所示的有向图,回答下面问题:

v1v2v4v3 38

(1)该图是强连通的吗?若不是,给出强连通分量。 (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算法的最小生成树

39

B2B2D3B2D3B2A4D3FFKF3KF3CKHHB2A4D3B25A4D3B25A45D3F3C4KF3C4KF3C4KHEHEHE

5 d 3 2 5 3 f

12、已知图G如下所示,求从顶点a到其余各顶点的最短路径。(给出求解过程)

b 6 a 3 c 4 2 e 答案: 终点 最短路径求解过程 b 6 5 (a,c,b) (a,b) c 3 (a,c) d 6 (a,c,d) 6 ? (a,c,d) e 7 (a,c,e) 7 7 ? (a,c,e) (a,c,e) f 9 ? ? ? (a,c,d,f) vj c b d e S {a,c} {a,c,b} {a,c,d} {a,c,e} 9 (a,c,d,f) f {a,c,d,f} 40

数据结构试题集(含答案) 

111111111251253334343434564264264262、设一个无向图的邻接矩阵如下图所示:(1)画出该图;(2)画出从顶点0出发的深度优先生成树;?01110?10100??11011??10101?00110??00011?0100?0??0??1?1??0??答案:(1)图形态
推荐度:
点击下载文档文档为doc格式
3jamd0g5vr3gyk7183zd
领取福利

微信扫码领取福利

微信扫码分享