数据结构第7章-图习题

第第 7 章章 图图 一 单项选择题一 单项选择题 1 在一个无向图 G 中 所有顶点的度数之和等于所有边数之和的 倍 A l 2B 1 C 2D 4 2 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 倍 A l 2 B 1 C 2D 4 3 一个具有 n 个顶点的无向图最多包含 条边 A n B n 1 C n 1 D n n 1 2 4 一个具有 n 个顶点的无向完全图包含 条边 A n n l B n n l C n n l 2 D n n l 2 5 一个具有 n 个顶点的有向完全图包含 条边 A n n 1 B n n l C n n l 2 D n n l 2 6 对于具有 n 个顶点的图 若采用邻接矩阵表示 则该矩阵的大小为 A n B n n C n 1 D n l n l 7 无向图的邻接矩阵是一个 A 对称矩阵 B 零矩阵 C 上三角矩阵 D 对角矩阵 8 对于一个具有 n 个顶点和 e 条边的无 有 向图 若采用邻接表表示 则表头 向量的大小为 A n B e C 2n D 2e 9 对于一个具有 n 个顶点和 e 条边的无 有 向图 若采用邻接表表示 则所有 顶点邻接表中的结点总数为 A n B e C 2n D 2e 10 在有向图的邻接表中 每个顶点邻接表链接着该顶点所有 邻接点 A 入边 B 出边 C 入边和出边 D 不是入边也不是出边 11 在有向图的逆邻接表中 每个顶点邻接表链接着该顶点所有 邻接点 A 入边 B 出边 C 入边和出边 D 不是人边也不是出边 12 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点 则该图一定是 A 完全图 B 连通图 C 有回路 D 一棵树 13 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 算法 A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 14 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 算法 A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 15 如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点 则下列说 法中不正确的是 A G 肯定不是完全图 B G 一定不是连通图 C G 中一定有回路 D G 有二个连通分量 16 下列有关图遍历的说法不正确的是 A 连通图的深度优先搜索是一个递归过程 B 图的广度优先搜索中邻接点的寻找具有 先进先出 的特征 C 非连通图不能用深度优先搜索法 D 图的遍历要求每一顶点仅被访问一次 17 下列说法中不正确的是 A 无向图中的极大连通子图称为连通分量 B 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D 有向图的遍历不可采用广度优先搜索方法 18 一个有向图 G 的邻接表存储如下图 7 1 所示 现按深度优先搜索遍历 从 顶点 v1出发 所得到的顶点序列是 A v1 v2 v3 v4 v5 B v1 v2 v3 v5 v4 C v1 v2 v4 v5 v3 D v1 v2 v5 v3 v4 图 7 1 一个有向图的邻接表 19 对图 7 2 所示的无向图 从顶点 1 开始进行深度优先遍历 可得到顶点访 问序列 A 1 2 4 3 5 7 6 B 1 2 4 3 5 6 7 C 1 2 4 5 6 3 7 D 1 2 3 4 5 7 6 图 7 2 一个无向图 20 对图 7 2 所示的无向图 从顶点 1 开始进行广度优先遍历 可得到顶点访 问序列 A 1 3 2 4 5 6 7 B 1 2 4 3 5 6 7 23 4 35 5 4 v1 v2 v3 v4 v5 1 6 5 4 3 2 7 C 1 2 3 4 5 7 6 D 2 5 1 4 7 3 6 21 一个无向连通图的生成树是含有该连通图的全部顶点的 A 极小连通子图 B 极小子图 C 极大连通子图 D 极大子图 22 设无向图 G V E 和 G V E 如果 G 为 G 的生成树 则下列说法 中不正确的是 A G 为 G 的连通分量 B G 为 G 的无环子图 C G 为 G 的子图 D G 为 G 的极小连通子图且 V V 23 任意一个无向连通图 最小生成树 A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在 24 对于含有 n 个顶点的带权连通图 它的最小生成树是指图中任意一个 A 由 n 1 条权值最小的边构成的子图 B 由 n 1 条权值之和最小的边构成的子图 C 由 n 1 条权值之和最小的边构成的连通子图 D 由 n 个顶点构成的边的权值之和最小的生成树 25 若一个有向图中的顶点不能排成一个拓扑序列 则可断定该有向图 A 是个有根有向图 B 是个强连通图 C 含有多个入度为 0 的顶点 D 含有顶点数目大于 1 的强连通分 量 26 判定一个有向图是否存在回路除了可以利用拓扑排序方法外 还可以用 A 求关键路径的方法 B 求最短路径的 Dijkstra 算法 C 广度优先遍历算法 D 深度优先遍历算法 27 求最短路径的 Dijkstra 算法的时间复杂度为 A O n B O n e C O n2 D O ne 28 求最短路径的 Floyd 算法的时间复杂度为 A O n B O ne C O n2 D O n3 29 关键路径是事件结点网络中 A 从源点到汇点的最长路径 B 从源点到汇点的最短路径 C 最长的回路 D 最短的回路 30 下面说法不正确的是 A 在 AOE 网中 减少任一关键活动的权值后 整个工期也就相应减少 B AOE 网工程工期为关键活动的权值和 C 在关键路径上的活动都是关键活动 而关键活动也必须在关键路径上 D A 和 B 31 下面说法不正确的是 A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成 将使整个工程提前完成 C 所有关键活动都提前完成 则整个工程提前完成 D 某些关键活动若提前完成 将使整个工程提前完成 二 填空题二 填空题 1 对于具有 n 个顶点的无向图 G 最多有 条边 2 对于具有 n 个顶点的强连通有向图 G 至少有 条边 3 对于具有 n 个顶点的有向图 每个顶点的度最大可达 4 若无向图 G 的顶点度数最小值大于 时 G 至少有一条回路 5 对于一个具有 n 个顶点和 e 条边的无向图 若采用邻接表表示 则表头向量 的大小为 所有邻接表中的结点总数是 6 已知一个有向图的邻接矩阵表示 删除所有从第 i 个结点出发的弧的方法是 7 对于 n 个顶点的无向图 采用邻接矩阵表示 求图中边数的方法是 判断任意两个顶点 i 和 j 是否有边相连的方法是 求 任意一个顶点的度的方法是 8 对于 n 个顶点的有向图 采用邻接矩阵表示 求图中边数的方法是 判断任意两个顶点 i 和 j 是否有边相连的方法是 求 任意一个顶点的度的方法是 9 无向图的连通分量是指 10 已知图 G 的邻接表如图 7 3 所示 从顶点 v1出发的深度优先搜索序列为 从顶点 1 出发的广度优先搜索序列为 图 7 3 图 G 的邻接表 11 n 个顶点连通图的生成树一定有 条边 12 一个连通图的 是一个极小连通子图 13 Prim 算法适用于求 的网的最小生成树 Kruskal 算法适用于求 的网的最小生成树 14 在 AOV 图中 顶点表示 有向边表示 15 可以进行拓扑排序的有向图一定是 16 从源点到汇点长度最长的路径称为关键路径 该路径上的活动称为 17 Dijkstra 算法从源点到其它各顶点的路径长度按 次序依次产生 该 算法在边上的权出现 情况时 不能正确产生最短路径 18 求从某源点到其余各项点的 Dijkstra 算法在图的顶点数为 10 用邻接矩阵 表示图时计算时间约为 10ms 则在图的顶点数为 40 时 计算时间约为 ms 三 判断题三 判断题 1 具有 n 个顶点的无向图至多有 n n 1 条边 v1 v2 v3 v4 v5 v6 23 4 35 6 4 63 2 有向图中各顶点的入度之和等于各顶点的出度之和 3 邻接矩阵只储存了边的信息 没有存储顶点的信息 4 对同一个有向图 只保存出边的邻接表中结点的数目总是和只保存入边的邻 接表中结点的数目一样多 5 如果表示图的邻接矩阵是对称矩阵 则该图一定是无向图 6 如果表示有向图的邻接矩阵是对称矩阵 则该有向图一定是有向完全图 7 如果表示某个图的邻接矩阵不是对称矩阵 则该图一定是有向图 8 连通分量是无向图的极小连通子图 9 强连通分量是有向图的极大连通子图 10 对有向图 G 如果以任一顶点出发进行一次深度优先或广度优先搜索能访 问到每一个顶点 则该图一定是完全图 11 连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点 12 图的深度优先搜索中一般要采用栈来暂时刚访问过的顶点 13 有向图的遍历不可采用广度优先搜索方法 14 连通图的生成树包含了图中所有顶点 15 设 G 为具有 n 个顶点的连通图 如果其中的某个子图有 n 个顶点 n 1 条 边 则该子图一定是 G 的生成树 16 最小生成树是指边数最小的生成树 17 从 n 个顶点的连通图中选取 n 1 条权值最小的边 即可构成最小生成树 18 只要无向网中没有权值相同的边 其最小生成树就是惟一的 19 只要无向网中有权值相同的边 其最小生成树就可能不是惟一的 20 有环图也能进行拓扑排序 21 拓扑排序算法仅适用于有向无环图 22 任何有向无环图的结点都可以排成拓扑排序 而且拓扑序列不惟一 23 关键路径是由权值最大的边构成的 24 在 AOE 网中 减小任一关键活动上的权值后 整个工期也就相应减小 25 在 AOE 网中工程工期为关键活动上权值之和 26 在关键路径的活动都是关键活动 而关键活动未必在关键路径上 27 关键活动不按期完成就会影响整个工程的完成时间 28 所有关键活动都提前完成 则整个工程将提前完成 29 某些关键活动若提前完成 将可能使整个工程提前完成 30 求单源最短路径的狄克斯特拉算法不适用于有回路的有向网 四 简答题四 简答题 1 图 G 是一个非连通无向图 共有 28 条边 则该图至少有多少个顶点 2 用邻接矩阵表示图时 矩阵元素的个数与顶点个数是否相关 与边的条数是 否有关 3 对于稠密图和稀疏图 就存储而言 采用邻接矩阵和邻接表哪个更好些 4 请回答下列关于图的一些问题 1 有 n 个顶点的有向强连通图最多有多少条边 最少有多少条边 2 表示一个有 1000 个顶点 1000 条边的有向图的邻接矩阵有多少个矩阵 元素 是否为稀疏矩阵 3 对于一个有向图 不用拓扑排序 如何判断图是否存在环 5 对 n 个顶点的无向图和有向图 采用邻接表表示时 如何判别下列有关问题 1 图中有多少条边 2 任意两个顶点 i 和 j 是否有边相连 3 任意一个顶点的度是多少 6 给出如图 7 4 所示的无向图 G 的邻接矩阵和邻接表两种存储结构 并在给定 的邻接表基础上 指出从顶点 1 出发的深度优先遍历和广度优先遍历序列 图 7 4 一个无向图 7 对于图 7 5 所示的有向图 试给出 1 邻接矩阵 2 邻接表 3 强连通分量 4 对照邻接表 给出从顶点 1 出发的深度优先遍历序列 5 对照邻接表 给出从顶点 3 出发的深度优先遍历序列 12 54 3 图 7 5 一个有向图 8 什么样的图其最小生成树是惟一的 9 已知带权连通图 G V E 邻接表如图 7 6 所示 请画出该图 并分别以深度优 先和广度优先遍历该图 写出遍历中结点的序列 并画出该图的一棵最小 生成树 其中表结点的 3 个域各为 1 2 3 4 5 图 7 6 连通图的邻接表 10 已知世界 6 大城市为 北京 B 纽约 N 巴黎 P 伦敦 L 东京 T 墨西哥城 M 试用由表 1 给出的交通网确定最小生成树 并说明所 使用的方法及其时间复杂度 顶点号边上所带的权指针 BNPLTM B 109828121124 N109585510832 P825839792 L815539589 T211089795113 M124329289113 14 32 5 6 v1 v2 v3 v4 v5 4 4 4 18 5 22 5 10 1 16 1 12 2 12 1 18 2 22 3 16 3 2 2 2 3 4 4 10 11 对于图 7 7 所示的带权有向图 采用狄克斯特拉算法求从顶点 1 到其它顶 点的最短路径 要求给出求解过程 图 7 7 一个有向图 图 7 8 一个有向图 12 设图 7 8 中的顶点表示村庄 有向边代表交通路线 若要建立一家医院 试问建在哪个村庄能使个村庄总体交通代价最小 13 表 2 所示给出了某工程各工序之间的优先关系和各工序所需的时间 表 2 某工程各工序关系表 工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 A B B C D B E G I E I F I H J K L G 完成如下各小题 1 画出相应的 AOE 网 2 列出事件的最早发生时间 最迟发生时间 3 找出关键路径并指明完成该工程所需的最短时间 14 如图 7 9 所示的 AOE 网 求 1 每项活动 ai最早开始时间 e ai 和最迟开始时间 l ai 2 完成此工程最少需要多少天 设边上权值为天数 3 哪些是关键活动 4 是否存在某项活动 当其提高速度后能使整个工程缩短工期 6 5 12 12 15 1313 4 4 3 1 3 2 0 4 3 9 82 2 1 2 7 1 5 3 42 a13 2 a1 5 a2 6 a3 3 a4 6 a5 3 a6 3 a7 4 a12 4 a11 2 a10 5 a9 4 a8 1 1 3 42 5 6 7 8 9 10 图 7 9 五 算法设计题五 算法设计题 1 假设图 G 采用邻接表存储 分别设计实现以下要求的算法 1 求出图 G 中每个顶点的入度 2 求出图 G 中每个顶点的出度 3 求出图 G 中出度最大的一个顶点 输出该顶点的编号 4 计算图 G 中出度为 0 的顶点数 5 判断图 G 中是否存在边 2 假设图 G 采用邻接矩阵存储 分别设计实现以下要求的算法 1 求出图 G 中每个顶点的入度 2 求出图 G 中每个顶点的出度 3 求出图 G 中出度最大的一个顶点 输出该顶点的编号 4 计算图 G 中出度为 0 的顶点数 5 判断图 G 中是否存在边 3 设计一个将邻接表转换为邻接矩阵的算法 4 一个连通图采用邻接表作为存储机构 设计一个算法实现从顶点 v 出发的深 度优先遍历的非递归过程 5 设计一个算法 求不带权无向连通图 G 中距离顶点 v 的最远顶点 6 设计一个算法 判断无向图 G 是否是一棵树 若是树 返回 1 否则返回 0 7 假设图采用邻接表存储 分别写出基于 DFS 和 BPS 遍历的算法来判别顶点 i 和顶点 j i j 之间是否有路径 8 假设图 G 采用邻接表存储 设计一个算法 判断无向图 G 是否连通 若连 通则返回 1 否则返回 0 9 假设图 G 采用邻接表存储 设计一个算法 输出图 G 中从顶点 u 到 v 的长 度为 1 的所有简单路径 10 假设图 G 采用邻接表存储 设计一个算法 输出图 G 中从顶点 u 到 v 的所 有简单路径 11 假设图 G 采用邻接表存储 设计一个算法 从如图 7 10 所示的无向图 G 中找出满足如下条件的一条路径 1 给定起点 vi 和终点 vj 2 给定一组必经点 7 9 即输出的路径必须包含这些顶点 3 给定一组必避点 1 6 即输出的路径不能包含这些顶点 图 7 10 12 假设图 G 采用邻接矩阵存储 采用遍历方法实际一个有向图的根的算法 若有向图中存在一个顶点 v 从 v 可以通过路径达达图中其它所有顶点 则称 v 为该有向图的根 13 假设图 G 采用邻接矩阵存储 设计一个算法判断在给定的有向图中是否存 在一个简单有向回路 若存在 则以顶点序列的方法输出该回路 找到一 条即可 14 采用堆排序来实现 Kruskal 算法 并说明时间复杂度 O