《2023年图习题及标准超详细解析超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年图习题及标准超详细解析超详细解析答案.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图习题及标准答案 2 作者：日期：中的极大连通子图有向图中的极小连通子图有向图中的极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏 3 第 7 章 图 一、选择题 1对于一个具有 n 个顶点和 e 条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B 2设无向图的顶点个数为 n，则该图最多有（）条边。A）
2、n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2【答案】B 3连通分量指的是（）A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图【答案】B 4n 个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D 5关键路径是（）A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径【答案】A 6有向图中一个顶点的度是该顶点的（）A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2
3、【答案】C 7有 e 条边的无向图，若用邻接表存储，表中有（）边结点。A）e B）2e C）e-1 D）2(e-1)中的极大连通子图有向图中的极小连通子图有向图中的极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏 4【答案】B 8实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】B 9实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）
4、栈 B）队列 C）二叉树 D）树【答案】A 10存储无向图的邻接矩阵一定是一个（）A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C 11在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A）1/2 B）1 C）2 D）4【答案】B 12 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A）O(n)B）O(n+e)C）O(n2)D）O(n3)【答案】B 13下列关于 AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完
5、成 D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B 14具有 10 个顶点的无向图至少有多少条边才能保证连通（）A）9 B）10 C）11 D）12【答案】A 15在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为（）A）e B）2e C）n2-e D）n2-2e【答案】D 16.对于一个具有 n 个顶点和 e 条边的无向图，如果采用邻接表来表示，则其表中的极大连通子图有向图中的极小连通子图有向图中的极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜
6、索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏 5 头向量的大小为 。A、n B、n+1 C、n-1 D、n+e 【答案】A 二、填空题 1无向图中所有顶点的度数之和等于所有边数的_倍。【答案】2 2 具有 n 个顶点的无向完全图中包含有_条边，具有 n 个顶点的有向完全图中包含有_条边。【答案】（1）n(n-1)/2 （2）n(n-1)3一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要_条边。【答案】n-1 5对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_。【答案】（1）O(n2
7、)（2）O(n+e)6对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_和_条。【答案】（1）e （2）2e 7 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_和_结点。【答案】（1）出边 （2）入边 8 对于一个具有 n 个顶点和 e 条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_和_。【答案】（1）O(n)（2）O(e)9对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为_和_。【答案】（1）n （2）n-1 中的极大连通子图有向图中的极小连通子图有向图中的
8、极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏 6 10Prim 算法和 Kruscal 算法的时间复杂度分别为_和_。【答案】（1）O(n2)（2）O(eloge)11.假设图 G中含有 n 个顶点，e 条边，且知每个顶点的度数为 di，则它们三者之间满足的关系为：。【答案】e=1/2di 12.我们把图中所有顶点加上遍历时经过的所有边构成的子图称为 。【答案】生成树 13、有 n
9、个顶点的无向图，其边数最大可达 ，像这样的有最大边数的无向图通常被称为 。【答案】n(n-1)/2 完全无向图 14、树被定义为连通而不具有 的（无向）图。【答案】回路 15、对于一个图 G的遍历，通常有两种方法，它们分别是 和 。【答案】深度优先法 广度优先法 16.AOV 网中，结点表示活动 ，边表示活动的先后顺序 ，AOE网中，结点表示事件 ，边表示活动 .7-16 试对右图所示的 AOE 网络，解答下列问题。(1)这个工程最早可能在什么时间结束。(2)求每个事件的最早开始时间Vei和最迟开始时间 VlI。(3)求每个活动的最早开始时间 e()和最迟开始时间 l()。(4)确定哪些活动是
10、关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl。然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间 l，根据 l-e=0?来确定关键活动，从而确定关键路径。1 2 3 4 5 6 Ve 0 19 15 29 38 43 中的极大连通子图有向图中的极小连通子图有向图中的极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏 7 Vl 0 19 15 37 38 43 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为 中的极大连通子图有向图中的极小连通子图有向图中的极大连通子图答案个结点的完全有向图含有边的数目答案关键点的最短路径答案有向图中一个顶点的度是该顶点的入度出度入度与出度之和入度出度答案有条边的无向图若用邻接归深度优先搜索算法需使用的辅助数据结构为栈队列二叉树树答案存储无向图的邻接矩阵一定是一个上三角矩阵稀疏