浙大远程数据结构与算法离线答案-最完整版(7)

【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：

V0 0 1 0 1 1 0 0 0 V1 1 0 1 0 1 0 0 0 V2 0 1 0 0 0 1 0 0 V3 1 0 0 0 0 0 1 0 V4 1 1 0 0 0 0 1 0 V5 0 0 1 0 0 0 0 0 V6 0 0 0 1 1 0 0 1 V7 0 0 0 0 0 0 0 1

(1) 画出该图的图形；

(2) 给出从V0出发的深度优先遍历序和广度优先遍历序。 答：

深度优先：01254673 广度优先：01324657

31

【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；

（5） 各个强连通分量 答案： （1）： 节点号 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （2）：

1 0 1 0 0 1 1 2 1 0 1 1 0 1 3 0 1 0 1 0 1 4 0 1 1 0 1 1 5 1 0 0 1 0 1 6 1 1 1 1 1 0 (3)：

32

（（4）：

（5）：

1：无强连通分量

33

【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。

答： 初始（第0步） 第一步（选C） 第二步(选F) 第三步(选E) 第四步(选G) 第五步(选D) 第六步(选B) 终点 D

P D P D P D 34

P D P D P D P B C D E F G

15 2 12 ∞ ∞ ∞ 0 0 0 15 2 12 10 6 ∞ A A A C C 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 16 A A A C C F 15 2 12 10 6 15 A A A C C D 15 2 12 10 6 15 A A A C C D 【21，6，3】给出如下图所示的具有7个结点的网G。请：

（1） 画出该网的邻接矩阵；

（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法

的执行过程及最小生成树的生成示意图）。

1

答： （1）：

0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 2 1 0 0 0 1 0 1 3 0 1 0 0 0 1 1 4 0 0 1 0 0 1 1 5 0 0 0 1 1 0 1 6 1 1 1 1 1 1 0

35

1 6 2 3 7 4 0 5 6 2 5 3 3 2 5 1 4 4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库浙大远程数据结构与算法离线答案-最完整版(7)在线全文阅读。