1、计算机专业基础综合数据结构（图）历年真题试卷汇编 1 及答案与解析一、单项选择题1 若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则可以断定该图一定_。【北京航空航天大学 2004 年】（A）是无向图（B）是有向图（C）是完全图（D）不是带权图2 设无向图的顶点个数为 n，则该图最多有_条边。【清华大学 1998 年】（A）n 一 1（B） n(n 一 1)2（C） n(n+1)2（D）n 23 执行_操作时，需要使用队列作辅助存储空间。【华中科技大学 2006 年】（A）查找散列表（B）广度优先搜索图（C）先序 (根)遍历二叉树（D）深度优先搜索图4 无向图(加权图) 的邻接矩
2、阵是_矩阵。【华中科技大学 2006 年】（A）下三角（B）上三角（C）稀疏（D）对称5 下列哪一种图的邻接矩阵是对称矩阵?_。【北京交通大学 2001 年】（A）有向图（B）无向图（C） AOV 网（D）AOE 网6 n 个顶点的无向图的邻接表最多有_个表结点。【华中科技大学 2006 年】（A）n 2（B） n(n 一 1)（C） n(n+1)（D）n(n 一 1)27 具有 6 个顶点的无向图，当有_条边时能确保是一个连通图。【华中科技大学2007 年】（A）8（B） 9（C） 10（D）118 以下图的叙述中，正确的是_。【华南理工大学 2005 年】（A）强连通有向图的任何顶点到其他
3、所有顶点都有弧（B）任意图顶点的入度等于出度（C）有向完全图一定是强连通有向图（D）有向图的边集的予集和顶点集的子集可构成原有向图的子图9 具有 n 个顶点的有向完全图有_条边。【湖南大学 2008 年】（A）n(n 一 1)2（B） n(n 一 1)（C） n(n+1)2（D）n(n+1)10 在一个无向图中，所有顶点的度数之和等于所有边数的_倍。【北京邮电大学 2005 年】【北京交通大学 2006 年】（A）3（B） 1（C） 2（D）411 采用邻接表存储的图的广度优先遍历算法类似于二叉树的算法。【华中科技大学 2007 年】（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历12
4、 若某带权图为 G=(V1E1)，其中 V=v1,v2，v 3，v 4，v 5，v 6，v 7，v 8，v 9，v 10)，E=(v1，v 2)5，(v 1，v 3)6， (v2，v 5)3，(v 3，v 5)6，(v 3，V 4)3，(v 4，v 5)3，(v 4，v 7)1，(v 4， v8)4， (v5，v 6)4，(v 5，v 7)2，(v 6，v 10)4，(v 7，v 9)5，(v 8，V 9)2，(v 9，v 10)2)(注：顶点偶对右下角的数据表示边上的权值)，则 G 的关键路径的长度为_。【北京航空航天大学 2002 年】（A）19（B） 20（C） 21（D）2213 已知
5、带权连通无向图 G=(V,E)，其中 V=v1，v 2，v 3，v 4，v 5，v 6，v 7)，E=(v1，v 2)10，(v 1，V 3)2，(v 3，V 4)2，(v 3，v 6)11， (v2，v 5)1，(v 4，v 5)4，(v 4，v 6)6，(v 5,v7)7，(v 6，v 7)3)(注：顶点偶对右下角的数据表示边上的权值) ，从源点 v1 到顶点 v7 的最短路径上经过的顶点序列是_。【北京航空航天大学 2003 年】（A）v 1，v 2，v 5，v 7（B） v1，v 3，v 4，v 6，v 7（C） v1，v 3，v 4，v 5，v 7（D）v 1，v 2，v 5，v 4
6、，v 6，v 714 已知某有向图 G=(V,E)，其中 V=v1，v 2，v 3，v 4，v 5，v 6，E=1， v2， 1，v 4， 2，v 6， 3，v 1， 3，vf 4， 4，v 5， 5，v 2， 5，v 6)，_是G 的拓扑序列。【北京航空航天大学 2004 年】（A）v 3，v 1，v 4，v 5，v 2，v 6（B） v3，v 4，v 1，v 5，v 2，v 6（C） v1，v 3，v 4，v 5，v 2，v 6（D）v 1，v 4，v 3，v 5，v 2，v 615 一个 n 个顶点的连通无向图，其边的个数至少为_。【浙江大学 1999 年】（A）n1（B） n（C） n
7、+1（D）nlogn16 n 个结点的完全有向图含有边的数目为_。【中山大学 1998 年】（A）n*n（B） n(n+1)（C） n2（D）n.(n 1)17 用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是_。【中科院软件所 1998 年】（A）逆拓扑有序（B）拓扑有序（C）无序的17 从邻接阵矩 可以看出，该图共有个顶点；如果是有向图该图共有条弧；如果是无向图，则共有 条边。【中科院软件所 1999 年】18 用相邻矩阵 A 表示图，判定任意两个顶点 vi 和 vi 之间是否有长度为 m 的路径相连，则只要检查_的第 i 行第 j 列的元素是
8、否为零即可。【武汉大学 2000 年】（A）mA（B） A（C） Am（D）A m-119 一个具有 n 个顶点的连通无向图，最少有_条边。【北京邮电大学 2007 年】（A）n 一 1（B） n（C） n(n1)2（D）n(n 1)20 n 个顶点、e 条边的有向图的邻接矩阵中非零元素有_个。【北京交通大学2004 年】（A）n（B） 2e（C） e（D）n+e21 对邻接表的叙述中，_是正确的。【华南理工大学 2006 年】（A）无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的 2 倍（B）邻接表比邻接矩阵的操作更简便（C）邻接矩阵比邻接表的操作更简便（D）求有向图结点的度，
9、必须遍历整个邻接表22 用邻接表存储图所用的空间大小_。【北京交通大学 2006 年】（A）与图的顶点数和边数都有关（B）只与图的边数有关（C）只与图的顶点数有关（D）与边数的平方有关23 若邻接表中有奇数个边结点，则一定是_。【中科院 2007 年】（A）图中有奇数个结点（B）图中有偶数个结点（C）图为无向图（D）图为有向图24 采用邻接表存储的图的深度优先遍历算法类似于树的_，而其广度优先遍历算法类似于树的_。【北京交通大学 2007 年】（A）中序遍历（B）先序遍历（C）后序遍历（D）按层次遍历25 一个连通图的生成树是该图的一个极小连通子图，若这个连通图有 n 个顶点，则它的生成树有_
10、条边。【湖南大学 2008 年】（A）n 一 1（B） n（C） n+1（D）不确定26 以下叙述中，正确的是_。【华南理工大学 2006 年】（A）图与树的区别在于图的边数大于或等于顶点数（B）假设有图 G=V，E)，顶点集 V V，E E，则 V和E 构成 G 的予图（C）无向图的连通分量指无向图中的极大连通子图（D）图的遍历就是从图中某一顶点出发访遍图中其余顶点27 无向图 G=(V,E)，其中：V=a，b，c，d，e ，f，E=(a，b)，(a，e) ，(a，c)，(b，e)，(c，f) ，(f,d)，(e，d)，对该图进行深度优先遍历，得到的顶点序列正确的是_。【南京理工大学 200
11、1 年】（A）a，b， e，c，d，f（B） a，c ，f,e，b，d（C） a，e ，b，c ，f,d（D）a，e，d，f,c，b28 下面哪一方法可以判断出一个有向图是否有环(回路)_。【东北大学 2000 年】（A）深度优先遍历（B）拓扑排序（C）求最短路径（D）求关键路径29 实现图的广度优先搜索算法时，使用的数据结构是_。【电子科技大学 2007年】（A）栈（B）队列（C）十字链表（D）三元组30 当各边上的权值_时，BFS 算法可用来解决单源最短路径问题。【中科院计算所 2000 年】（A）均相等（B）均互不相等（C）不一定相等31 求解最短路径的 Floyd 算法的时间复杂度为_
12、。【合肥工业大学 1999 年】（A）O(n)（B） O(n+c)（C） O(n2)（D）O(n 3)32 在有向图 G 的拓扑序列中，若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是_。【南京理工大学 2000 年】（A）G 中有弧 i，v j（B） G 中有一条从 vi 到 vj 的路径（C） G 中没有弧 i，v j（D）G 中有一条从 vi 到 vj 的路径33 下面关于求关键路径的说法不正确的是_。【南京理工大学 1998 年】（A）求关键路径是以拓扑排序为基础的（B）一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同（C）一个事件的最迟开始时间为以该事件为尾的
13、弧的活动最迟开始时间与该活动的持续时间的差（D）关键活动一定位于关键路径上34 下列关于 AOE 网的叙述中，不正确的是_。【北方交通大学 1999 年】【北京工业大学 1999 年】（A）关键活动不按期完成就会影响整个工程的完成时间（B）任何一个关键活动提前完成，那么整个工程将会提前完成（C）所有的关键活动提前完成，那么整个工程将会提前完成（D）某些关键活动提前完成，那么整个工程将会提前完成35 对 AOE 网的关键路径，下面的说法_是正确的。【华南理工大学 2005 年】（A）提高关键路径上的一个关键活动的速度，必然使整个工程缩短工期（B）完成工程的最短时间是从始点到终点的最短路径的长度（
14、C）一个 AOE 网的关键路径只有一条，但关键活动可有多个（D）任何一项活动持续时间的改变都可能会影响关键路径的改变36 在下列网中，_是边不带权值的图。【华南理工大学 2007 年】（A）邮电图（B） AOV 网（C）公路网（D）AOE 网37 能有效缩短关键路径长度的方法是_。【电子科技大学 2007 年】（A）缩短任意一个活动的持续时间（B）缩短关键路径上任意一个关键活动的持续时间（C）缩短多条关键路径上共有的任意一个关键活动的持续时间（D）缩短所有关键路径上共有的任意一个关键活动的持续时间38 下面有向图(见图 4-1)的所有拓扑序列共有_个。【北京交通大学 2007 年】（A）4（B
15、） 6（C） 5（D）738 从邻接阵矩 可以看出，该图共有个顶点；如果是有向图该图共有条弧；如果是无向图，则共有 条边。【中科院软件所 1999 年】38 从邻接阵矩 可以看出，该图共有个顶点；如果是有向图该图共有条弧；如果是无向图，则共有 条边。【中科院软件所 1999 年】39 （A）9（B） 3（C） 6（D）1（E）以上答案均不正确40 （A）5（B） 4（C） 3（D）2（E）以上答案均不正确41 （A）5（B） 4（C） 3（D）2（E）以上答案均不正确二、综合题42 对右边的无向图(见图 4-2)，按照 Dijkstra 算法，写出从顶点 1 到其他各个顶点的最短路径和最短路径
16、长度。(顺序不能颠倒)【南京大学 2004 年】43 已知一有向图如图 4-3 所示。 【西安电子科技大学 2004 年】1)写出该图的邻接矩阵表示并据此给出从顶点 1 出发的深度优先遍历序列 2)求该有向图的强连通分量数目。3)给出该图的两个拓扑序列。4)若将该图视为无向图，用 Kruskal 算法求最小生成树。44 假定无向图以邻接矩阵形式存储，邻接矩阵的定义如下：#define MAX 20typedef char ElemType ;strUCt MGraphElemType vexsMAX； 顶点数组int arcsMAXMAX； 邻接矩阵int vexnum; 顶点数；试用 C 语
17、言编写算法函数并分析时间复杂度。【华中科技大学 2007 年】1)intDeleteNode(structMGraphG，ElemTypee) ；从图 G 中删除顶点值为 e 的顶点，成功返回 1，否则返回 0。2)intDeleteEdge(strUCtMGraphG，ElemTypea，ElemTypeb)；从图 G 中删除边(a， b)，成功返回 1，否则返回 0。45 为实现村村通工程，某公路局要在以下 7 个核心乡镇修建公路，图 4-4 为乡镇之间已有的土路及距离示意图，请给出一个方案，使得既满足村村通的要求，又使得修建公路的费用最省。【北京交通大学 2006 年】 1)请画出拟修建
18、公路的示意图。2)如果用邻接表存储图 4-4，请画出该数据结构的示意图。3) 请用 c 语言完整定义出示意图所展示的数据结构(请给出必要的注释说明)。46 试对图 4-5 所示的 AOE 网络，解答下列问题。 (图中数字的单位为天)【北京交通大学 2007 年】 1)这个工程最早可能什么时间结束?2)确定哪些活动是关键活动，并给出关键路径。47 已知一具有 n 个顶点的有向图 G=(V，E)采用邻接表存储方法。请写一算法，检查任意给定序列 v1，v 2，v 3，v n(viV，1in)是否为该有向图的一个拓扑序列。若是，算法给出信息 1；否则，给出信息 0。【北京航空航天大学 2005 年】4
19、8 写出从图的邻接表表示转换成邻接矩阵表示的算法，用类 PASCAL 语言(或 C语言)写成过程形式。【南开大学 1998 年】49 编写算法，求有向图 G 中距离顶点 v0 的最短路径长度为 len 的所有顶点。【华南理工大学 2007 年】50 图 4-6 为一个用 AOE 网表示的工程。试回答： 1)完成此工程，至少需要多少时间?2)指出关键路径。 3)哪些活动加速，可以缩短完成工程所需的时间?4)画出此图的邻接表表示。51 试设计一个算法，判断一个无环路有向图 G 中是否存在这样的顶点，该顶点到其他任意顶点都有一条路径可达。52 设无向图 G 已用邻接表结构存储，顶点表为 GLn(n
20、为图中顶点数)，试用“广度优先搜索” 方法，写出求图 G 中各连通分量的 C 语言描述算法：BFSCOM(GL)。(注：算法中可调用队列操作的基本算法)【北京科技大学 2001 年】53 求图的中心点的算法。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为：max从 w 到 v 的最短距离 1w 是 g 中所有顶点，如果 v 是有向图 G 中具有最小偏心度的顶点，则称顶点 v 是 G 的中心点。【中南大学 1998 年】计算机专业基础综合数据结构（图）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 考查图的存储方式。图的邻接矩阵对角线元素必为 0，其余元
21、素全为 1 代表任何两个顶点之间都存在边，也就是完全图。【知识模块】 图2 【正确答案】 B【试题解析】 考查图的基本性质。当图的任意两个顶点之间有一条边时，图有最多的边数。因此每个顶点相连的边有 n 一 1 条，因此一共有 n(n 一 1)2 条边。【知识模块】 图3 【正确答案】 B【试题解析】 考查图的遍历。图的广度优先遍历，从出发点开始，依次访问已访问结点的未被访问的邻接点，为保证“先被访问结点的邻接点”先于“后被访问结点的邻接点”被访问，需在访问结点时将其邻接点依次入队列。【知识模块】 图4 【正确答案】 D【试题解析】 考查图的存储方式。对于无向图的邻接矩阵，每条边对应矩阵的两个关
22、于对角线对称的两个元素的值。【知识模块】 图5 【正确答案】 B【试题解析】 考查图的基本概念和存储方式。对称矩阵意味着，存在 vi 到 vi 的边时，也存在 vi 到 vi 的边。因此答案为 B。【知识模块】 图6 【正确答案】 A【试题解析】 考查图的存储方式。当图的边最多时，邻接表的表结点数目最大。有 n 个顶点的无向图最多有 n(n 一 1)2 条边，每条边对应于邻接表的两个表结点。共 n(n 一 1)个边表结点，加卜几个顶点表结点，共 n2 个表结点。【知识模块】 图7 【正确答案】 D【试题解析】 考查图的基本概念。确保是一个连通图等价于最大边数的非连通图的基础上再加一条边。5 个
23、结点为一个连通分量且具有最多边时即是最大边数的非连通图，所以图非连通时最多有 5(51)2=10 条边。故当有 10+1=11 条边时确保是一个连通图。【知识模块】 图8 【正确答案】 C【试题解析】 考查图的基本概念。强连通有向图的任何顶点到其他所有顶点部有路径，但未必有弧；无向图任意图顶点的入度等于出度，但有向图未必满足：若边集中的某条边对应的某个顶点不在对应的顶点集中，有向图的边集的予集和顶点集的子集无法构成子图。【知识模块】 图9 【正确答案】 B【试题解析】 考查有向完全图的概念。恰有 n(n1)条边的有向图称为有向完全图。【知识模块】 图10 【正确答案】 C【试题解析】 考查无向
24、图边数和度数的关系。无向图中，每条边对应着两个顶点，在计算顶点度数时被计算了两次，所以顶点度数之和等于边数 2 倍。【知识模块】 图11 【正确答案】 D【试题解析】 考查图的遍历。广度优先遍历的基本思想：首先访问起始顶点 v，然后访问与 v 相连的所有顶点 w1、w 2，接着再访问与 w1、w 2相连的顶点，直至所有顶点都被访问。【知识模块】 图12 【正确答案】 C【试题解析】 考查图的关键路径。画出题目所表示的图如图 4-7 所示，则可以得到关键路径的长度为 21。图中所表示的两条路径都是关键路径。【知识模块】 图13 【正确答案】 B【试题解析】 考查图的最短路径。如图 4-8 所示，
25、则 A、B、C 、D 对应的路径长度分别为 18、13、15、24。【知识模块】 图14 【正确答案】 A【试题解析】 考查图的拓扑序列。可列出所有边，观察入度为 0 的顶点，删除该顶点以及以其为始点的边，然后继续寻找入度为 0 的顶点。或者也可以用排除法，从集合 E 中可以得到，v 3 在 v1 前，排除 C、D；v 1 在 v4 前，排除 B。【知识模块】 图15 【正确答案】 A【试题解析】 考查图的基本性质。n 个顶点的连通无向图至少有 n1 条边，n 个顶点的强连通有向图至少有 n 条边。【知识模块】 图16 【正确答案】 D【试题解析】 考查图的基本性质。n 个顶点的完全有向图含有
26、边的数目是 n 个顶点的完全无向图的边数的 2 倍。【知识模块】 图17 【正确答案】 A【试题解析】 考查图的遍历和拓扑排序。设有向图中有顶点 vi，它有后继顶点vj，即存在边 i，v j。根据 DFS 遍历的规则，v i 入栈后，必先遍历完其后继顶点后vi 才会出栈，也就是说 vi 会在 vj 之后出栈，在如题所指的过程中，v i 在 vj 后打印。由于 vi、v j 具有任意性，可以从上面的规律看出，输出顶点的序列是逆拓扑有序序列。【知识模块】 图【知识模块】 图18 【正确答案】 C【试题解析】 考查图的邻接矩阵。先考虑 m=2 的情况，若 vi、v j 之间存在长度为2 的路径，设此
27、路径经过顶点 vk，则存在边 i，v k和 k，v j。因此 Aik 和 Akj 皆不为 0，因此A 2ij=Aik*Aki0。对于 m2 的情况与此类似，故答案为 C。【知识模块】 图19 【正确答案】 A【试题解析】 考查连通无向图最少边数。n 个顶点的无向图，如果要连通，则至少要保证有 n 一 1 条边。【知识模块】 图20 【正确答案】 C【试题解析】 考查邻接矩阵的概念。有向图中，当存在一条从顶点 i 到顶点 j 的边时，邻接矩阵第 i 行第 j 列值不为 0。【知识模块】 图21 【正确答案】 D【试题解析】 考查邻接表和邻接矩阵。无向图的邻接表中，第 i 个顶点的度为第i 个链表
28、中结点数，故 A 不对。邻接表和邻接矩阵对于不同的操作各有优势，B 和C 都不准确。【知识模块】 图22 【正确答案】 A【试题解析】 考查邻接表的概念。邻接表中，对于每个顶点，都有一个顶点表结点；对于边，有边表结点。所用空间跟图的顶点和边数都有关。【知识模块】 图23 【正确答案】 D【试题解析】 考查邻接表的存储方式。无向图中，如果结点 vi 与 vj 相邻，则 vj在 vi 对应的链表中，v i 在 vj 对应的链表中，所以，无向图邻接表中边结点个数一定为偶数，所以题中所述图为有向图。【知识模块】 图24 【正确答案】 A,D【试题解析】 考查图的两种遍历算法与树的遍历算法的比较。深度优
29、先遍历所遵循的搜索策略是尽可能的“深”地搜索一个图。深度优先搜索类似于树的先序遍历。而广度优先遍历始终是将已发现顶点和未发现顶点之间的边界，沿其广度方向扩展，类似于树的层次遍历。【知识模块】 图25 【正确答案】 A【试题解析】 考查连通图生成树的边数。【知识模块】 图26 【正确答案】 C【试题解析】 考查树和图的有关特性。图与树的区别是逻辑上的而不是边数的区别，图的边数也可能小于树的边数，故 A 不对；若 E，中的边对应的顶点不是 V的元素时，V和E)无法构成图，故 B 不对；无向图的极大连通子图称为连通分量，C 正确；图的遍历要求每个结点只能被访问一次， D 的说法不准确。故选 c。【知
30、识模块】 图27 【正确答案】 D【试题解析】 考查图的遍历。根据深度优先的算法可以得到答案。【知识模块】 图28 【正确答案】 B【试题解析】 考查拓扑排序的特点。拓扑排序时，当某顶点不为任何边的头时才能加入序列，存在环路时环路中的顶点一直是某条边的头，不能加入拓扑序列。也就是说，还存在顶点但无法找到下一个可以加入拓扑序列的顶点则说明此图存在回路。【知识模块】 图29 【正确答案】 B【试题解析】 考查广度优先搜索算法。【知识模块】 图30 【正确答案】 A【试题解析】 考查单源最短路径问题。BFS 算法实际求得的是源点到各顶点的路径所经过的边数，因此，各边权值相等时可以用来解决单源最短路径
31、问题。【知识模块】 图31 【正确答案】 D【试题解析】 考查 Floyd 算法的时间复杂度。【知识模块】 图32 【正确答案】 D【试题解析】 考查图的拓扑排序。【知识模块】 图33 【正确答案】 C【试题解析】 考查图的关键路径问题。一个事件的最迟开始时间与以该事件为尾的弧的活动最迟开始时间相同，或者等于最迟结束时间与该活动的持续时间的差。【知识模块】 图34 【正确答案】 B【试题解析】 考查图的关键路径问题。【知识模块】 图35 【正确答案】 D【试题解析】 考查图的关键路径问题。一个 AOE 网可能有不止一条关键路径，因此 A 和 c 不对：完成工程的最短时间是从始点到终点的最长路径
32、的长度，B 不对。【知识模块】 图36 【正确答案】 B【试题解析】 考查图的关键路径问题。每个顶点表示一个活动，用弧表示活动间的优先关系，这样的图记为 AOV 网，因此 AOV 网的边不带权值。【知识模块】 图37 【正确答案】 D【试题解析】 考查图的关键路径问题。关键路径是始点和终点间的最长路径，只有所有关键路径的长度都缩短，整个图的关键路径才能有效缩短，因此只有 D 满足条件。【知识模块】 图38 【正确答案】 C【试题解析】 考查图的拓扑排序。本图的拓扑排序序列有：ABCFDEG、ABCDFEG、ABCDEFG、ABDCFEG、ABDCEFG 。【知识模块】 图【知识模块】 图【知识
33、模块】 图39 【正确答案】 B【知识模块】 图40 【正确答案】 B【知识模块】 图41 【正确答案】 D【试题解析】 考查图的基本概念和存储方式。邻接矩阵的顶点数等于矩阵的行(列)数，有向图的边数等于矩阵中非零元素的个数，无向图的边数等于矩阵中非零元素个数的一半。【知识模块】 图二、综合题42 【正确答案】 根据 Dijkstra 算法，求从顶点 1 到其余各顶点的最短路径见表 4-1。【知识模块】 图43 【正确答案】 1)该图的邻接矩阵如下： 深度优先遍历序列为：1，2，3，5，7，4，6。2)当某项点只有出弧没有入弧时，其他顶点无法到达这个顶点，不可能与其他顶点和边构成强连通分量。顶
34、点 1 无入弧构成第一个强连通分量。删除顶点 1 及所有以之为尾的弧。顶点 2 无入弧构成一个强连通分量。删除顶点 2 及所有以之为尾的弧。依次类推，可以最后得到，每个顶点都是一个强连通分量，所以强连通分量的数目为 7。3)该图的两个拓扑序列如下：1，2，4， 6，3，5，7 。 1，4，2，6，3，5， 7。4)若视该图为无向图，用Kruskal 算法生成最小生成树的过程如图 4-9 所示。得到的最小生成树如图410 所示。【知识模块】 图44 【正确答案】 1)算法的基本设计思想：查找值为 e 的顶点，若未找到则返回0，找到则进行后面的处理。找到值为 e 的顶点之后，删除顶点数组中的顶点。
35、根据顶点对应的下标，删除邻接矩阵中对应的行和列。 顶点数的值自减 1。算法的代码：int DeleteNode(struct MGraphG，ElemType e)从图 G 中删除顶点值为 e 的顶点，成功返回 1，否则返回 0。可删除多个值为 e 的顶点int i，J t k；for(i=0； ii)都不存在 vj 到 vi 的路径。当删除 vi 前所有顶点及以之为尾的弧后，不存在任何以 vi 为尾的弧。算法的实现过程如下： 设置变量 vj，令其等于vi。遍历邻接表，检查是否存在表结点为 vj。若不存在，则执行下一步，否则返回 0。删除以 vj 为表头的表。若未到序列末，令 vj 为序列中下
36、一顶点，并执行步骤；否则返回 1。算法的代码： int CheckTopo(ALGraphG ，vexElemV) 检查顶点数组 v 中的序列是否为该图的一个拓扑序列 int i，j ； vexElem vj ; ArcNode*p， *q; for(i=0； iverticesj)firstarc; while(P!=NULL) 遍历边链表。找到序列中当前顶点，说明序列不是拓扑序列 if(vj=Pdata) return 0； P=P 一next： for(J=0;JverticesJ) p=(G 一verticesJ)firstarc ; while(p !=NULL) 遍历边链表，删除各
37、边结点 q=p; p=p 一next； free(q)， (G 一verticesj)，firstarc=NULL； 【知识模块】 图48 【正确答案】 算法的基本设计思想：设图的顶点分别存储在 vn数组中。首先初始化数据结构，定义出邻接矩阵。遍历邻接表，在遍历顶点 vi的边链表时，修改邻接矩阵的第 i 行的元素值。若链表边结点的值为 j，则修改 arcsiU=1。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图同样适用。算法的代码：VOid Convert(ALGraphG，arcs) 此算法将邻接表方式表示的图 G 转换为邻接矩阵 arcs设图有 n 个项点，图为带权图int i
38、;for(i=0；iverticesi)firstarc；while(p!=NULL) 遍历边链表arcsip 一data=1；P=P 一next； Convert【知识模块】 图49 【正确答案】 算法的基本设计思想：直接使用单源最短路径算法Dijkstra计算各顶点到 v0 的最短距离，然后找到距 v0 为 len 的顶点即可。算法的代码：void ShortestPathDIJ(MGraph G，int v0，int 1en)(全局变量 dist、path及 final。distv存放从 v0 到 v 的最短路径长度。pathvw为 1，则 w 是从 v0 到 v 当前求得最短路径上的顶点finalv 为 1 当且仅当 vS，即已求得从 v0 到 v 的最短路径for(int v=0；vGvexnum；v+)finalV=0;distv=Garcv0v；for(w=0;wGvexnum；w+)pathVW=0; 设空路径if(diStvINFINITY)fpathvv0=1;pathvv=1; fordistvO=0；finalv0=1; 初始化，v0 顶点属于 S 集开始主循环，每次求得 vO 到某个 v 顶点的最短路径，并加 v 到 S 集
