第七章 图 复习题及答案.docx

本文格式为Word版，下载可任意编辑第七章 图 复习题及答案 第七章 图 复习题及答案 一、选择题 1.在一个图中，全体顶点的度数之和等于全体边的数目的_______倍 A．1/2 B．1 C．2 D．4 2在一个有向图中，全体顶点的入度之和等于全体顶点的出度之和的_______倍 A．1/2 B．1 C．2 D．4 6．具有6个顶点的无向图至少理应有_______条边才能保证是一个连通图 A．4 B．5 C．6 D．7 7. 一个无向图采用邻接矩阵存储方法，其邻接矩阵确定是一个_______ A．对称矩阵 B．对角矩阵 C．三角矩阵 D．稀疏矩阵 8．若具有n个顶点的无向图采用邻接矩阵存储方法，那么邻接矩阵的大小为________ 9．具有n个顶点、e条边的无向图采用邻接表存储方法，该邻接表中一共有________个边结点 A．n B．2n C．e D．2e l0．图的深度优先探寻算法类似于二叉树的——。

八．先序遍历 B．中序遍历 C．后序遍历 D．按层次遍历 11．图的广度优先探寻算法类似于二叉树的—— A．先序遍历 B．中序遍历 C．后序遍历 D．按层次遍历 12．导致图的遍历序列不惟一的因素是———— A．启程点的不同、遍历方法的不同 B．启程点的不同、存储布局的不同 c．遍历方法的不同、存储布局的不同 D．启程点的不同、存储布局的不同、遍历方法的不同 13．任何一个带权无向连通图的最小生成树—— A．是惟一的 ， B．是不惟一的 C．有可能不惟一 D．有可能不存在 16．判定一个有向图中是否存在回路可以利用——方法 A．求最小生成树 B．求最短路径 C．拓扑排序 D．图的遍历 17．判定一个有向图中是否存在回路除了利用拓扑排序方法以外，还可以利用 ——方法 A.图的遍历 B．求最小生成树 c．最短路径 D．求关键路径 19．下面的说法中，不正确的是—— A．AOE网是一个带权的有向图 B AOE网是一个带权且无环路的有向图 C．AOE网是一个带权且无环路的有向连通图 D正常处境下，AOE网中只有一个源点和一个终点 20．AOE网中的关键路径是该网中的——。

A．从源点到终点的最长路径 B．从源点到终点的最短路径 c．最长的回路 D．最短的回路 A．带权连通图的某最小生成树的权值之和确定小于其他生成树的权值之和 B从源点到终点的最短路径是惟一的 C．任意一个AOV网不确定存在拓扑序列 D．任意一个AOE网中的关键路径是惟一的 答案： 1． 选择C ；2．选择B，结论是鲜明的；3．选择D；4．选择A； 6．选择B 由生成树的定义可知，具有6个顶点的无向图至少理应具有5条边才能保证该无向 图是一个连通图，故此题选择B 7．选择A 若无向图采用邻接矩阵存储方法，那么其邻接矩阵确定是一个对称矩阵 8．选择D 具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个n阶方阵，具有 n2个矩阵元素，因此，此题选择D 9．选择D 若具有n个顶点、e条边的无向图采用邻接表存储方法，该邻接表由n个链表组成，n个链表中一共有2e个边结点，因此，此题选择D 10．选择A 由图的深度优失探寻方法的过程不难看到图的深度优先探寻类似于二叉树的前序遍历过程，应选择A。

11．选择D 由图的广度优先探寻方法的过程不难看到图的广度优先探寻类似于二叉树的按层次遍历过程，应选择D 12．选择D 导致对一个图举行遍历而得到的遍历序列不惟一的因素有大量，首先，遍历的启程顶点选择得不惟一，得到的遍历序列鲜明不是惟一的即使遍历的启程顶点一致，采用的遍历方法若不一致，那么得到的结果也是不一致的另外，即使遍历的启程顶点一致，并且采用同一种遍历方法，若图的存储布局不一致，那么得到的结果也可能是不一致的 例如，对于邻接表布局而言，建立邻接表时供给边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表布局会导致不同的遍历结果因此，此题理应选择D 13．选择C 一般处境下，带权连通图的最小生成树不确定是惟一的 14．选择Co 由求解带权连通图的最小生成树的方法可以得到结论 15．选择Bo 由求解最短路径的迪杰斯特拉(Dijstra)方法可以得到结论 16．选择C 拓扑排序方法可以判定一个有向图中是否存在回路 17．选择Do 除了采用拓扑排序方法判定一个有向图中是否存在回路之外，求关键路径的过程也可以判定一个有向图中是否存在回路。

18．选择A 按照拓扑排序方法对该图举行拓扑排序便可得到结果 19．选择C9 说法A，B和D是正确的，只有C是错误的 有向图，但它不是连通图，应选择co 20．选择A 由AOE网的关键路径的定义可以得到结论 21．选择C 求出该AOE网的关键路径便可以得到结论 22．选择C 由于带权连通图的某最小生成树的权值之和不确定小于其他生成树的权值之和；对 于一个图而言，从源点到终点的最短路径也不确定是惟一的；任意一个AOE网中的关 键路径也不确定惟一，因此，只有说法c是错误的确实，任意一个Aov网不确定存 在拓扑序列 二、综合题 10. 试对右图所示的AOE网络，解答以下问题 (1) 这个工程最早可能在什么时间终止 (2) 求每个事情的最早开头时间Ve[i]和最迟开头时间Vl[I] (3) 求每个活动的最早开头时间e( )和最迟开头时间l( ) (4) 确定哪些活动是关键活动画出由全体关键活动构成的图，指出哪些活动加速可使整个工程提前完成。

【解答】 按拓扑有序的依次计算各个顶点的最早可能开头时间Ve和最迟允许开头时间Vl然后再计算各个活动的最早可能开头时间e和最迟允许开头时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径 1 ? Ve 0 Vl 0 0 17 17 2 ? 19 19 0 0 0 3 ? 15 15 15 15 0 4 ? 29 37 19 27 8 5 ? 38 38 19 19 0 6 ? 43 43 15 27 12 29 37 8 38 38 0 e l l-e 此工程最早完成时间为43关键路径为 三、算法设计 见图测验要求，图的存储布局建立及遍历算法是重点 — 7 —。