1、计算机学科专业基础综合数据结构-图(一)及答案解析(总分：96.00，做题时间：90 分钟)一、B单项选择题/B(总题数：13，分数：26.00)1.设无向图的顶点个数为 n，则该图最多有U /U条边。 A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.0 E.n2（分数：2.00）A.B.C.D.E.2.n个结点的完全有向图含有边的数目U /U。 A.n*n B.n(n+1) C.n/2 D.n*(n-1)（分数：2.00）A.B.C.D.3.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为U /U。 A.O(n) B.O(n+e) C.O(n2) D.O(n3)（
2、分数：2.00）A.B.C.D.4.若一个图的边集为(A，B)， (A，C)， (B，D)， (C，F)， (D，E)， (D，F)，则从顶点 A开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。 A.A，B，C，D，E，F B.A，B，C，F，D，E C.A，B，D，C，E，F D.A，C，B，F，D，E（分数：2.00）A.B.C.D.5.已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4，V5，V6，V7，E=V1，V2，V1，V3，V1，V4，V2，V5，V3，V5，V3V6，V4，V6，V5，V7，V6，V7)，G 的拓扑序列是U /U。 A.V1，V3，V4，V6
3、，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V4，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7（分数：2.00）A.B.C.D.6.当一个有 N个顶点的图用邻接矩阵 A表示时，顶点 Vi的度是U /U。 （分数：2.00）A.B.C.D.7.无向图 G=(V，E)，其中：V=a，b，cd，e，f，E=(a，b)， (a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(ed)，对该图进行深度优先遍历，得到的顶点序列正确的是U /U。 A.a，b，e，c，d，f B.a，c，f，e，b，d C.a，e，b，c，f，d D.a，e
4、，d，f，c，b（分数：2.00）A.B.C.D.8.已知一个有向图的边集为a，b，a，c，a，d，b，d，b，e，d，e，则由该图产生的一种可能的拓扑序列为U /U。 A.a，b，c，d，e B.a，bd，e，b C.a，c，b，e，d D.a，c，d，b，e（分数：2.00）A.B.C.D.9.若一个图的边集为1，2，1，4，2，5，3，1，3，5，4，3)，则从顶点 1开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。 A.1，2，3，4，5 B.1，2，4，3，5 C.1，2，4，5，3 D.1，4，2，5，3（分数：2.00）A.B.C.D.10.设有向无环图 G中的有向边集
5、合 E=1，2，2，3，3，4，1，4)，则下列属于该有向图 G的一种拓扑排序序列的是U /U。 A.1，2，3，4 B.2，3，4，1 C.1，4，2，3 D.1，2，4，3（分数：2.00）A.B.C.D.11.设有 6个结点的无向图，该图至少应有U /U条边才能确保是一个连通图。 A.5 B.6 C.7 D.8（分数：2.00）A.B.C.D.12.设用邻接矩阵 A表示有向图 G的存储结构，则有向图 G中顶点 i的入度为U /U。 A.第 i行非 0元素的个数之和 B.第 i列非 0元素的个数之和 C.第 i行 0元素的个数之和 D.第 i列 0元素的个数之和（分数：2.00）A.B.C
6、.D.13.设如图所示，在下面的 5个序列中，符合深度优先遍历的序列有U /U个。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5 B4 C3 D2 （分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：7，分数：70.00)14.对有 5个结点A，B，C，D，E)的图的邻接矩阵 （分数：10.00）_15.已知连通图如下： (1)若从顶点 B出发对该图进行遍历，分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列； (2)写出按深度优先搜索的递归程序。（分数：10.00）_16.设有数据逻辑结构为： B
7、=(K，R)，K=k1，k2，k9 R=k1，k3，k1，k8，k2，k3，k2，k4，k2，k5，k3，k9，k5，k6，k8，k9，k9，k7，k4，k7，k4，k6 (1)画出这个逻辑结构的图示。 (2)相对于关系 r，指出所有的开始接点和终端结点。 (3)分别对关系 r中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。（分数：10.00）_17.下图是带权的有向图 G的邻接表表示法，求：（分数：10.00）_18.欲用 4种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色(点相交不算相邻)。 (1)试用一种数据结构表示地图上各国相邻的关系
8、； (2)描述涂色过程的算法。(不要求证明)（分数：10.00）_19.下表给出了某工程各工序之间的优先关系和各工序所需时间： 工序代号 A B C D E F G H I J K L M N所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驱工作 A，B B C，D B E G，I E I F，IH，J，K L G(1)画出相应的 AOE网；(2)列出各事件的最早发生时间、最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。（分数：10.00）_20.已知无向图 G=(V，E)的邻接表，给出求图 G的连通分量个数的算法。（分数：10.0
9、0）_计算机学科专业基础综合数据结构-图(一)答案解析(总分：96.00，做题时间：90 分钟)一、B单项选择题/B(总题数：13，分数：26.00)1.设无向图的顶点个数为 n，则该图最多有U /U条边。 A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.0 E.n2（分数：2.00）A.B. C.D.E.解析：无向图 G中边数目的取值范围：0=e=n(n 一 1)/2。有 n(n-1)/2条边的无向图称为完全图。2.n个结点的完全有向图含有边的数目U /U。 A.n*n B.n(n+1) C.n/2 D.n*(n-1)（分数：2.00）A.B.C.D. 解析：有向图 G中弧数目的
10、取值范围：0=e=n(n-1)。有 n(n-1)条弧的有向图称为有向完全图。3.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为U /U。 A.O(n) B.O(n+e) C.O(n2) D.O(n3)（分数：2.00）A.B. C.D.解析：设 N一V，E是连通网，TE 是最小生成树中边的集合，初始为空。定义一个仅含一个顶点的集合 U=u0)，u 0V(u 0可从顶点集合 V中任意选取)，则将 N中的所有顶点分成了两个集合：U，VU。重复执行以下操作：在所有的 uU，vV 决定的边(u，v)E)中寻找一条代价最小的边(u 0，v 0)，将该边并入 TE集合，同时 v0并入 U
11、，直到 U=V为止。以上操作，通俗地讲，实际上是从两大阵营(两个图的顶点的集合)中寻找一条最短的路。Prim 算法中，最小代价生成树的顶点和边都是逐步生成的，开始的时候顶点集合中有一个顶点，边的集合为空。4.若一个图的边集为(A，B)， (A，C)， (B，D)， (C，F)， (D，E)， (D，F)，则从顶点 A开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。 A.A，B，C，D，E，F B.A，B，C，F，D，E C.A，B，D，C，E，F D.A，C，B，F，D，E（分数：2.00）A.B.C.D. 解析：对图的广度优先遍历方法描述为：从图中某个顶点 v出发，在访问该顶点 v
12、之后，依次访问 v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。5.已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4，V5，V6，V7，E=V1，V2，V1，V3，V1，V4，V2，V5，V3，V5，V3V6，V4，V6，V5，V7，V6，V7)，G 的拓扑序列是U /U。 A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V4，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7（分数：2.00）A. B.C.D.
13、解析：在给定的有向图 G中，若顶点序列 vi1，v i2，v in满足下列条件：若在有向图 G中从顶点 vi到顶点 vj有一条路径，则在序列中顶点 vi必在顶点 vj之前，便称这个序列为一个拓扑序列。6.当一个有 N个顶点的图用邻接矩阵 A表示时，顶点 Vi的度是U /U。 （分数：2.00）A.B. C.D.解析：邻接矩阵法是图的一种顺序存储结构。设 G有 n个顶点，则可用 n*n矩阵 A(称为 G的邻接矩阵，行标从 1n，列标从 1n)保存该有向图。对无向图：如果 vi，v j之间有边，则 A的元素 aij=aji=1，否则 aij=aji=0；A 为对称矩阵。对有向图：如果 vi有指向
14、vj的弧，则 A的元素 aij=1，否则 aij=0。对带权图：如果 vi，v j之间有边或者弧(v i指向 vj)，则 A的元素 aij=wij，否则 aij=INFINITY。利用邻接矩阵，可以判断任意两顶点之间是否有边(弧)，并可方便求各顶点的度，图的边数等。例如：对无向图：顶点 vi的度 TD(vi)是 A中第 i行(或者第 i列)的元素之和。对有向图：顶点 vi的出度 OD(vi)是第 i行的的元素之和，入度 ID(vi)是第 i列的元素之和。对带权图：顶点 vi的度的求法同上类似，但不再是求和，而是求行、列中不为零的元素个数。7.无向图 G=(V，E)，其中：V=a，b，cd，e，
15、f，E=(a，b)， (a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(ed)，对该图进行深度优先遍历，得到的顶点序列正确的是U /U。 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，b（分数：2.00）A.B.C.D. 解析：深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点 v出发，访问该顶点，然后依次从 v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与 v有路径相通的顶点都被访问完为止。8.已知一个有向图的边集为a，b，a，c，a，d，b，d，b，e，d，e，则由该图产
16、生的一种可能的拓扑序列为U /U。 A.a，b，c，d，e B.a，bd，e，b C.a，c，b，e，d D.a，c，d，b，e（分数：2.00）A. B.C.D.解析：解析见 5。9.若一个图的边集为1，2，1，4，2，5，3，1，3，5，4，3)，则从顶点 1开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。 A.1，2，3，4，5 B.1，2，4，3，5 C.1，2，4，5，3 D.1，4，2，5，3（分数：2.00）A.B.C. D.解析：解析见 710.设有向无环图 G中的有向边集合 E=1，2，2，3，3，4，1，4)，则下列属于该有向图 G的一种拓扑排序序列的是U /U。
17、 A.1，2，3，4 B.2，3，4，1 C.1，4，2，3 D.1，2，4，3（分数：2.00）A. B.C.D.解析：解析见 5。11.设有 6个结点的无向图，该图至少应有U /U条边才能确保是一个连通图。 A.5 B.6 C.7 D.8（分数：2.00）A. B.C.D.解析：图的连通性：如果从顶点 v到 u有路径，则称为 v和 u是连通的。连通图：对图 G中任何两个顶点，如果是连通的，则称 G为连通图。对有向图来说，如果每对顶点之间v到 u、u 到 v都是连通的，则称该有向图为强连通图。连通分量和极大连通子图：虽然无向图 G本身不连通，但是 G一般都有极大连通子图(也是连通的)，称为
18、G的连通分量。有向图的极大连通子图称为 G的强连通分量，如下图所示。(所谓“极大”，是指再向G的这个子图增加一个顶点，该子图就不再是连通图了。)*(2)连通图的生成树问题：连通图中两顶点之间的路径可能有多条，如果保持顶点个数不变，而是通过删减边/弧的方法使得两个顶点之间只有一条路径，则生成的图称为原图的极小连通子图，又称为原图的生成树。如下图：*说明：生成树实际上就是一棵树，是一种没有环路的连通图。如果再增加一条边，则一定生成环路。生成树如果有 n个顶点，则一定有 n-1条边。如果 G1是一个具有 n个顶点的连通无向图，那么 G1最多 n(n-1)/2条边，最少 n一 1条边。如果 G2是一个
19、具有 n个顶点的强连通有向图，那么 G2最多 n(n-1)条边，最少 n条边。如果 G3是一个具有 n个顶点的弱连通有向图，那么 G3最多 n(n-1)条边，最少 n-1条边。12.设用邻接矩阵 A表示有向图 G的存储结构，则有向图 G中顶点 i的入度为U /U。 A.第 i行非 0元素的个数之和 B.第 i列非 0元素的个数之和 C.第 i行 0元素的个数之和 D.第 i列 0元素的个数之和（分数：2.00）A.B. C.D.解析：对有向图：顶点 vi的出度 OD(vi)是第 i行的元素之和，入度 ID(vi)是第 i列的元素之和。13.设如图所示，在下面的 5个序列中，符合深度优先遍历的序
20、列有U /U个。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5 B4 C3 D2 （分数：2.00）A.B.C.D. 解析：解析见 7。可知 a e b d f c，a e f d b c 符合深度优先搜索条件。二、B综合应用题/B(总题数：7，分数：70.00)14.对有 5个结点A，B，C，D，E)的图的邻接矩阵 （分数：10.00）_正确答案：(如图所示：*(2)深度优先遍历序列：ABCDE；广度优先遍历序列：ABCED(3) 顶点 A B C D EVe(i) 0 100 30 50 10V1(i) 0 1
21、00 60 90 40所以，关键路径 AB(长 100)。解析：如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权的有向图称为边活动网(Activity on edge network)，简称 AOE网。顶点表示一个事件；顶点的入边表示该事件发生所需的活动；顶点的出边表示当该事件发生后，后续的活动都可以开展了。AOE网中有些活动可以并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度，路径长度为路径上各边的权值之和。把开始顶点到完成顶点的最长路径称为关键路径。几个相关的概念：*e(i)：活动 ai的最早开始时间；*1(i)：活动 ai
22、的最迟开始时间；*ve(j)：事件的最早发生时间；*v1(j)：事件的最迟发生时间；*源点：入度为零的顶点；*汇点：出度为零的顶点。关键活动：关键活动就是 e(i)=l(i)的活动。l(i)-e(i)表示完成活动 ai的时间余量，是在不延误工期的前提下，活动 ai可以延迟的时间。关键路径算法：*输入 e条弧，建立 AOE网的存储结构。*从源点 v0出发，令 ve(0)=0求 ve(i) 1=i=n-1。*从汇点 vn出发，令 v1(n-1)=vc(n-1)，求 v1(i) 2=i=n-2。k根据各顶点的 ve和 v1值，求每条弧 s的最早开始时问 e(s)和最迟开始时间 l(s)。若某条弧 e
23、(s)=l(s)，则为关键活动。注意：求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。算法分析：设 AOE网有 n个顶点、e 条边，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O(n+e)，因此，求关键路径算法的时间复杂度为 O(n+e)。)解析：15.已知连通图如下： (1)若从顶点 B出发对该图进行遍历，分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列； (2)写出按深度优先搜索的递归程序。（分数：10.00）_正确答案：(1)在邻接点按升序排列
24、的前提下，其深度优先搜索和广度优选搜索序列分别为 BADCEF和BACEDF。(2) void dfs(v)i=GraphLocateVertex(g，v)； 定位顶点visitedi=1；printf(v)； 输出顶点信息p=gifirstarc；while(p)if(visitedpadjvex=0)dfs(gpadjvexvertex)；p=pnext；void traver()深度优先搜索的递归程序；以邻接表表示的图 g是全局变量。for(i=1；i=n；i+)visitedi=0；访问数组是全局变量初始化。for(vi=v1；v i=v n；v i+)if(visitedGraphL
25、ocateVertex(g，v i)=0)dis(vi)；)解析：16.设有数据逻辑结构为： B=(K，R)，K=k1，k2，k9 R=k1，k3，k1，k8，k2，k3，k2，k4，k2，k5，k3，k9，k5，k6，k8，k9，k9，k7，k4，k7，k4，k6 (1)画出这个逻辑结构的图示。 (2)相对于关系 r，指出所有的开始接点和终端结点。 (3)分别对关系 r中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。（分数：10.00）_正确答案：(1)*(2)开始结点(入度为 0)K1，K2，终端结点(出度为 0)K6，K7。(3)拓扑序列 K1，
26、K2，k3，k4，k5，k6，k8，k9，k7k2，k1，k3，k4，k5，k6，k8，k9，k7规则：开始结点为 k1或 k2，之后，若遇多个入度为 0的顶点，按顶点编号顺序选择。(4)邻接表和逆临接表：*)解析：17.下图是带权的有向图 G的邻接表表示法，求：（分数：10.00）_正确答案：(1)V 1，V 2，V 3，V 8，V 5，V 7，V 4，V 6(2)V1，V 2，V 4，V 6，V 3，V 5，V 7，V 8(3)V1到 V8的最短路径是 56，路径为 V1V2V5V7V8(4)*V1到 V8的关键路径是 V1V6V5V3V8，长 97。)解析：18.欲用 4种颜色对地图上的
27、国家涂色，有相邻边界的国家不能用同一种颜色(点相交不算相邻)。 (1)试用一种数据结构表示地图上各国相邻的关系； (2)描述涂色过程的算法。(不要求证明)（分数：10.00）_正确答案：(地图涂色问题可以用“四染色”定理。将地图上的国家编号(1 到 n)，从编号 1开始逐一涂色，对每个区域用 1色，2 色，3 色，4 色(下称“色数”)依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若 1至 4色均与相邻某区域重色，则需退栈回溯，修改栈顶区域的颜色。用邻接矩阵数据结构 Cnn描叙地图上国家间的关系。n 个国家用 n阶方阵表示，若第i个国家与第 j个国家相邻
28、，则 Cij=1，否则 Cij=0。用栈 s记录染色结果，栈的下标值为区域号，元素值是色数。 void MapColor(AdjMatrix C)以邻接矩阵 C表示的 n个国家的地区涂色 int s； 栈的下标是国家编号，内容是色数 s1=1； 编号 01的国家涂 1色 i=2；j=1；i 为国家号，j 为涂色号 while(i=n) while(j=4&i=n) k=1； k 指已涂色区域号 while(ki&sk*Cik!=j) k+； 判断相邻区是否已涂色 if(ki) j=j+1；用 j+1色继续试探 else si=j； l+： j=1； 与相邻区不重色，涂色结果进栈，继续对下一区涂
29、色进行试探 if(j4) 1： j=si+1； /变更栈顶区域的颜色 )解析：19.下表给出了某工程各工序之间的优先关系和各工序所需时间： 工序代号 A B C D E F G H I J K L M N所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驱工作 A，B B C，D B E G，I E I F，I H，J，K L G(1)画出相应的 AOE网；(2)列出各事件的最早发生时间、最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。（分数：10.00）_正确答案：(AOE 网如右图*图中虚线表示在时间上前后工序之间仅是接续顺序关系
30、不存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点 1代表工程开始事件，顶点 11代表工程结束事件。(2)各事件发生的最早和最晚时间如下表： 事件 1 2 3 4 5 6 7 8 9 10 11 12最早发生时间 0 15 10 65 50 80 200380395425445420最晚发生时间 0 15 57 65 380 80 335380395425445425(3)关键路径为顶点序列：1246891011；事件序列：ACEGHLM，完成工程所需的最短时间为 445。)解析：20.已知无向图 G=(V，E)的邻接表，给出求图 G的连通分量个数的算法。（分数：10
31、.00）_正确答案：(struct ArcNode int adjvex； ArcNode*nextarc； InfoType*info； ； typedef struct VertexType data； ArcNode*firstarc； VNode，AdjListMAX_VERTEX_NUM struct ALGraph AdjList adjlist； int n，e； ALGraph； static int visited En； void dfs(ALGraph g，int V)；int dfscount(ALGraph g) int i，j；j=0； for(i=0；ign；i+) if(visited=0) j+； dfs(g，i)； viod dfs(ALGraph g，int V) ArcNode*P；： visited v=1： p=g-adjlistvfirstarc； while(P!=Null) if(visitedp-adjvex=0) dfs(g，padjvex)； P=pnextarc；) )解析：
