数据结构课后习题(第7章)

计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 1 页 共 11 页 课后习题课后习题 第第 7 7 章章 图图 2011 级 班 学号 姓名 A 题 号一二三四五总分 得 分 一 判断题 如果正确 在对应位置写 T T 否则写 F F 每题 0 5 分 共 5 分 12345678910 1 图 G 由两个集合 V G 和 E G 所组成 其中顶点集 V G 不能为空集 而边 集 E G 可以为空集 2 一般情况下 对于稠密图 G 采用邻接表存储比采用邻接矩阵存储节省省空间 3 生成树是一个连通图的极小连通子图 它含有图中全部 n 个顶点 但只有 n 1 条边 4 从不同顶点出发进行 DFS 或 BFS 得到的生成树不同 即 图的生成树不惟一 但 具有 n 的结点 n 1 条边的连通图其生成树是唯一的 5 求最小生成树的算法有 Prim 普里姆 算法和 Dijkstra 迪杰斯特拉算法 6 关键活动 指的是 该弧上的权值增加 将使有向图上的最长路径的长度增加 7 整个工程完成的时间为 从有向图的源点到汇点的最短路径长度 8 有 n 个顶点的无向连通图至少有 n 1 条边 有 n 个顶点的强连通图至少有 n 条边 9 若用有向图表示一个工程 在图中用顶点表示活动 用弧表示活动间的优先关系 则 这样的有向图叫做用顶点表示活动的网络 简称 AOV 网 10 十字链表是无向图的另一种链式结构 二 单项选择 请将正确答案的代号填写在下表对应题号下面 每题 1 分 共 30 分 题号 123456789101112131415 答案 题号 161718192021222324252627282930 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 2 页 共 11 页 答案 1 在一个图中 所有顶点的度数之和等于图的边数的 倍 A 1 2 B 1 C 2 D 4 2 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 倍 A 1 2 B 1 C 2 D 4 3 若用邻接矩阵表示一个有向图 则其中每一列包含的 1 的个数为 A 图中每个顶点的入度 B 图中每个顶点的出度 C 图中弧的条数 D 图中连通分量的数目 4 图的邻接矩阵表示法适用于表示 A 无向图 B 有向图 C 稠密图 D 稀疏图 5 任何一个无向连通图的最小生成树 A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在 6 一个有 n 个顶点的无向图最多有 条边 A n B n n 1 C n n 1 2 D 2n 7 具有 4 个顶点的有向完全图有 条边 A 6 B 12 C 16 D 20 8 n 个顶点 e 条边的带权无向连通图的最小生成树包含 个顶点 A n 1 B n C n 2 D n 1 9 在一个具有 n 个顶点的无向图中 要连通全部顶点至少需要 条边 A n B n 1 C n 1 D n 2 10 对于一个具有 n 个顶点 e 条边的无向图 若采用邻接矩阵表示 则该矩阵的大小是 A n B n e C n e D n n 11 对于一个具有 n 个顶点 e 条边的无向图 若采用邻接表表示 则该邻接表包含 个边结点 A e B 2e C n e D n2 12 已知一有向图的邻接表存储结构如图 2 所示 根 据有向图的深度优先遍历算法 从顶点 v1 出发 所 得到的顶点序列是 A v1 v2 v3 v5 v4 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 3 页 共 11 页 a6 1 V5 V4 V1 V2 V6 V3 a8 5 a2 10 a1 3 a5 1 a4 20 a7 7 a3 18 图 4 B v1 v2 v3 v4 v5 C v1 v3 v4 v5 v2 D v1 v4 v3 v5 v2 13 已知一有向图的邻接表存储结构如图 2 所示 根据有向图的广度优先遍历算法 从 顶点 v1 出发 所得到的顶点序列是 A v1 v2 v3 v4 v5 B v1 v3 v2 v4 v5 C v1 v2 v3 v5 v4 D v1 v4 v3 v5 v2 14 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 15 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 16 关键路径是 AOE 网络中 A 从源点到汇点的最长路径 B 从源点到汇点的最短路径 C 最长的回路 D 最短的回路 17 对于一个有向图 若一个顶点的入度为 k1 出度为 k2 则对应邻接表中该顶点单 链表中的结点数为 A k1 B k2 C k1 k2 D k1 k2 18 对于一个有向图 若一个顶点的入度为 k1 出度为 k2 则对应逆邻接表中该顶点 单链表中的结点数为 A k1 B k2 C k1 k2 D k1 k2 19 在图 3 所示的拓朴排列的结果序列为 A 125634 B 516234 C 123456 D 521634 20 一个有 n 个顶点的无向连通图 它所包含的连通分量个数为 A 0 B 1 C n D n 1 21 判定一个有向图是否存在回路除了可以利用拓扑排序方法外 还可以利用 A 求关键路径的方法 B 求最短路径的 Dijkstra 方法 C 广度优先遍历算法 D 深度优 先遍历算法 22 如果图 4 是一交通图 其中 Vi 表示城市 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 4 页 共 11 页 ai表示城市之间交通费用 则从 V1 到 V4 中转站最少的路径可为 A V1V2V4 B V1V2V5V6V4 C V1V3V5V6V4 D V1V5V6V4 23 如果图 4 当做一交通图 Vi 表示城市 ai表示城市之间交通费用 则 V1 到 V4 交通 费用最省路径可为 A V1V2V4 B V1V2V5V6V4 C V1V3V5V6V4 D V1V5V6V4 24 如果图 4 是一 AOE 网 其一关键路径为 A V1V2V4 B V1V2V5V6V4 C V1V3V5V6V4 D V1V5V6V4 25 求关键路径的算法中 关键活动是指最早发生时间 最迟发生时间的活动 A 等于 B 大于 C 小于 D 不确定 26 已知一个图右如下所示 从顶点 a 出发进行广度优先 遍历可能得到的序列为 A a c e f b dB a c b d f e C a c b d e fD a c d b f e 27 给定下面有向图 题 27 从顶点 1 出发 其深度优先搜索序列为 A 12534 B 12435 C 14325 D 12345 28 对于上图所示的 AOV 网 题 28 不能出现的拓扑序列为 A 2 4 1 3 5 B 1 2 4 3 5 C 1 2 3 4 5 D 2 1 4 3 5 29 已知一个有向图如右所示 则从顶点 出发能得到拓朴序列为 A B C D 30 下列为顶点表示活动的有向图如下图所示 其有向边表示活动之间发生的先后顺序 则其拓朴序列为 题 27 1 5 4 3 2 1 3 5 4 2 题 28 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 5 页 共 11 页 A FBCAED B FBCEDA C BCAFED D BFCAED 二 填空题 每空 1 分 共 40 分 1 若 u v 是 E G 中的一条边 则称 u 与 v 互为 2 带权图的路径长度是指路径上 3 图的存储结构主要有 十字链表 邻接多重表 对于一个确定的图 其 是唯一的 不惟一 因各个边 结点的链入顺序是任意 4 邻接矩阵的空间复杂度为 而邻接表的空间复杂度为 邻接矩阵多用于 的存储 邻接表多用于 的存储 5 深度优先搜索是模仿树的 过程 算法是递归的 广度优先搜索是一种 分层的搜索过程 是模仿树的 过程 算法是 的 6 Prime 算法特点 将顶点归并 与边数无关 适于求 的最小生成树 Kruskal 算法特点 将边归并 适于求 的最小生成树 7 若从一个连通图中删去任何一个顶点及其相关联的边 它仍为一个连通图的话 则 该连通图被称为 8 若连通图中的某个顶点和其相关联的边被删去之后 该连通图被分割成两个或两个 以上的连通分量 则称此顶点为 没有 的连通图为双连通图 E A B C D F 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 6 页 共 11 页 9 求单源最短路径 用 算法 求所有顶点间的最短路径 用 算法 10 在带权有向无环网中 用有向边表示一个工程中的活动 用边上权值表示活动持续 时间 用顶点表示事件 则这样的有向图叫做 的网络 简称 网 常用于大型工程的计划管理 11 构造 AOV 网络全部顶点的拓扑有序序列的运算就叫做 它是判断图中 是否存在有向环的方法之一 该算法是通过重复选择具有 个前驱的顶点的 过程来完成的 12 如果 n 个顶点的图是一个环 则它有 棵不同的生成树 13 图的邻接表存储结构又叫出边表 图的 存储结构又叫入边表 入边表 只适用于存储 图 14 若要求一个稠密图 G 的最小生成树 最好用 算法来求解 15 n 个顶点无向图至少有 条边 至多有 条边 含 n 个 顶点的无向连通图中至少含有 条边 16 在无向图 G 的邻接矩阵 A 中 若 A i j 等于 1 则 A j i 等于 17 已知图 G 的邻接表如图 4 所示 从顶点 v1 出 发的深度有限搜索序列为 其从顶点 v1 出发的广度优先搜索序列为 18 在如下图所示的网络计划图中关键路径是 全部计划完成的时间 是 5 4 6 8 2 3 9 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 7 页 共 11 页 7 11 4 6 8 19 从邻接矩阵 A 可以看出 如果是无向图该图共有 条边 如果是 0011 0010 1101 1010 有向图 该图共有 条边 20 在有向图中 以顶点 v 为弧头的边的数目称为 v 的 以顶点 v 为弧尾 的边的数目称为 v 的 四 简答题 10 分 1 设带权图 即网 N V E 是连通的 其中 V 为顶点集 E 为带权边集 再设 TE 是最小生成树边的集合 已知求 TE 时是从和 TE 出发 00 VuuU 其中 通过不断从 U 和 V U 之间查找最小代价边加入 TE 中直到 U V 为止而实现的 请问对 求最小生成树算法进行简要描述 并说出这种算法的名称 4 分 算法的名称 算法 算法简要描述 令 TE 00 VuuU 其中 如果则执行 步 否则执行 步 VU 转到 步执行 结束且返回 TE 2 简要描述 Kruskal 克鲁斯卡尔 算法 3 分 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 8 页 共 11 页 3 简要描述拓扑排序的算法及其用途 3 分 五 应用题 15 分 1 4 分 求出下图从顶点 a 到其余各顶点之间的最短路径 最短路径最短路径长度 a b a c a c3 a d a e a f 2 4 分 已知如图所示的有向图 请给出该图的 1 邻接矩阵 2 邻接表 3 逆邻接表 4 每个顶点的入 出度 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 9 页 共 11 页 邻接矩阵 2 邻接表 3 逆邻接表 4 每个顶点的入 出度 顶点ABCDEF 出度221201 入度021131 3 3 分 1 下图中从源点 V3 到汇点 V6 的关键路径是 关键路 径的长度为 关键活动是 B C E F AD 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 10 页 共 11 页 v3 v6 v7 v4 v1 v8 v5 v2 a1 6 a6 3 a4 4 a2 7 a3 5 a9 5 a5 2a10 2 a8 7 a7 9a12 5 a11 6 a13 9 计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 1