南工大第四章 图(35 页)Good is good, but better carries it.精益求精，善益求善。数据结构与算法上机作业 第四章 图一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。A. 1/2B. 1C. 2D. 42、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 B 倍。A. 1/2B. 1C. 2D. 43、G 是一个非连通无向图，共有 28 条边，则该图至少有 D 个顶点。A. 6B. 7C. 8D. 94、有 n 个顶点的图的邻接矩阵使用 B 数组存储的。A. 一维B. n 行 n 列C. 任意行 n 列D. n 行任意列5、对于一个具有 n 个顶点和 e 条边的无向图，采纳邻接表表示，则表头数组大小至少为（假设下标为 0 的数组参加使用） A 。A. n-1B. n+1C. nD. n+e6、下列说法正确的是 C 。A. 有向图的邻接矩阵一定是不对称的B. 有向图的邻接矩阵一定是对称的C. 无向图的邻接矩阵一定是对称的D. 无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的 A ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历8、广度优先遍历类似与二叉树的 D ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历9、下列关于开放树(Free Tree)的说法错误的是 C ： A. 具有 n 个结点的开放树包含 n-1 条边 B. 开放树没有回路 C. 开放树可以是非连通图 D. 在开放树中任意加一条边，一定会产生回路10、在如下图所示的图中，从顶点 a 出发，按深度优先遍历，则可能得到的一种顶点的序列为 。 A. a, b, e, c, d, fB. a, c, f, e, b, d C. a, e, b, c, f, dD. a, e, d, f, c, b11、在如上图所示的图中，从顶点 a 出发，按广度优先遍历，则可能得到的一种顶点的序列为 。A. a, b, e, c, d, fB. a, b, e, c, f, dC. a, e, b, c, f, dD. a, e, d, f, c, b12、设网(带权的图)有 n 个顶点和 e 条边，则采纳邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为 C 。A. O(n)B. O(n+e)C. O(n2)D. O(n3)13、设图有 n 个顶点和 e 条边，求解最短路径的 Floyd 算法的时间复杂度为 O 。A. O(n)B. O(n+e)C. O(n2)D. O(n3)14、最小生成树是指 C 。A. 由连通网所得到的边数最少的生成树。B. 由连通网所得到的顶点数相对较少的生成树。C. 连通网中所有生成树中权值之和为最小的生成树。D. 连通网的微小连通子图。15、下面关于工程计...
