1、计算机专业基础综合数据结构（图）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面是一个求最小生成树的算法，其中 G 是连通无向图， T 是所求的生成树。T：=G：While T 中存在回路 dobegin 在 T 中找一条权值最大的边 e；T：=T 一e； (T 中去掉 e 边)EnD试问该算法是哪一种求最小生成树的算法?( )（A）Prim(普里姆)算法（B） Kruskal(克鲁斯卡尔算法)（C）罗巴赫算法（D）其他算法2 邻接表是图的一种( ) 。（A）顺序存储结构（B）链接存储结构（
2、C）索引存储结构（D）散列存储结构3 下面试图对图中路径进行定义，说法正确的是( )。（A）由顶点和相邻顶点序列构成的边所形成的序列（B）由不同顶点所形成的序列（C）由不同边所形成的序列（D）上述定义都不是4 无向图中顶点个数为 n，那么边数最多为( )。（A）n 一 1（B） n(n 一 1)2（C） n(n+1)2（D）n 25 在一个具有 n(n0) 个顶点的连通无向图中，至少需要的边数是( )。（A）n（B） n+1（C） n 一 1（D）n26 以下叙述中正确的是( )。I对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图连通图的广度优
3、先搜索中一般要采用队列来暂存访问过的顶点图的深度优先搜索中一般要采用栈来暂存访问过的顶点（A）I，（B） ，（C） I，（D）I，7 带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中( )。（A）第 i 行非的元素之和（B）第 i 列非的元素之和（C）第 i 行非且非 0 的元素个数（D）第 i 列非且非 0 的元素个数8 在一个无向图中，所有顶点的度之和等于边数的( )倍。（A）12（B） 1（C） 2（D）49 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )算法。（A）前序遍历（B）中序遍历（C）后序遍历（D）按层遍历10 任何一个无向连通图( )最小生成树。
4、（A）只有一棵（B）有一棵或多棵（C）一定有多棵（D）可能不存在11 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。（A）求关键路径的方法（B）求最短路径的迪杰斯特拉方法（C）深度优先遍历算法（D）广度优先遍历算法12 有 n 个顶点 e 条边的无向图，采用邻接表存储时，有( )个表头结点，有( )个链表结点。（A）n，2e（B） n，2e+1（C） n 一 1，2e（D）n12e+113 对于由 n 个顶点组成的有向完全图来说，图中共包含( )条边，对于由 n 个顶点组成的无向完全图来说，图中共包含( )条边。（A）n，n(n 一 1)（B） n，n(n 一 1)
5、2（C） 2n，n(n 一 1)（D）n(n 1)，n(n 一 1)214 在一个( ) 图中寻找拓扑序列的过程称为( ) 。（A）有向，拓扑排序（B）无向，拓扑排序（C）有向，最短路径搜索（D）无向，最短路径搜索15 用邻接矩阵 A 表示图，判定任意两个顶点 vi 和 vj 之间是否有长度为 m 的路径相连，则只要检查( ) 的第 i 行第 j 列的元素是否为零即可。（A）mA（B） A（C） Am（D）Am-116 当各边上的权值( ) 时，BFS 算法可用来解决单源最短路径问题。（A）均相等（B）均互不相等（C）不一定相等（D）不确定17 下面关于图的存储结构的叙述中正确的是( )。（A
6、）用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关（B）用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关（C）用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关（D）用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关18 在有向图 G 的拓扑序列中，若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是( )。（A）G 中有弧v i，v j（B） G 中有一条从 vi 到 vj 的路径（C） G 中没有弧v i，v j（D）G 中有一条从 vj 到 vi 的路径19 以下关于图的说法中正确的是( )。I一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩
7、阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（A），（B） ，（C） ，（D）仅有20 下列关于 AOE 网的叙述中，不正确的是( )。（A）关键活动不按期完成就会影响整个工程的完成时间（B）任何一个关键活动提前完成，那么整个工程将会提前完成（C）所有的关键活动提前完成，那么整个工程将会提前完成（D）某些关键活动提前完成，那么整个工程将会提前完成21 一个二部图的邻接矩阵 A 是一个( )类型的矩阵。（A）nn 矩阵（B）分块对称矩阵（C）上三角矩阵（D）下三角矩阵22 求解最短路径的 Floyd 算法的时间复
8、杂度为( )。（A）O(n)（B） O(n+c)（C） O(n2)（D）O(n 3)23 下列 4 组含 C1C7 的结点序列中，( )是下图所示的有向图的拓扑序列。（A）C1，C2 ，C6，C7，C5，C4，C3（B） C1，C2，C6，C3， C4，C5，C7（C） C1，C4，C2，C3， C5，C6，C7（D）C5，C7 ，C4，C1，C2，C3，C624 如果具有 n 个顶点的图是一个环，则它有( )棵生成树。（A）n 2（B） n（C） n 一 1（D）125 如下图所示，在下面的 5 个序列中，符合深度优先遍历的序列有( )个。aebfdc acfdeb aedfcb aefdb
9、c aecfdb（A）5（B） 4（C） 3（D）226 无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有( )个顶点。（A）1l（B） 12（C） 15（D）1627 对 AOE 网络中有关关键路径的叙述中，正确的是( )。（A）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间（B）从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间（C）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间（D）从开始顶点到完成顶点的具有
10、最小长度的路径，关键路径长度是完成整个工程所需的最长时间28 以下关于图的叙述中，正确的是( )。（A）强连通有向图的任何顶点到其他所有顶点都有弧（B）图与树的区别在于图的边数大于或等于顶点数（C）无向图的连通分量指无向图中的极大连通子图（D）假设有图 G=V，E，顶点集 VV，EE，则 V和E 构成 G 的子图29 假设有 n 个顶点 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为( ) 。（A）O(n)（B） O(e)（C） O(n+e)（D）O(ne)30 若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 的结点数至少是( )
11、。（A）11（B） 10（C） 9（D）831 已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=a，b，a，c ， d，c ，d，e，b，e，c ，e。对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。（A）a，d， c，b，e（B） d，a，b，c ，e（C） a，b，d，c ，e（D）a，b， c，d，e32 用有向无环图描述表达式(A+B)*(A+B) A)，至少需要顶点的数目为( )。（A）5（B） 6（C） 8（D）933 邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：关于图中各个域的说
12、明，不正确的是( )。（A）vertex 存储的是结点的数值域的内容（B） firstedge 域指示第一条依附于该顶点的边（C） mark 指向下一条依附于结点的边（D）info 为指向和边相关的各种信息的指针域34 以下关于十字链表的说法中，不正确的是( )。（A）十字链表是有向图的另一种链式存储结构（B）行指针 row 为矩阵中的行位置，列指针 col 为矩阵中的列位置（C）数值 val 为矩阵中的值（D）right 指针指向矩阵中的行位置，down 指针指向矩阵中的列位置二、综合应用题41-47 小题，共 70 分。35 证明：具有 n 个顶点和多于 n 一 1 条边的无向连通图 G
13、一定不是树。36 证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 0 的充要条件是该图为无环图。37 关于图(Graph) 的一些问题：(1)有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?(2)表示有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?38 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上?39 假定图 G=(V，E)是有向图，V=1 ，2，N ，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即 A 是一个二维数组。如果 i 到 j 有边，则 Ai，j=1 ，否则Ai
14、，j=0。请给出一个算法思想，该算法能判断 G 是否是非循环图(即 G 中是否存在回路)，要求算法的时间复杂性为 O(n2)。40 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?41 G=(V，E)是一个带有权的连通图，如图所示。 (1)什么是 G 的最小生成树? (2)G如图所示，请找出 G 的所有最小生成树。42 对于如下的加权有向图，给出算法 Dijkstra 产生的最短路径的支撑树，设顶点A 为源点，并写出生成过程。43 (1)对于有向无环图，叙述求拓扑有序序列的步骤。(2)对于以下的图，写出它的4 个不同的拓扑有序序列。44 试写一算法，判断以邻接
15、表方式存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij) 。( 注意：算法中涉及的图的基本操作必须在存储结构上实现。)45 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)46 已有邻接表表示的有向图，请编程判断从第 u 顶点至第 v 顶点是否有简单路径，若有则打印出该路径上的顶点。47 “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“ 破圈法 ”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现
16、你所给出的算法。(注意：圈就是回路)48 设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为：MAx从 到 v 的最短距离| 属于 V(G)如果 v 是有向图 G 中具有最小偏心度的顶点，则称顶点 v 是 G 的中心点。49 对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减 1，并对其未访问的、入度为 0 的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义。(2)定义在算法中使用的全局辅助数组。(3)写出在遍历图的同时进行拓扑排序的算法。计算
17、机专业基础综合数据结构（图）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 由算法可以看出使用的是 Kruskal 算法。【知识模块】 数据结构2 【正确答案】 B【试题解析】 图的邻接表存储结构是一种链接存储结构。【知识模块】 数据结构3 【正确答案】 A【试题解析】 由图的定义可知，B 与 C 是错误的。【知识模块】 数据结构4 【正确答案】 B【试题解析】 无向图中有 n 个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为 n(n 一 1)
18、2。【知识模块】 数据结构5 【正确答案】 C【试题解析】 在无向图中，如果从一个顶点 vi 到另一个顶点 vj(ij)有路径，则称顶点 vi 和 vj 是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有 n 个顶点的连通无向图至少有 n1 条边。【知识模块】 数据结构6 【正确答案】 B【试题解析】 I 的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。、的叙述显然是正确的。【知识模块】 数据结构7 【正确答案】 D【试题解析】 有向图的邻接矩阵中，0 和表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。【知识模块
19、】 数据结构8 【正确答案】 C【试题解析】 在无向图中，一条边计入两个顶点的度数。【知识模块】 数据结构9 【正确答案】 A【试题解析】 由图的深度优先遍历算法和二叉树的前序遍历可知选 A。【知识模块】 数据结构10 【正确答案】 B【试题解析】 无向连通图应有一棵或多棵最小生成树。【知识模块】 数据结构11 【正确答案】 C【试题解析】 当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出 DFSTraverse 算法)即为逆向的拓扑序列。【知识模块】 数据结构12 【正确答案】 A【试题解析】 根据邻接表的结构，无向图对应的邻接表有 n 个表头结点，有 2e个链表结点(每
20、条边对应两个链表结点)。【知识模块】 数据结构13 【正确答案】 D【试题解析】 由完全图的定义可知本题答案为 D。【知识模块】 数据结构14 【正确答案】 A【试题解析】 寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。【知识模块】 数据结构15 【正确答案】 C【试题解析】 此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为 1，否则为 0。本题只要考虑 Am=AAA(m 个 A 矩阵相乘后的乘积矩阵)中(i ，j) 的元素值是否为 0 就行了。【知识模块】 数据结构16 【正确答案】 A【试题解析】 此题考查的知识点是图的 BFS 算法。BFS 是从根结点开始
21、，沿着树的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选 A。【知识模块】 数据结构17 【正确答案】 A【试题解析】 邻接矩阵法的基本思想是对于有 n 个顶点的图，用一维数组 vexsn存储顶点信息，用二维数组 Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在 vexs 数组中的下标代表顶点，邻接矩阵中的元素 Aij存放的是顶点 i 到顶点 j 之间关系的信息。邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第 i 个单链表表示依附于顶点 Vi的边(对
22、有向图是以顶点 Vj 为头或尾的弧)。【知识模块】 数据结构18 【正确答案】 D【试题解析】 此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点vi 与顶点 vj 有一条弧，则拓扑序列中顶点 vi 必在顶点 vj 之前。若有一条从 vi 到 vi的路径，则顶点 vi 不可能在顶点 vj 之前。所以应选 D。【知识模块】 数据结构19 【正确答案】 A【试题解析】 说法 I 是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都等于有向图中的边的个数。 说法是正确的，邻接矩阵的空间复杂度为 O(n2)，与边的个数无关。 说法是错误的，有向图的邻接矩阵不一定是不对称的，例如，
23、有向完全图的邻接矩阵就是对称的。【知识模块】 数据结构20 【正确答案】 B【试题解析】 此题考查的知识点是图的关键路径。在 AOE 网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。关键路径上的活动称为关键活动。A 、C 、D 的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选 B。【知识模块】 数据结构21 【正确答案】 B【试题解析】 此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图 G=V，E 的顶点集 V 划分成两个子集 V1 和 V2(V1V2= )，使得 G中任何一条边的两个端点
24、一个属于 V1，另一个属于 V2，则称 G 为二部图。由于其特点，其存储矩阵必为分块对称的，所以选 B。【知识模块】 数据结构22 【正确答案】 D【知识模块】 数据结构23 【正确答案】 D【试题解析】 考查拓扑排序的算法。以 l 开头的拓扑排序过程，如下图所示：以 5 开头的拓扑排序过程，答案中的过程如下图所示：【知识模块】 数据结构24 【正确答案】 B【试题解析】 因为 n 个顶点构成的环共有 n 条边，去掉其中任意一条便是一棵生成树，共有凡种情况，所以可以有 n 棵不同的生成树。【知识模块】 数据结构25 【正确答案】 D【试题解析】 本题中，符合深度优先遍历顺序的是 1 和 5，其
25、他三个序列均不符合。【知识模块】 数据结构26 【正确答案】 D【试题解析】 由于在具有 n 个顶点 e 条边的无向图中，有 ，故可求得度为 2 的顶点数为 7 个，从而最多有 16 个顶点。【知识模块】 数据结构27 【正确答案】 A【试题解析】 本题考查关键路径的定义。关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。关键活动：关键路径上的活动称为关键活动。【知识模块】 数据结构28 【正确答案】 C【试题解析】 强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A 错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若 E中的边对应的顶点不
26、是 V中的元素时，则 V和E无法构成图，D 错误。【知识模块】 数据结构29 【正确答案】 C【试题解析】 删除与某项点 v 相关的所有边的过程如下：先删除下标为 v 的顶点表结点的单链表，出边数最多为 n 一 1，对应时间复杂度为 O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为 O(e)。故总的时间复杂度为 O(n+e)。【知识模块】 数据结构30 【正确答案】 B【试题解析】 n 个顶点构成的无向图中，边数 n(n1)2，将 e=36 代入，有n9，现已知无向图是非连通的，则 n 至少为 10。【知识模块】 数据结构31 【正确答案】 D【试题解析】 选项 D 中，删去 a
27、、b 及其对应的出边后，c 的入度不为 0，因此有边d，c，故不是拓扑序列。选项 A、B、C 均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。【知识模块】 数据结构32 【正确答案】 A【试题解析】 此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的 5 个字符作为 5 个顶点，其中A+B 和 A 可共用，所以至少 5 个即可，选 A。【知识模块】 数据结构33 【正确答案】 C【试题解析】 顶点表由两个域组成，vertex 域存储和该顶点相关的信息，firstedge 域指示第一条依附于该顶点的边。边表结点由六个域组成：mark
28、为标记域，用以标记该条边是否被搜索过；iVex 和 jVex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边：info 为指向和边相关的各种信息的指针域。【知识模块】 数据结构34 【正确答案】 D【试题解析】 right 指向右侧的一个非零元素，down 指向下侧的一个非零元素。【知识模块】 数据结构二、综合应用题41-47 小题，共 70 分。35 【正确答案】 此题考查的知识点是图的定义。具有 n 个顶点 n1 条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于 n 一 1条，
29、因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。【知识模块】 数据结构36 【正确答案】 此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为 0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(Aij=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为 0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无
30、环图顶点编号，应按顶点出度顺序编号。)【知识模块】 数据结构37 【正确答案】 (1)n(n 一 1)，n (2)10 6，不一定是稀疏矩阵 提示：此题考查的知识点是图的相关术语。 (1)在有向图 G 中，如果对于每一对 vi，v j 属于 V，v i 不等于vj，从 vi 到 vj 从 vj 到 vi 都存在路径，则称 G 是强连通图。最多边是所有的顶点每对之间都有边，边数为 n(n 一 1)；最少只有一个方向有边，为 n。 (2)元素个数为矩阵的大小，即 106，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。【知识模块】 数据结构38 【正确答案】 此题考查的知识
31、点是图顶点度数。可以按各顶点的出度进行排序。n 个顶点的有向图，其顶点最大出度是 n 一 1，最小出度为 0。这样排序后，出度最大的顶点编号为 1，出度最小的顶点编号为 n 之后，进行调整，即若存在弧i，j，而顶点 j 的出度大于顶点 i 的出度，则将 j 的编号排在顶点 i 的编号之前。【知识模块】 数据结构39 【正确答案】 此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行DFS(v)时，若在退出 DFS(v)前碰到某顶点 u，其邻接点是已经访问的顶点 v，则说明 v 的子孙 u 有到 v 的回边，即说明有环；否则，无环。【知识模块】 数据结构40 【正确答案】 此题考查的知识点是
32、图的遍历。遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。【知识模块】 数据结构41 【正确答案】 (1)无向连通图的生成树包含图中全部 n 个顶点，以及足以使图连通的 n 一 1 条边。而最小生成树则是各边权值之和最小的生成树。 (2)最小生成树有两棵。下面给出顶点集合和边集合，编以三元组(V i，V j，W) 形式，其中 W 代表权值。 V(G)=1 ，2，3， 4，5 E1(G)=(4，5，2)，(2，5，4)，(2，3，5)，(1，2， 7)； E2(G)=(4，5，2) ，(2，4，4)，(2，3，5)，(1，2，7) 提示：此题考查的知识点是最
33、小生成树的定义。该题说明图的最小生成树不唯一，但权值和唯一，出现两个或两个以上的情况是因为有权值相同的边。牢记 Prim(选图的顶点) 、Kruskal(选图的边，边上权值排序) 两种算法的区别及算法步骤。【知识模块】 数据结构42 【正确答案】 顶点 A 到顶点 B、C、D、E 的最短路径依次是 3、18、38、43，按 Dijkstra 所选顶点过程是 B、C、D、E。支撑树的边集合为A， B，B，C ，C，D，B，E，具体分析如下表所示。【知识模块】 数据结构43 【正确答案】 (1)对有向图，求拓扑序列步骤为：在有向图中选一个没有前驱(即入度为零) 的顶点并输出。在图中删除该顶点及所有
34、以它为尾的弧。重复和步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。(2)从入度为 0 的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。从顶点 1 开始的可能的拓扑序列为12345678、12354678、13456278、13546278。提示：此题考查的知识点是拓扑排序。【知识模块】 数据结构44 【正确答案】 算法 1：int visited=0； 全局变量，访问数组初始化int dfs(AdjList g，vi)以邻接表存储的有向图 g，判断 vi 到 vj 是否有通路，返回 1 或 0visitedvi=1； visited
35、 是访问数组，设顶点的信息就是顶点编号P=gvifirstarc； 第一个邻接点while(P!=null)j=p 一 adjvex；if(vj=j)flag=1；return(1)； vi 和 Vj 有通路if(visitedj=0)dfs(g，j)；P=P 一next： whileif(!flag)return(0)；算法 2：输出 vi 到 vj 的路径，其思想是用一个栈存放遍历的顶点，遇到顶点 vj时输出路径。void dfs(AdjList g，int i) 顶点 vi 和顶点 vj 间是否有路径，如有，则输出int top=0， stack； stack 是存放顶点编号的栈visi
36、tedi=1； visited 数组在进入 dfs 前已初始化stack+top=i；P=gifirstarc； 求第一个邻接点while(P)if(p 一adjvex=j)stack+top=j；printf(”顶点 vi 和 vj 的路径为：n”)；for(i=1；i=top；i+)printf(”4d”，stacki)；.exit(0)；else if(visitedp-adjvex=0)dfs(g ，g 一adjvex)；top 一一；p=p 一next；算法 3：非递归算法求解。int Judge(AdjList g，int i，j)判断 n 个顶点以邻接表示的有向图 g 中，顶点
37、vi 各 vj 是否有路径，有则返回 1，否则返回 0。for(i=l；i =n；i+)visitedi=0； 访问标记数组初始化int stack，top=0；stack+top=vi；while(top 0)k=stacktop 一一；p=gkfirstarc；while(P!=null&visitedp 一adjvex=1)P=p 一next；查第 k 个链表中第一个未访问的弧结点if(P=null)top 一一；elsei=p 一 adjvex；if(i=j)return(1)； 顶点 vi 和 vj 间有路径elsevisitedi=1；stack+top=i ；whileretur
38、n(0)：顶点 vi 和 vj 间无通路提示：此题考查的知识点是图的遍历。在有向图中，判断顶点 Vi 和顶点 vj 间是否有路径，可采用搜索的方法，从顶点 vi 出发，不论是深度优先搜索 (DFS)还是宽度优先搜索(BFS)，在未退出 DFS 函数或 BFS 函数前，若访问到 vi，则说明有通路，否则无通路。设一全程变量 flag，初始化为 0，若有通路，则 flag=1。【知识模块】 数据结构45 【正确答案】 用邻接矩阵存储时，可用以下方法实现：void Print(int v，int start)输出从顶点 start 开始的回路for(i=1；i =n；i+)if(gvi!=0&vis
39、itedi=1) 若存在边(v，i) ，且顶点 i 的状态为 1printf(”d”，v)；if(i=start)printf(”n”)；else Print(i，start) ；break； if Printvoid dfs(int v)visitedv=1；for(j=1；j =n；j+)if(gvj!=0) 存在边 (v，j)if(visitedj!=1)if(!visitedj)dfs(j)； ifelsecycle=1；Print(j，j)；visitedv=2；void find_cycle() 判断是否有回路，有则输出邻接矩阵。Visited 数组为全局变量for(i=1：i =
40、n：i+)visitedi=0；for(i=1；i =n；i+)if(!visitedi)dfs(i)；【知识模块】 数据结构46 【正确答案】 void Allpath(AdjList g，vertype u，Vertype v)求有向图 g 中顶点 u 到顶点 v 的所有简单路径，初始调用形式int top=0， s；s+top=u；visitedu=1；while(top 0 | P)p=gstopfirstarc； 第一个邻接点while(p!=null&visitedp 一adjvex=1)p=p 一next； 下一个访问邻接点表if(p=null)top-一； 退栈elsei=p
41、一 adjvex； 取邻接点(编号)if(i=v) 找到从 u 到 V 的一条简单路径，输出for(k=1；k=top ：k+)printf(” 3d”，sk)；printf(”3d n”，V)； ifelsevisitedi=1；s+top=i； else 深度优先遍历 else while【知识模块】 数据结构47 【正确答案】 void SpnTree(AdjList g)用“破圈法 ”求解带权连通无向图的一棵最小代价生成树tvpedef struct|int i，j，w ；node； 设顶点信息就是顶点编号，权是整数node edge；scanf(“dd“，&e ，&n)； 输入边数和
42、顶点数for(i=1：i =e；i+) 输入 e 条边：顶点，权值scanf(“ddd“，&edgeii，&edgeij，&edgei.W) ；for(i=2；i =e；i+) 按边上的权值大小，对边进行逆序排序edge0=edgei；j=i 一 1；while(edgejwedge0w)edgej+1=edgej-；edgej+1=edge0； fork=1：eg=e；while(eg =n) 破圈，直到边数 e=n 一 1if(connect(k) 删除第 k 条边若仍连通edgekW=0；eg 一一； 测试下一条边 edgek，权值置 0 表示该边被删除k+； 下条边 whileconn
43、ect()是测试图是否连通的函数，可用 DFS 函数或 BFS 函数实现，若是连通图，一次进入 DFS 函数或 BFS 函数就可遍历完全部顶点,否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈” 结束后，可输出 edge 中 不为 0 的 n1 条边。【知识模块】 数据结构48 【正确答案】 设 C 是有向图 G 的邻接矩阵，求最小偏心度的顶点的步骤如下：(1)利用 Floyd 算法求出每对顶点之间的最短路径矩阵 A：(2)对矩阵 A 求出每列 i 的最大值，得到顶点 i 的偏心度；(3)在这 n 个顶点的偏心度中，求出最小偏心度的顶点 k，即为图 G 的中心点。对应的算
44、法如下：int Center(MGraph&G)int AMAXVMAXV， BbtAXV；int i，j，k，m；for(i=0；i Gn；i+) 将邻接矩阵赋给 Afor(j=0；j Gn；j+)Aij=Gedgesij；for(k=0；kGn；k+) 实现(1)功能，求出每对顶点之间的最短路径for(i=0；i Gn：i+)for(j=0；j Gn；j+)if(Aik+AkjAij)Aij=Aik+Akj；for(j=0；j Gn；j+)实现(2)功能，得出矩阵 A 每列最大值，即顶点 i 的偏心度，结果放在 B 数组中Bj=A0j；for(i=1；i Gn：i+)if(BjAij)Bj
45、=Aij；k=0；m=Bj；实现(3)功能，找出 n 个顶点中偏心度最小的顶点，结果放在 k 中，即为图 G 的中心点for(i=1；i Gn；i+)if(Bim)m=Bi；k=i；retum k： 返回 k 值【知识模块】 数据结构49 【正确答案】 (1)邻接表定义typedef struct ArcNodeint adjvex；struet ArcNode * next；ArcNode；typedef struct VNodevertype data：ArcNode*firstare：VNode，AdjListMAX；(2)全局数组定义int visited=0；finished=0 ；
46、flag=1 ； flag 测试拓扑排序是否成功ArcNode 木 final=null： final 是指向顶点链表的指针，初始化为 0(3)算法void dfs(AdjList g，vertype v)以顶点 v 开始深度优先遍历有向图 g，顶点信息就是顶点编号ArcNode*t： 指向边结点的临时变量printf(”d”，v)：visitedv=1；P=gvfirstarc ；while(p!=null)j=p 一 adjvex；if(visitedj=1&finishedj=0)flag=0： dfs 结束前出现回边else if(visitedj=0)dfs(g，j)；finishedj=1；p=p 一next： whilet=(ArrNode*)malloc(sizeof(ArcNode)； Iit 请边结点t 一adjvex=v：t-next=final；final=t； 将该顶点插入链表dfs 结束int dfs_Topsort(Adjlist g)对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回 1，否则返回0i=1：while(flag&i=n)if(visited i=0)dfs(g，i)；finishedi=1； ifreturn(flag)；【知识模块】 数据结构
