《考研计算机－习题精炼和重点回顾 图》由会员分享，可在线阅读，更多相关《考研计算机－习题精炼和重点回顾 图（20页珍藏版）》请在金锄头文库上搜索。
1、在一个图中，所有顶点的度数之和等于所有边的数目的（ ）倍。 您的答案是：【未答】 正确答案是：【C 】解析：2具有 6 个顶点的无向图至少应有（ ）条边才能确保一个连通图。 您的答案是：【未答】 正确答案是：【A】解析：根据连通图的定义，连通图中任意两个顶点都是连通的。一个极小连通子图，它含有图中全部顶点，但只有足以构成一个树的 边。题目中，无向图具有 6 个顶点，则至少应该有 6 条边才能确保一个连通图。3对于具有 n(n1)个顶点的强连通图，其有向边条数至少是 您的答案是：【未答】 正确答案是：【B】解析：当所有 n 个顶点都在某一个有向环（有向回路）上时，形成一个强连通图，其有向边条数为
2、 n，例外情况是 n=1 时，至少可以有 0 条有向边。在此情况下，当有向边的条数少于 n 则不能构成环，不再是强连通图。4如下图所示的有向图的强连通分量为 A.ABCDEF B.A，BC ，DEF C.A，B ，CD，E ，F D.A，B，C ，D，E ，F 您的答案是：【未答】 正确答案是：【A】解析：图中顶点 A、B、C、D、E、F 都没有返回自身的路径，可判断它们各自构成一个强连通分量。5若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定是 您的答案是：【未答】 正确答案是：【D】解析：一个有向图具有拓扑排序序列，说明它是个有向无环图（简称 但在邻接矩阵上并没有直接的表示。6对于一个有
3、向图，若一个顶点的度为 度为 对应逆邻接表中该顶点单链表中的边结点数为 您的答案是：【未答】 正确答案是：【C 】解析：对于有向图，顶点 v 的度分为入度和出度，入度是以顶点 v 为终点的边的数目；出度是以顶点 v 为起点的边的数目，顶点 v 的度等于起入度和出度之和。因此，此有向图的入度为 于有向图的邻接表表示，边表的结点数就等于图中边数，每个单链表的结点数就是相应顶点的出度。所谓逆邻接表就是对图中每个顶点 立一个单链表，把与 邻接的顶点放在一个链表中，即边表中存放的是入度边而不是出度边。对于一个有向图，若一个顶点的度为 度为 对应逆邻接表中该顶点单链表中的边结点数为 若邻接表中有奇数个边表
4、结点，则一定是 您的答案是：【未答】 正确答案是：【D】解析：无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数。8用邻接矩阵 A 表示图，判断任意两个结点 间是否有长度为 m 的路径相连，则只要检查（ ）的第 i 行第 j 列的元素是否为零即可。 C. D. 您的答案是：【未答】 正确答案是：【C 】解析：当 m=1 时，显然只需检查邻接矩阵 A 的第 i 行第 j 列元素是否为零；当 m1时，假设顶点 间存在长度为 路径，的第 i 行第j 列元素非零，则如果存在长度为 m 的路径，可以证明矩阵 第 i 行第 除了使用拓扑排序的方法，下面哪一种方法可以判断出一个有向图是否有回路
5、 您的答案是：【未答】 正确答案是：【A】解析：本题主要考查判断有向图中是否有回路的方法。从图中的任意一个顶点出发，采用深度优先遍历，若路径中的顶点有重复，则图中有回路。【归纳总结】判断有向图是否存在回路的方法：拓扑排序和深度优先遍历。10导致图的遍历序列不唯一的因素是 历方法的不同 储结构的不同 储结构的不同 储结构的不同、遍历方法的不同 您的答案是：【未答】 正确答案是：【D】解析：导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先，遍历的出发顶点选择的不唯一，而得到的遍历序列显然不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，而得到的结果也是不相同的。另外，即使遍历
6、的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。11用邻接表表示的图进行广度优先遍历时，通常采用下列哪种结构实现算法？ 您的答案是：【未答】 正确答案是：【B】解析：本题主要考查图的广度优先遍历算法的特点。因为广度优先遍历的过程具有“先被访问的顶点的邻接点优先于后被访问的顶点的邻接点”的特征，所以需使用队列存储已被访问的路径长度为 1，2，n 的顶点。12下面哪个算法可用于求无向图的所有连通分
7、量？ 您的答案是：【未答】 正确答案是：【A】解析：本题主要考查图的连通分量的求法和广度优先遍历算法的应用。从图中一个顶点出发进行广度优先遍历，可将与该顶点连接的所有顶点遍历到，即找到了包含该顶点的连通分量；再选择剩余未被访问过的顶点继续广度优先遍历，直到所有顶点都被访问过。13一个有 n 个顶点 e 条边的连通图的生成树有多少条边 您的答案是：【未答】 正确答案是：【C 】解析：本题主要考查生成树的定义和性质。生成树的定义是包含连通图中全部 n 个顶点和 边的极小连通子图。【归纳总结】图的生成树是不唯一的，从不同顶点出发可以得到不同的生成树，当存在相同权值的边时，其最小生成树也可能是不唯一的
8、。14下列说法正确的是 的一棵最小代价生成树的代价未必小于图 G 的其他任何一棵生成树的代价 权值最小的边一定会出现在所有的解中 该图的最小生成树是唯一的 您的答案是：【未答】 正确答案是：【C 】解析：本题主要考查最小生成树的定义和性质。最小（代价）生成树是连通网中的所有生成树中权值之和最小的生成树，A 与该定义矛盾；当存在从一个结点直接指向其自身的边时，即使该边的权值最小也不会出现在任何解中，因此 B 不正确；因为图中每边的权值都不相同，最小生成树一定有权值最小的 边构成，必然是唯一的，因此 C 正确；一个带权无向连通图中最小生成树的权值之和一定为最小的 权值之和，因此一定是唯一的，因此
9、D 不正确。15任何一个带权无向连通图的最小生成树 您的答案是：【未答】 正确答案是：【C 】解析：一般情况下，带权连通图的最小生成树不一定是唯一的。16对于含有 n 个顶点 e 条边的无向连通图，求最小生成树的 法的时间复杂度为 A.O( B.O( C. D.O( 您的答案是：【未答】 正确答案是：【D】解析：本题主要考查 法的时间复杂度。17已知带权连通无向图 G（V ，E），其中Vv1，v4，v5，v6，E( v1，0 ，( v1， ，( v3，( v3，1，( v2， ，( v4，( v4， ，( v5，( v6，（注：顶点偶对右下角的数据为边上的权值），从源点 顶点 最短路径上经过的
10、顶点序列是 v2，v5，v3，v4，v6，v3，v4，v5，v5，v4，v6，您的答案是：【未答】 正确答案是：【B】解析：由求解最短路径的 法可以得到结论。18设某有向图中有 n 个顶点，e 条边，进行拓扑排序时总的时间复杂度为 A.O( B.O(n+e) C.O(e*n) D.O( 您的答案是：【未答】 正确答案是：【B】解析：无19带权连通图 G（V，E），其中Vv1，v4，v5，v6，v8，v9，E( v1，( v1，( v2，( v3， ，( v3，( v4，( v4，( v4， ，( v5，( v5， ，( v6，( v7，( v8，( v9，（注：顶点偶对右下角的数据为边上的权值
11、）， G 的关键路径的长度是 您的答案是：【未答】 正确答案是：【C 】解析：求出该 的关键路径便可以得到结论20假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧） 您的答案是：未答； 参考答案是：有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用 0，1 ，2表示这三种状态。前面已提到，若 v ）结束前出现顶点 u 到 v 的回边，则图中必有包含顶点 v 和 u 的回路。对应程序中 v 的状态
12、为 1，而 u 是正访问的顶点，若我们找出 u 的下一邻接点的状态为 1，就可以输出回路了。【解答】用 C 语言算法描述如下：v, /输出从顶点 始的回路i=1;i=n) /破圈，直到边数 e=k) /删除第 k 条边若仍连通k; /测试下一条边 k，权值置 0 表示该边被删除k+; /下条边 是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入 可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第 40 题就是测连通分量个数的算法，请参考。“破圈”结束后，可输出 w 不为的 边。限于篇幅，这些算法不再写出。解析：无22带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：(1)该最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点;(2)选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v;(3)重复步骤(2)，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之，否则请举例说明。 您的答案是：未答； 参考答案是：题目中方法不一定能（或不能）求得最短路径。举例说明：图（a）中，假
