第7章 图.ppt

《第7章 图.ppt》由会员分享，可在线阅读，更多相关《第7章 图.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 图图一、判一、判 断断 题题 1、在、在n个结点的无向图中，若边数大于个结点的无向图中，若边数大于n-1,则该则该图必是连通图。（）图必是连通图。（）2、若一个有向图的邻接矩阵对角线以下元素均、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）为零，则该图的拓扑有序序列必定存在。（）1、（、（）2、（、（）1、强连通分量是无向图的极大强连通子图。、强连通分量是无向图的极大强连通子图。2、连通分量指的是有向图中的极大连通子图。、连通分量指的是有向图中的极大连通子图。（）（）1、（、（）2、（、（）1、有、有n个顶点的无向图个顶点的无向图,采用邻接矩阵表示采

2、用邻接矩阵表示,图中的图中的边数等于邻接矩阵中非零元素之和的一半。边数等于邻接矩阵中非零元素之和的一半。2、无向图的邻接矩阵一定是对称矩阵，有向图的邻、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。接矩阵一定是非对称矩阵。1、（、（）2、（、（）1、连通图上各边权值均不相同，则该图的最、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）小生成树是唯一的。（）2、带权的连通无向图的最小生成树是唯一的。、带权的连通无向图的最小生成树是唯一的。（）（）1、（、（）2、（、（）1、AOE网一定是有向无环图。（）网一定是有向无环图。（）2、任何任何AOE网拓扑排序的结果都是唯

3、一的。网拓扑排序的结果都是唯一的。（）（）1、（、（）2、（、（）1、用、用DFS遍历一个无环有向图，并在遍历一个无环有向图，并在DFS算算法退栈返回时打印相应的顶点，则输出的法退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序。（）顶点序列是逆拓扑有序。（）1、（、（）二、选择题二、选择题1、一个一个n个顶点的连通无向图，其边的个数至个顶点的连通无向图，其边的个数至少为（少为（）。）。An+1 Bn Cn-1 Dnlogn；答案：答案：C 2、n个结点的有向完全图含有边的数目（）。个结点的有向完全图含有边的数目（）。An*n n*（n）Cn2 Dn*（nl）答案：答案：D 3、用、用DF

4、S遍历一个无环有向图，并在遍历一个无环有向图，并在DFS算法退算法退栈返回时打印相应的顶点，则输出的顶点序列是栈返回时打印相应的顶点，则输出的顶点序列是 A 逆拓扑有序逆拓扑有序 B 拓扑有序拓扑有序 C 无序的无序的 答案：答案：A4、下列哪一种图的邻接矩阵是对称矩阵？（、下列哪一种图的邻接矩阵是对称矩阵？（）A有向图有向图 B无向图无向图 CAOV网网 DAOE网网答案：答案：B5、下列说法不正确的是（、下列说法不正确的是（）。）。A图的遍历是从给定的源点出发每一个顶点仅被访图的遍历是从给定的源点出发每一个顶点仅被访问一次问一次 B图的深度遍历不适用于有向图图的深度遍历不适用于有向图C遍历

5、的基本算法有两种：深度遍历和广度遍历遍历的基本算法有两种：深度遍历和广度遍历 D图的深度遍历是一个递归过程图的深度遍历是一个递归过程答案：答案：B 6、下面哪一方法可以判断出一个有向图是否有环、下面哪一方法可以判断出一个有向图是否有环（回路）：（回路）：A深度优先遍历深度优先遍历 B.拓扑排序拓扑排序 C.求最短路径求最短路径 D.求关键路径求关键路径答案：答案：AB7、在图采用邻接表存储时，求最小生成树的在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)答案：答案：C8、在有向图、在有向图G的拓扑

6、序列中，若顶点的拓扑序列中，若顶点Vi在顶点在顶点Vj之前，之前，则下列情形不可能出现的是（则下列情形不可能出现的是（）。）。AG中有弧中有弧 BG中有一条从中有一条从Vi到到Vj的路径的路径 CG中没有弧中没有弧 DG中有一条从中有一条从Vj到到Vi的路径的路径 答案：答案：D9、关键路径是事件结点网络中（关键路径是事件结点网络中（）。）。A从源点到汇点的最长路径从源点到汇点的最长路径 B从源点到汇点的最短路径从源点到汇点的最短路径 C最长回路最长回路 D最短回路最短回路答案：答案：A10、下列关于下列关于AOE网的叙述中，不正确的是（网的叙述中，不正确的是（）。）。A关键活动不按期完成就会

7、影响整个工程的完成时间关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成某些关键活动提前完成，那么整个工程将会提前完成答案：答案：B三、应用题三、应用题1、图的存储结构、图的存储结构v邻接表邻接表P164v十字链表十字链表P1652、图的遍历、图的遍历v深度优先搜索深度优先搜索v广度优先搜索广度优先搜索3、最小生成树、最小生成树P174P1744、关键路径、关键路径P186P1865、最短路径、最短路径P190P190