数据结构 陈雁 第5章自测练习题参考答案.docx

数据结构 陈雁 第5章 自测练习题参考答案第5章 自测练习题参考答案 1.设一个有向图G =，其中V= v1，v2，v3，v4 ，E=v1，v4，v2，v1，v2，v3，v4，v1，v4，v2。请画出该有向图，并求出每个顶点的入度与出度，画出相应的邻接矩阵、邻接表和逆邻接表。 解： 有向图： 3 2 1 4 V1入度2，出度1， v2入度1，出度2, v3入度1，出度0， v4入度1，出度2 邻接阵： 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 邻接表： 1 4 2 1 3 3 4 1 2 逆邻接表： 1 2 4 2 3 4 2 4 1 1 2分别求出题图5-1从v2出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 解 ： 广度优先序列是：v2,v1,v3,v6,v4,v5 深度优先序列是：v2,v1,v3,v4,v5,v6 3.已知一个有向图的邻接表如题图5-2所示，求出根据深度优先搜索算法从顶点v1出发遍历得到的顶点序列。 解 ： 深度优先序列是：v1,v3,v4,v5,v2 广度优先序列是：v1,v3,v2,v4,v5 4.分别用普里姆和克鲁斯卡尔算法构造题图5-3所示网络的最小生成树。 解 ： 普里姆算法： v2 (v1,v3) (v3,v4) v5 (v4,v5) v6 1 v3 4 (v4,v2) 或 (v5,v2) 6 2 v4 v2 克鲁斯卡尔算法： (v4,v5) v5 (v2,v4) 或 (v2,v5) v6 1 v3 4 (v1,v3) 6 2 (v3,v4) v4 5.求出题图5-4从顶点v1到其它各顶点之间的最短路径。 解： (v1-v3 ) 5 (v1-v3-v6) 15 (v1-v3-v6-v4) 19 (v1-v2) 20 (v1-v3-v6-v5) 25 2 6.画出题图5-5所示的AOV网所有可能的拓扑有序序列。并指出应用拓扑排序算法求得的是那一个序列？ 解： 所有可能的拓扑有序序列： v1,v4,v2,v5,v3 ,v6 1 V1 0 2 V2 2 3 V3 1 4 V4 0 2 3 6 5 2 v1,v4,v2,v3,v5, v6 5 V 5 1 v1,v4,v5,v2,v3, v6 6 V 6 v4,v1,v2,v5,v3, v6 6 2 v4,v1,v2,v3,v5, v6 题图 5-5 AOV网的邻接表表示 v4,v1,v5,v2,v3, v6 v4,v5,v1,v2,v3, v6 根据邻接表，应用拓扑排序算法求得的序列是： v4,v5,v1,v2,v3 v6 3