数据结构第五章图习题

05 图图 单选题 1 设无向图 G 中有五个顶点 各顶点的度分别为 2 4 3 1 2 则 G 中边数为 C 4 条 5 条 6 条 无法确定 2 含 n 个顶点的无向完全图有 D 条边 含 n 个顶点的有向图最多有 C 条弧 含 n 个顶点的有 向强连通图最多有 C 条弧 含 n 个顶点的有向强连通图最少有 条弧 设无向图中有 n 个顶 点 则要接通全部顶点至少需 G 条边 A n2 B n n 1 C n n 1 D n n 1 2 E n 1 F n G n 1 3 对下图从顶点 a 出发进行深度优先遍历 则 A 是可能得到的遍历序列 A acfgdeb B abcdefg C acdgbef D abefgcd 对下图从顶点 a 出发进行广度优先遍历 则 D 是不可能得到的遍历序列 A abcdefg B acdbfge C abdcegf D adcbgef 4 设图 G 的邻接矩阵 A 则 G 中共有 C 个顶点 若 G 为有向图 则 G 中共有 D 010 101 010 条弧 若 G 为无向图 则 G 中共有 B 条边 A 1 B 2 C 3 D 4 E 5 F 9 G 以上答案都不对 5 含 n 个顶点的图 最少有 B 个连通分量 最多有 D 个连通分量 A 0 B 1 C n 1 D n 6 用邻接表存储图所用的空间大小 A A 与图的顶点数和边数都有关 B 只与图的边数有关 C 只与图的顶点数有关 D 与边数的平方有关 7 n 个顶点的无向图的邻接表最多有 B 个表结点 A n2 B n n 1 C n n 1 D n n 1 2 8 无向图 G V E 其中 V a b c d e f E a b a e a c b e c f f d e d 对该图进行深度优 先遍历 得到的顶点序列正确的是 D A a b e c d f B a c f e b d C a e b c f d D a e d f c b 9 图的 BFS 生成树的树高比 DFS 生成树的树高 A A 小或相等 B 小 C 大或相等 D 大 10 下列不正确的是 C 1 求从指定源点到其余各顶点的迪杰斯特拉 Dijkstra 最短路径算法中弧上权不能为负的原因是在实 际应用中无意义 2 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O n3 图用邻接矩阵表示 3 Floyd 求每对不同顶点对的算法中允许弧上的权为负 但不能有权和为负的回路 A 1 2 3 B 1 C 1 3 D 2 3 11 当各边上的权值 A 时 BFS 算法可用来解决单源最短路径问题 A 均相等 B 均互不相等 C 不一定相等 12 若一个有向图具有拓扑排序序列 那么它的邻接矩阵必定为 C A 对称矩阵 B 稀疏矩阵 C 三角矩阵 D 一般矩阵 13 在有向图 G 的拓扑序列中 若顶点 Vi 在顶点 Vj 之前 则下列情形不可能出现的是 D A G 中有弧 B G 中有一条从 Vi 到 Vj 的路径 C G 中没有弧 D G 中有一条从 Vj 到 Vi 的路径 14 关键路径是 AOE 网中 B A 从始点到终点的最短路径 B 从始点到终点的最长路径 C 人始点到终点的边数最多的路径 D 从始点到终点的边数最少的路径 15 下面关于求关键路径的说法不正确的是 C A 求关键路径是以拓扑排序为基础的 B 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D 关键活动一定位于关键路径上 填空题 1 设无向连通图 G 含 n 个顶点 e 条边 则 G 的生成树含 个顶点 条边 2 连通分量是无向图的 子图 生成树是无向连通图的 子图 3 对稀疏图而言 在邻接矩阵和邻接表这两种存储结构中选择 更为适宜 4 设无向图 G 含 n 个顶点 e 条边 则 G 的邻接表表示中含 个边表结点 5 设有向图 G 含 n 个顶点 e 条弧 则 G 的邻接表表示中含 个边表结点 计算题 1 设无向图如下 写出对该图从顶点 a 出发进行广度优先遍历可能得到的所有遍历序列 解 解 abcdefg abdcegf acbdfeg acdbfge adbcgef adcbgfe 2 设有向图如下 写出对该图从顶点 a 出发进行深度优先遍历可能得到的所有遍历序列 解 解 abedc acbed acdbe 3 设无向网如下 1 写出其邻接矩阵 2 基于该邻接矩阵求深度优先生成树和广度优先生成树 3 基于该邻接矩阵按普里姆算法求最小生成树 4 写出其邻接表 5 基于该邻接表按克鲁斯卡尔算法求 最小生成树 解 解 1 645 625 236 379 456755 5553 9554 34 2 深度优先生成树 广度优先生成树 3 最小生成树 求解过程 4 邻接表 5 最小生成树 4 设 AOV 图如下 写出对该图进行拓扑排序可能得到的所有拓扑序列 解 解 abcdefg abcdfeg abcfdeg 5 设 AOE 网如下 试求关键路径 解 关键路径 v1 v2 v5 v7 关键路径 v1 v3 v6 v7 6 设有向网如下 试用迪杰斯特拉算法求从顶点 A 出发到其余各顶点的最短路径 解 解 ab 3 af 5 afe 7 abc 11 afed 14 7 设有向网如下 试用弗洛伊德算法求图中各对顶点间的最短路径 解 算法题 下列算法题中可能用到的类如下 public class MGraph private Object vexs private int adj private int vexnum private int arcnum public MGraph int maxvn int i j vexs new Object maxvn adj new int maxvn maxvn for i 0 i maxvn i for j 0 j maxvn j adj i j 0 vexnum 0 arcnum 0 构造函数 图的邻接矩阵存储结构类 public class ALANode public int adj public ALANode next 图的邻接表存储结构中的表结点类 public class ALVNode public Object data 顶点信息 public ALANode firstarc 图的邻接表存储结构中的头结点类 public class ALGraph private ALVNode vexs private int vexnum private int arcnum public ALGraph int maxvn vexs new ALVNode maxvn vexnum 0 arcnum 0 构造函数 图的邻接表存储结构类 1 在 ALGraph 类中添加符合如下要求的构造函数 public ALGraph Object v ArcArray a 其中 v 为顶点向量 a 为弧向量 类 ArcArray 的定义如下 public class ArcArray private int index1 弧尾顶点下标 private int index2 弧头顶点下标 2 public ALGraph MGraph g 2 在 ALGraph 类中添加实现如下功能的方法 1 在无向图中插入一个顶点 2 在无向图中删除一个顶点 3 在无向图中添加一条边 4 在无向图中删除一条边 5 判定无向图中是否存在从顶点 vi到顶点 vj的路径 i j 6 输出无向图中从顶点 vi到顶点 vj的所有简单路径 解 5 public boolean path int i int j 从顶点 vi出发进行深度优先遍历 调用完成时所有与 vi有路径相通的顶点都被访问到 boolean visited new boolean vexs length for k 0 k vexnum k visited k false dfs i visited return visited j path void dfs int i boolean visited 从顶点 vi出发对图 G 进行深度优先遍历 visited i true for p vexs i firstarc p p p next if visited p adj dfs p adj visited dfs 3 在 MGraph 类中添加符合如下要求的构造函数 1 public class MGraph Object v EdgeArray e 其中 v 为顶点向量 e 为边向量 类 EdgeArray 的定义如下 public class EdgeArray p