图的练习-word资料(精).doc

图的练****一、判断 1、(√)带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。 2、(√) AOE 网是一种带权的无环连通图。 3、(√)强连通图的各顶点间均可达。 4、(√) 用邻接矩阵法存储一个图时, 在不考虑压缩存储的情况下, 所占用的存储空间大小只与图中结点个数有关,而与图的边数无关。 5、(× )带权无向图的最小生成树是唯一的。 6、(√)图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被访问过。 7、(√) 任何无环的有向图, 其结点都可以排在一个拓扑序列里。 8、(√)任何一个关键活动延迟,那么整个工程将会延迟。 9、(× )任何一个关键活动提前完成,那么整个工程将会提前完成。 10、(× )对任意一个图,从它的某个顶点出发,进行一次深度优先或广度优先遍历搜索,即可访问图的每个顶点。二、填空 1、 Prim 算法生成一个最小生成树每一步选择都要满足边的总数不超过 n-1 , 当前选择的边的权值是候选边中最小的, 选中的边加入树中不产生回路三项原则。 2、 Kurskal 算法的时间复杂度 O( eloge ),对稀疏图较为适合。 3、 Prim 算法的时间复杂度 O(n 2),对稠密图较为适合。 4、 AOV 网络中, 顶点表示活动, 边表示活动间的优先顺序, AOE 网络中,顶点表示事件,边表示活动。 5 、设有向图 G 中有 n 个顶点 e 条有向边,所有的顶点入度数之和为 d ,则 e和d 的关系为 d=e 。 6 、已知图 G 的邻接表如图所示,其从顶点 v1 出发的深度优先搜索序列为 v1v2v3v6v5v4 , 其从顶点 v1 出发的广度优先搜索序列为 v1v2v5v4v3v6 。 7、设无向图 G 中有 n 个顶点 e 条边,则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为 O(n 2); 用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为O( n+e )。 8 、设有向图 G 的存储结构用邻接矩阵 A 来表示,则 A 中第 i 行中所有非零元素个数之和等于顶点 i的出度,第i 列中所有非零元素个数之和等于顶点 i的入度。 9 、设无向图 G 中有 n 个顶点和 e 条边,则其对应的邻接表中有个表头结点和 2e 个边结点。 10 、拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。三、选择 1 、设某无向图中有 n 个顶点 e 条边,则建立该图邻接表的时间复杂度为( )。 A、 O(n+e) B、 O(n 2)C、 O(ne) D、 O(n 3)A 2 、设用邻接矩阵 A 表示有向图 G 的存储结构,则有向图 G 中顶点 i 的入度为( )。 A 、第 i 行非 0 元素的个数之和 B 、第 i 列非 0 元素的个数之和 C 、第 i行0 元素的个数之和 D 、第 i列0 元素的个数之和 B 3 、设某无向图有 n 个顶点,则该无向图的邻接表中有( )个表头结点。 A、 2nB、nC、 n/2 D、 n(n-1)B 4 、设无向图 G 中有 n 个顶点,则该无向图的最小生成树上有( )条边。 A、nB、 n-1 C、 2nD、 2n-1B 5 、设无向图 G 中有 n 个顶点 e 条边,则其对应的邻接表中的表头结点和表结点的个数分别为(