第7章图

第7章图7.1选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。A）n-1B）n(n-1)/2C）n(n+1)/2D）n2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*nB）n（n+1）C）n/2D）n*（n-1）【答案】D5．关键路径是（）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度B）出度C）入度与出度之和D）（入度+出度）/2【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。A）eB）2eC）e-1D）2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）1/2B）1C）2D）4【答案】B12．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）A）O(n)B）O(n+e)C）O(n2)D）O(n3)【答案】B13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（）A）9B）10C）11D）12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A）eB）2eC）n2-eD）n2-2e【答案】D7.2填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。【答案】22．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。【答案】（1）n(n-1)/2（2）n(n-1)3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。【答案】n-14．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为_____________和_____________。【答案】（1）O(n2)（2）O(n+e)5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。【答案】（1）O(n2)（2）O(e)6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。【答案】（1）e（2）2e7．在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。【答案】（1）出边（2）入边8．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。【答案】（1）O(n)（2）O(e+n)9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。【答案】（1）n（2）n-110．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。【答案】（1）O(n2)（2）O(eloge)11．针对下图所示的连通网络，试按如下格式给出在Kruscal算法构造最小生成树过程中顺序选出的各条边。【答案】设边的信息表示为（始点，终点，权值），则在Kruscal算法构造最小生成树过程中顺序选出的各条边为：（3，5，1），（2，4，2），（1，5，3），（1，2，3）。7.3判断题1．图是一种非线性结构，所以只能用链式存储。（）【答案】×2．图的最小生成树是唯一的。（）【答案】×3．如果一个图有n个顶点和小于n-1条边，则一定是非连通图。（）【答案】√4．有n-1条边的图一定是生成树。（）【答案】×5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（）【答案】√6．用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价为O(n+e)。（）【答案】√7．逆邻接表只能用于有向图，邻接表对于有向图和无向图的存储都适用。（）【答案】√8．任何一个关键活动提前完成,那么整个工程将会提前完成。（）【答案】×9．在AOE网络中关键路径只有一条。（）【答案】×10．在AOV网络中如果存在环，则拓扑排序不能完成。（）【答案】√11．图的邻接矩阵存储是唯一的，邻接表存储也是唯一的。（）【答案】×12．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是O(n*e)。（）【答案】×13．任意一个图都是其自身的子图。（）【答案】√14．一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（）【答案】×7.4应用题1．设有一有向图为G=(V，E)。其中，V={v1,v2,v3,v4,v5}，E={v2,v1,v3,v2,v4,v3,v4,v2,v1,v4,v4,v5,v5,v1}，请画出该有向图并判断是否是强连通图。分析：作该题的关键是弄清楚以下两点（1）边集E中vi,vj表示一条以vi为弧尾，vj为弧头的有向弧。（2）强连通图是任意两顶点间都存在路径的有向图。【答案】该有向图是强连通图，表示如下：2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【答案】【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：（1）图中有多少条边?（2）任意两个顶点i和j是否有边相连?（3）任意一个顶点的度是多少?【答案】（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。（2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。（3）任意一个顶点vi的度是第i行或第i列上非0元的个数。4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。【答案】邻接矩阵如下：邻接表如下：逆邻接表如下：十字链表如下：深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。【答案】该无向图如下所示：深度优先搜索生成树为：广度优先搜索生成树为：6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。【答案】【解析】Kruscal算法的操作步骤：首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。【答案】7．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下（1）求事件的最早发生时间ve(j),最晚发生时间vl(j);（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6),最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0);（3）计算e(i),l(i)：设ai由弧j,k表示，持续时间记为dutj,k，则有下式成立e(i)=ve(j)l(i)=vl(k)-dut(j,k)（4）找出e(i)-l(i)=0的活动既是关键活动。【答案】关键路径为：a0-a4-a6-a98．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。【答案】（1）0132465（2）01234659．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值，或者是D[j]与vj到vk弧上的权值之和，其中D[j]是已经找到的从v到vj的最短路径。【答案】S是已找到最短路径的终点的集合。10．利用Floyd算法求下图中各对顶点之间的路径。【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，．．．，vk）和(vk，．．．，vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。求解的关键是求解如下的一个n阶方阵序列：D(-1)，D(0)，D(1)，．．．，D(k)，D(n-1)其中D(-1)[i][j]=G．arcs[i][j]D(k)=Min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1【答案】每对顶点之间的最短路径及长度总结如下：顶点A到顶点C最短路径为：A-C，长度为：１顶点A到顶点B最短路径为：A-C-B，长度为：4顶点C到顶点A最短路径为：C-B-A，长度为：12顶点C到顶点B最短路径为：C-B，长度为：3顶点B到顶点A最短路径为：B-A，长度为：9顶点B到顶点C最短路径为：B-A-C，长度为：10