数据结构与算法6.docx

精品word学习资料可编辑 名师归纳总结——欢迎下载 第六次作业 一，挑选题 1，深度优先遍历类似与二叉树的 A ： A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 2 ，广度优先遍历类似与二叉树的 D ： A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 3，以下关于开放树 (Free Tree) 的说法错误选项 C ： A. 具有 n 个结点的开放树包含 n-1 条边 B. 开放树没有回路 C. 开放树可以是非连通图 D. 在开放树中任意加一条边，肯定会产生回路 4，关于最小生成树，以下说法错误选项 C ： A. 最小生成树是一棵开放树 B. 最小生成树各边的和是全部生成树中最小的 C. 任何图都只有一个最小生成树 D. 能够产生最小生成树的图，其边肯定有权值 5 ，任何一个无向 连通图的最小生成树 B ： A. 只有 1 棵 B. 1 棵或多棵 C. 肯定有多棵 D. 可能不存在 6 ，在如下图所示的图中，从顶点 a 动身，按深度优先遍历，就可能得到的一种顶点的序列为 C 和 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 7，在如上图所示的图中，从顶点 a 动身，按广度优先遍历，就可能得到的一种顶点的序列为 A ； A. a, b, e, c, d, f B. a, b, e, c, f, d C. a, e, b, c, f, d D. a, e, d, f, c, b 8 ，设网 ( 带权的图) 有 n 个顶点和 e 条边，就采纳邻接表储备时，求最小生成树的 Prim 算法的时间复杂度为 C ； 23 A. O(n) B. O(n+e) C. O(n) D. O(n) 9 ，设图有 n 个顶点和 e条边，求解最短路径的Floyd 算法的时间复杂度为 D ； 23 A. O(n) B. O(n+e) C. O(n) D. O(n) 10，最小生成树是指 C ； A. 由连通网所得到的边数最少的生成树； B. 由连通网所得到的顶点数相对较少的生成树； C. 连通网中全部生成树中权值之和为最小的生成树； D. 连通网的微小连通子图； 11，下面关于工程方案的 AOE 网的表达中， 不正确选项 B ； A. 关键活动不按期完成就会影响整个工程的完成时间； B. 任何一个关键活动提前完成，那么整个工程将会提前完成； C. 全部关键活动都提前完成，那么整个工程将会提前完成； D. 某些关键工程如提前完成，那么整个工程将会提前完成； 12，在 AOE 网中，始点和汇点的个数为 D ； A. 1 个始点，如干个汇点 B. 如干个始点，如干个汇点 C. 如干个始点， 1 个汇点 D. 1 个始点， 1 个汇点 13，在下图所示的无向图中，从顶点 v1 开头采纳 Prim 算法生成最小生成树，算法过程中 产生的顶点次序为 B ； A. v1, v3, v4, v2, v5, v6 B. v1, v3, v6, v2, v5, v4 C. v1, v2, v3, v4, v5, v6 D. v1, v3, v6, v4, v2, v5 14，在 精品word学习资料可编辑 名师归纳总结——欢迎下载 上图所示的途中，采纳 Cruskal 算法生成最小生成树，过程中产生 的边的次序是 C ； A. (v1, v2), (v2, v3), (v5, v6), (v1, v5) B. (v1, v3), (v2, v6), (v2, v5), (v1, v4) C. (v1, v3), (v2, v5), (v3, v6), (v4, v5) D. 精品word学习资料可编辑 名师归纳总结——欢迎下载 (v2, v5), (v1, v3), (v5, v6), (v4, v5) 1，5 拓扑排序的结果是 A ； A. 如下图所示的图中，其中一个 精品word学习资料可编辑 名师归纳总结——欢迎下载 v1 → v2 → v3 → v6 → v4 → v5 → v7 → v8 B. v1 → v2 → v3 → v4 → v5 → v6 → v7 → v8 C. v1 → v6 → v4 → v5 → v2 → v3 → v7 → v8 D. v1 → v6 → v2 → v3 → v7 → v8 → v4 → v5 16，在下图所示的 AOE 网中，活动 a9的最早开头时间为 B ； A. 13 B. 14 C. 15 D. 16 17，在上图所示的 AOE 网 中，活动 a4 的最迟开头时间为 D A. 4 B. 5 C. 6 D. 7 二，