图的练习(anwser).doc

图的练习一、判断1、（ ）带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。2、（ ）AOE网是一种带权的无环连通图。3、（ ）强连通图的各顶点间均可达。4、( )用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。5、（ ）带权无向图的最小生成树是唯一的。6、（ ）图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。 7、（ ）任何无环的有向图，其结点都可以排在一个拓扑序列里。8、（ ）任何一个关键活动延迟，那么整个工程将会延迟。9、（ ）任何一个关键活动提前完成，那么整个工程将会提前完成。10、（ ）对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先遍历搜索，即可访问图的每个顶点。二、填空1、Prim 算法生成一个最小生成树每一步选择都要满足 边的总数不超过n-1 ， 当前选择的边的权值是候选边中最小的 ， 选中的边加入树中不产生回路 三项原则。2、Kurskal算法的时间复杂度 O（n+e） ,对 稀疏 图较为适合。3、Prim算法的时间复杂度 O（n2） ,对 稠密 图较为适合。4、AOV网络中，顶点表示 活动 ，边表示 活动间的优先顺序 ，AOE网络中，顶点表示 事件 ，边表示 活动 。5、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为 d=e 。6、已知图G 的邻接表如图所示，其从顶点v1 出发的深度优先搜索序列为 v1v2v3v6v5v4 ， 其从顶点v1 出发的广度优先搜索序列为 v1v2v5v4v3v6 。7、设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为 O（n2） ；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为 O（n+e）。8、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的 出度 ，第i列中所有非零元素个数之和等于顶点i的 入度 。9、设无向图G中有n个顶点和e条边，则其对应的邻接表中有 个表头结点和 2e 个边结点。10、拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。三、选择1、设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ A ）。A、 O(n+e)B、O(n2)C、O(ne)D、O(n3)2、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B）。A、第i行非0元素的个数之和B、第i列非0元素的个数之和C、第i行0元素的个数之和D、第i列0元素的个数之和3、设某无向图有n个顶点，则该无向图的邻接表中有（ B ）个表头结点。A、2n B、nC、n/2D、n(n-1)4、设无向图G中有n个顶点，则该无向图的最小生成树上有（ B ）条边。A、nB、n-1C、2nD、2n-15、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。A、n，eB、e，nC、2n，eD、n，2e6、设某强连通图中有n个顶点，则该强连通图中至少有（ C ）条边。A、n(n-1)B、n+1C、nD、n(n+1)7、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ C ）倍。A、1/2 B、 2 C、 1 D、 4 8、有8个结点的无向图最多有（ A ）条边。A、28 B、14 C、56 D、112 9、关键路径AOE网络中（ A ）A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路10、已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（ D ）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（ B ）。 Aa，b，e，c，d，f Ba，c，f，e，b，d Ca，e，b，c，f，d， Da，e，d，f，c，b Aa，b，c，e，d，f Ba，b，c，e，f，d Ca，e，b，c，f，d， Da，c，f，d，e，b11、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ A ）。 A先序遍历 B中序遍历 C后序遍历 D按层遍历 12、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。 A先序遍历B中序遍历 C后序遍历 D按层遍历 13、AOV网是一种（D）。 A有向图 B无向图 C无向无环图 D有向无环图14、如果从一个无向图的任意顶点出发进行一次深度优先搜索遍历即可访问所有顶点，则该图一定是（ B ）A、完全图 B、连通图 C、有回路 D、一棵树15、在邻接表表示图时，拓扑排序算法的时间复杂度是（B ）A、O（n） B、O（n+e）C、O（n2）D、O（n3）四、应用1、给出如图所示的无向图G 的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1 出发的深度优先遍历和广度优先遍历序列。2、根据所给有向图，写出一个拓扑序列。0214365132547685153101227963、 分别用prim算法、kruskal算法将给定的图简化为最小的生成树，要求从顶点1出发。 4、使用普里姆算法构造出如图所示的图G 的一棵最小生成树。 5、使用克鲁斯卡尔算法构造出如图所示的图G 的一棵最小生成树。6、应用迪杰斯特拉算法，求从A开始到各点的最短路径，要求写出具体的执行过程。f81041569435212abdcge7、试对下图所示的AOE网络(1) 这个工程最早可