1、图模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 下列关于无向连通图特性的叙述中，正确的是（ ）。I 所有顶点的度之和为偶数 II 边数大于顶点个数减 1I 至少有一个顶点的度为 1（A）只有 I（B）只有 II（C） I 和 II（D）I 和I2 若无向图 G=(V，E)中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（ ）。（A）6（B） 15（C） 16（D）213 下列关于图的叙述中，正确的是（ ）。I,回路是简单路径 II,存储稀疏图，用邻接矩阵比邻接表更省空间 III,若有向图中存在拓扑序列，则该图不存在回路（A）
2、仅（B）仅 I、II（C）仅 III（D）仅 I、III4 一个有 n 个顶点和 n 条边的无向图一定是（ ）。（A）连通的（B）不连通的（C）无环的（D）有环的5 一个有 28 条边的非连通无向图至少有（ ）个顶点。（A）7（B） 8（C） 9（D）106 对于一个有 n 个顶点的图：如果是连通无向图，其边的个数至少为（ ）；如果是强连通有向图，其边的个数至少为（ ）。（A）n-1 ，n（B） n-1，n(n-1)（C） n，n（D）n，n(n-1)7 以下关于图的叙述中，正确的是（ ）。（A）强连通有向图的任何顶点到其他所有顶点都有弧（B）图的任意顶点的入度等于出度（C）有向完全图一定是强
3、连通有向图（D）有向图的边集的子集和顶点集的子集可构成原有向图的子图8 以下关于图的叙述中，正确的是（ ）。（A）图与树的区别在于图的边数大于或等于顶点数（B）假设有图 G=V，E，顶点集 VV，EE ，则 V和E构成 G 的子图（C）无向图的连通分量指无向图中的极大连通子图（D）图的遍历就是从图中某一顶点出发访遍图中其余顶点9 在有 n 个顶点的有向图中，每个顶点的度最大可达（ ）。（A）n（B） n-1（C） 2n（D）2n-210 如果具有 n 个顶点的图是一个环，则它有（ ）棵生成树。（A）n 2（B） n（C） n-1（D）111 图中有关路径的定义是（ ）。（A）由顶点和相邻顶点序
4、偶构成的边所形成的序列（B）由不同顶点所形成的序列（C）由不同边所形成的序列（D）上述定义都不是12 具有 6 个顶点的无向图，当有（ ）条边时能确保是一个连通图。（A）8（B） 9（C） 10（D）1113 无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有（ ）个顶点。（A）11（B） 12（C） 15（D）1614 设有无向图 G=(v，E)和 G=(V，E)，如果 G是 G 的生成树，则下列不正确的是（ ）。 I,G 为 G 的连通分量 II,G为 G 的无环子图 III,G为 G 的极小连通子图且 V=V（A
5、）I、II（B）只有 III（C） II、III（D）只有 I15 若一个具有 n 个顶点，e 条边的无向图是一个森林，则该森林中必有（ ）棵树。（A）n（B） e（C） n-e（D）116 在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数是（ ）。（A）顶点 v 的度（B）顶点 v 的出度（C）顶点 v 的入度（D）依附于顶点 v 的边数17 带权有向图 G 用邻接矩阵存储，则 vi 的入度等于邻接矩阵中（ ）。（A）第 i 行非-的元素个数（B）第 i 列非-的元素个数（C）第 i 行非-且非 0 的元素个数（D）第 i 列非-且非 0 的元素个数18 若邻接表中有奇数个边表结点，
6、则一定是（ ）。（A）图中有奇数个结点（B）图中有偶数个结点（C）图为无向图（D）图为有向图19 用邻接表法存储图所用的空间大小（ ）。（A）与图的顶点数和边数有关（B）只与图的边数有关（C）只与图的顶点数有关（D）与边数的平方有关20 下列哪一种图的邻接矩阵是对称矩阵（ ）。（A）有向网（B）无向网（C） AOV 网（D）AOE 网21 假设有 n 个顶点 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为（ ）。（A）O(n)（B） O(e)（C） 0(n+e)（D）O(ne)22 以下关于图的存储结构的叙述中正确的是（ ）。（A）一个图的邻接矩阵表示唯一，邻接
7、表表示唯一（B）一个图的邻接矩阵表示唯一，邻接表表示不唯一（C）一个图的邻接矩阵表示不唯一，邻接表表示唯一（D）一个图的邻接矩阵表示不唯一，邻接表表示不唯一23 若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则可以断定该图一定（ ）。（A）是无向图（B）是有向图（C）是完全图（D）不是带权图24 n 个顶点的无向图的邻接表最多有（ ）个边表结点。（A）n 2（B） n(n-1)（C） n(n+1)（D）n(n-1)225 在含有 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为（ ）。（A）e（B） 2e（C） n2-e（D）n 2-2e25 从邻接阵矩可以看出，该图共
8、有() 个顶点；如果是有向图该图共有()条弧；如果是无向图，则共有() 条边。26 _;（A）9（B） 3（C） 6（D）127 _;（A）5（B） 4（C） 3（D）228 _;（A）5（B） 4（C） 3（D）229 对邻接表的叙述中，（ ）是正确的。（A）无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的两倍（B）邻接表比邻接矩阵的操作更简便（C）邻接矩阵比邻接表的操作更简便（D）求有向图结点的度，必须遍历整个邻接表30 关于图的存储结构，（ ）是错误的。（A）使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关（B）邻接表
9、只用于有向图的存储，邻接矩阵适用于有向图和无向图（C）若一个有向图的邻接矩阵，对角线以下元素为 0，则该图的拓扑序列必定存在（D）存储无向图的邻接矩阵是对称的，故只需存储邻接矩阵的下 (或上)三角部分即可31 当一个有 n 个顶点的图用邻接矩阵 A 表示时，若图为有向图时，顶点 vi 的入度是（ ）；若图为无向图时，顶点 vi 的度是（ ）。32 无向图 G=(V，E)，其中：V=a，b，c，d，e ，f)，E=(a，b)，(a ，e)，(a，c)，(b，e)，(c，D，(f，d)，(e，d)，对该图从 a 开始进行深度优先遍历，得到的顶点序列正确的是（ ）。（A）a，b， e，c，d，f（B
10、） a，c ，fe，b，d（C） a，e ，b，c ，f ，d（D）a，e，d，f，c，b33 如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是（ ）。（A）完全图（B）连通图（C）有回路（D）一棵树34 如图所示，在下面的 5 个序列中，符合深度优先遍历的序列有多少个（ ）。 1、aebfdc2、acfdeb3、aedfcb4 、aefdbc5、aecfdb（A）5（B） 4（C） 3（D）235 对于一个非连通无向图 G，采用深度优先遍历访问所有顶点，在 DFSTraverse函数(见考点讲解 DFS 部分 )中调用 DFS 的次数正好等于（ ）。（A）顶点数（
11、B）边数（C）连通分量数（D）不确定36 对一个有 n 个顶点 e 条边的图采用邻接表表示时，进行 DFS 遍历的时间复杂度为（ ），空间复杂度为（ ）：进行 BFS 遍历的时间复杂度为（ ），空间复杂度为（ ）。（A）O(n)（B） O(e)（C） O(n+e)（D）O(1)37 对于有 n 个顶点 e 条边的图采用邻接矩阵表示时，进行 DFS 遍历的时间复杂度为（ ）；进行 BFS 遍历的时间复杂度为（ ）。（A）O(n 2)（B） O(e)（C） O(n+e)（D）O(e 2)38 用邻接表存储的图的深度优先遍历算法类似于树的（ ），而其广度优先遍历算法类似于树的（ ）。（A）中序遍历（
12、B）先序遍历（C）后序遍历（D）按层次遍历图模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 A【试题解析】 无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减 1，故 II 错误。考虑一个无向连通图的顶点恰好构成一个回路的情况，此时，每个顶点的度都是 2，故 III 错误。在无向图中，所有顶点的度之和为边数的 2 倍，故 I 正确。【知识模块】 图2 【正确答案】 C【试题解析】 由于题干要求在“任何情况”下都是连通的，考虑最极端情形，即G 的 6 个顶点构成一个完全无向图，再加上一条边后，第 7 个顶点必然与此完全无向图构成一个连
13、通图，所以最少边数=6*52+1=16。【知识模块】 图3 【正确答案】 C【试题解析】 回路对应于路径，简单回路对应于简单路径，故 I 错误；稀疏图是边比较少的情况，此时用邻接矩阵必将浪费大量的空间，应该选用邻接表，故 II错误。存在回路的图不存在拓扑序列，III 正确。II 和I 中所涉知识点请参阅后面的内容。【知识模块】 图4 【正确答案】 D【试题解析】 如果一个无向图有 n 个顶点和 n1 条边，可以使它连通但没有环(即生成树) ，但再加一条边，在不考虑重边的情形下，就必然会构成环。【知识模块】 图5 【正确答案】 C【知识模块】 图6 【正确答案】 A【试题解析】 对于连通无向图，
14、边最少即构成一棵树的情形；对于强连通有向图，边最少即构成一个环的情形。【知识模块】 图7 【正确答案】 C【试题解析】 强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，有向图的边集的子集和顶点集的子集无法构成子图。【知识模块】 图8 【正确答案】 C【试题解析】 图与树的区别是逻辑上的而不是边数的区别，图的边数也可能小于树的边数，故 A 错；若 E中的边对应的顶点不是 V的元素时，V和E)无法构成图，故 B 错；无向图的极大连通子图称为连通分量，C 正确；图的遍历要求每个结点只能被访问一
15、次，且若图非连通，从某一顶点出发，无法访问到其他全部顶点，D 的说法不准确。【知识模块】 图9 【正确答案】 D【试题解析】 在有向图中，顶点的度为入度与出度之和。n 个顶点的有向图中，任一顶点最多还可以与其他 n1 个顶点有一对边相连。【知识模块】 图10 【正确答案】 B【试题解析】 因为 n 个顶点构成的环共有 n 条边，去掉其中任意一条便是一棵生成树，所以共有 n 种情况。【知识模块】 图11 【正确答案】 A【试题解析】 参考路径的定义。【知识模块】 图12 【正确答案】 D【知识模块】 图13 【正确答案】 D【知识模块】 图14 【正确答案】 D【试题解析】 一个连通图的生成树是
16、一个极小连通子图，显然它是无环的，故II、I 正确。极大连通子图称为连通分量，G连通而非连通分量。这里再补充一下“极大连通子图”：如果图本来就不是连通的，那么每个子部分如果包含它本身的所有顶点和边，那么它就是极大连通子图。【知识模块】 图15 【正确答案】 C【试题解析】 n 个结点的树有 n1 条边，假设有 x 棵树，将每棵树的根连到一个添加的结点，则成为一棵树，结点数是 n+1，边数是 e+x，从而可知 x=ne，也就是 ne 棵树了。【知识模块】 图16 【正确答案】 C【试题解析】 题中的边表是不包括顶点表的。因为任何顶点 u 对应的边表里存放的都是以 u 为起点的边所对应的另一个顶点
17、 v。从而 v 在边表中出现的次数也就是它的入度。【知识模块】 图17 【正确答案】 D【试题解析】 有向图的邻接矩阵中，O 和一表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。【知识模块】 图18 【正确答案】 D【试题解析】 无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数。题中边表结点为奇数个，故必然是有向图，且有奇数条边。【知识模块】 图19 【正确答案】 A【试题解析】 邻接表表示时，顶点数 n 决定了顶点表的大小，边数 e 决定了边表的个数，且每条边存储两次，占用的总存储空间为 O(n+2e)，故选 A。而邻接矩阵只与图的顶点数有关，为 O(V2)。【知
18、识模块】 图20 【正确答案】 B【试题解析】 无向图的邻接矩阵存储中，每条表存储两次，且 AijAji。【知识模块】 图21 【正确答案】 C【试题解析】 删除与某顶点 v 相关的所有边过程如下：先删除下标为 v 的顶点表结点的单链表，出边数最多为 n-1，对应时间复杂度为 O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为 O(e)。故总的时间复杂度为 O(n+e)。【知识模块】 图22 【正确答案】 B【试题解析】 邻接矩阵表示唯一是因为图中边的信息表示在矩阵中有确定的位置，邻接表不唯一是因为邻接表取决于读入边的顺序和边表中的插入算法。【知识模块】 图23 【正确答案】 C【
19、试题解析】 除主对角线上的元素，其余元素全为 1，则说明任意两个顶点之间都有边相连，则该图一定是完全图。【知识模块】 图24 【正确答案】 B【试题解析】 n 个顶点的无向图最多有 n(n1)2 条边，每条边在邻接表中存储两次，所以边表结点最多为 n(n-1)个。【知识模块】 图25 【正确答案】 D【试题解析】 无向图的邻接矩阵中，非零元素的个数为 2e，故零元素的个数为 n2-2e。读者应掌握此题的变形，当无向图变为有向图时，能够求出零的个数和非零的个数。【知识模块】 图【知识模块】 图26 【正确答案】 D【知识模块】 图27 【正确答案】 B【知识模块】 图28 【正确答案】 D【试题
20、解析】 邻接矩阵的顶点数等于矩阵的行(列)数，有向图的边数等于矩阵中非零元素的个数，无向图的边数等于矩阵中非零元素个数的一半。【知识模块】 图29 【正确答案】 D【试题解析】 无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数，故 A错。【知识模块】 图30 【正确答案】 B【试题解析】 n 个顶点的图，若采用邻接矩阵表示，不考虑压缩存储，则存储空间大小为 O(n2)，A 正确。【知识模块】 图31 【正确答案】 D【知识模块】 图32 【正确答案】 D【试题解析】 此类题可以根据边的邻接关系快速排除错误选项，以 A 为例，在遍历到 e 之后，应该访问与 e 邻接但未被访问的结点，
21、 (e，c)显然不在边集中。【知识模块】 图33 【正确答案】 B【试题解析】 若仅通过一次 DFS 或 BFS 就可访问图中所有顶点，则可知图是连通的，故选 B。【知识模块】 图34 【正确答案】 D【试题解析】 仅 1 和 4 正确。以 2 为例，遍历到 c 之后，与 c 邻接且未被访问的结点为空集，所以 a 的邻接点 b 或 e 入栈，显然 2 不符合这种情况。【知识模块】 图35 【正确答案】 C【试题解析】 DFS(或 BFS)可以用来计算图的连通分量数，而计算的结果正是DFSTraverse（ ）中 DFS 被调用的次数。【知识模块】 图36 【正确答案】 C【试题解析】 深度优先遍历时，每个顶点表结点和每个边表结点均查找一次，每个顶点递归调用一次；而广度优先时也是每个顶点表结点和每个边表结点均查找一次，每个顶点进入队列一次。故而都是选 C，A。【知识模块】 图37 【正确答案】 A【试题解析】 采用邻接矩阵表示时，查找一个顶点所有出边的时间复杂度为 O(n)，共有 n 个顶点，故时间复杂度均为 O(n2)。【知识模块】 图38 【正确答案】 B【试题解析】 图的深度优先搜索类似与树的先根遍历，是先访问结点，再递归向外层结点遍历，都采用回溯算法。图的广度优先搜索类似于树的层序遍历，是一层一层向外层扩展遍历，都需要采用队列来辅助算法的实现。【知识模块】 图
