[考研类试卷]计算机专业基础综合（图）模拟试卷4及答案与解析.doc

1、计算机专业基础综合（图）模拟试卷 4 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在有向图 G 的拓扑序列中，若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是( )。（A）G 中有弧v i，v j（B） G 中有一条从 vi 到 vj 的路径（C） G 中没有弧v i，v j（D）G 中有一条从 vj 到 vi 的路径2 以下关于图的说法中正确的是( )。I一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关无向图的邻接矩阵

2、一定是对称的，有向图的邻接矩阵一定是不对称的（A）I，（B） ，（C） I，（D）仅有3 下列关于AOE 网的叙述中，不正确的是( )。（A）关键活动不按期完成就会影响整个工程的完成时间（B）任何一个关键活动提前完成，那么整个工程将会提前完成（C）所有的关键活动提前完成，那么整个工程将会提前完成（D）某些关键活动提前完成，那么整个工程将会提前完成4 一个二部图的邻接矩阵 A 是一个( )类型的矩阵。（A）nn 矩阵（B）分块对称矩阵（C）上三角矩阵（D）下三角矩阵5 求解最短路径的 Floyd 算法的时间复杂度为( )。（A）O(n)（B） O(n+c)（C） O(n2)（D）O(n 3)6

3、下列 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，C67 如果具有 n 个顶点的图是一个环，则它有( )棵生成树。（A）n 2（B） n（C） n 一 1（D）18 如下图所示，在下面的 5 个序列中，符合深度优先遍历的序列有( )个。 aebfdc acfdebaedfcbaefdbc aecfdb（A）5（B） 4（C） 3（D）29 无向图 G 有 23 条边，度为 4

4、的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有( )个顶点。（A）11（B） 12（C） 15（D）1610 对 AOE 网络中有关关键路径的叙述中，正确的是( )。（A）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间（B）从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间（C）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间（D）从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间11 以下关于图的叙述中，正确的是( )

5、。（A）强连通有向图的任何顶点到其他所有顶点都有弧（B）图与树的区别在于图的边数大于或等于顶点数（C）无向图的连通分量指无向图中的极大连通子图（D）假设有图 G=V，E，顶点集 VV，EE，则 V和E 构成 G 的子图12 假设有 n 个顶点 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为( ) 。（A）O(n)（B） O(e)（C） O(n+e)（D）O(ne)13 若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 的结点数至少是( ) 。（A）11（B） 10（C） 9（D）814 已矢口有向图 G=(V， A)，其中 V=a，b

6、，c，d，e，A=， ， 。对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。（A）a，d， c，b，e（B） d，a，b，c ，e（C） a，b，d，c ，e（D）a，b， c，d，e15 用有向无环图描述表达式(A+B)*(A+B) A)，至少需要顶点的数目为( )。（A）5（B） 6（C） 8（D）916 邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示： 关于图中各个域的说明，不正确的是( )。（A）vettex 存储的是结点的数值域的内容（B） firstedge 域指示第一条依附于该顶点的边（C） ma

7、rk 指向下一条依附于结点的边（D）info 为指向和边相关的各种信息的指针域17 以下关于十字链表的说法中，不正确的是( )。（A）十字链表是有向图的另一种链式存储结构（B）行指针 row 为矩阵中的行位置，列指针 col 为矩阵中的列位置（C）数值 val 为矩阵中的值（D）right 指针指向矩阵中的行位置，down 指针指向矩阵中的列位置二、综合应用题41-47 小题，共 70 分。18 对于如下的加权有向图，给出算法 Dijkstra 产生的最短路径的支撑树，设顶点A 为源点，并写出生成过程。 19 (1)对于有向无环图，叙述求拓扑有序序列的步骤。 (2)对于以下的图，写出它的4 个

8、不同的拓扑有序序列。 20 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij) 。( 注意：算法中涉及的图的基本操作必须在存储结构上实现。)21 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)22 已有邻接表表示的有向图，请编程判断从第 u 顶点至第 v 顶点是否有简单路径，若有则打印出该路径上的顶点。23 “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“ 破圈法 ”求解给定的带权连通

9、无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)24 设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为：MAx从 w 到 v 的最短距离|w 属于 V(G)如果 v 是有向图 G 中具有最小偏心度的顶点，则称顶点 v 是 G 的中心点。25 对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减 1，并对其未访问的、入度为 0 的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义。(2)定义在算法中使用的全局辅

10、助数组。(3)写出在遍历图的同时进行拓扑排序的算法。计算机专业基础综合（图）模拟试卷 4 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点vi 与顶点 vj 有一条弧，则拓扑序列中顶点 vi 必在顶点 vj 之前。若有一条从 vj 到 vi的路径，则顶点 vi 不可能在顶点 vj 之前。所以应选 D。【知识模块】 图2 【正确答案】 A【试题解析】 说法 I 是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都

11、等于有向图中的边的个数。 说法是正确的，邻接矩阵的空间复杂度为 D(n2)，与边的个数无关。 说法是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。【知识模块】 图3 【正确答案】 B【试题解析】 此题考查的知识点是图的关键路径。在 AOE 网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。关键路径上的活动称为关键活动。A 、C 、D 的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选 B。【知识模块】 图4 【正确答案】 B【试题解析】 此题考查的知识点是二部图的定义与存储。

12、二部图定义为：若能将无向图 G=的顶点集 V 划分成两个子集 V1 和 V2(V1V2= )，使得 G 中任何一条边的两个端点一个属于 V1，另一个属于 V2，则称 G 为二部图。由于其特点，其存储矩阵必为分块对称的，所以选 B。【知识模块】 图5 【正确答案】 D【知识模块】 图6 【正确答案】 D【试题解析】 考查拓扑排序的算法。 以 l 开头的拓扑排序过程，如下图所示： 以 5 开头的拓扑排序过程，答案中的过程如下图所示： 【知识模块】 图7 【正确答案】 B【试题解析】 因为 n 个顶点构成的环共有 n 条边，去掉其中任意一条便是一棵生成树，共有 n 种情况，所以可以有 n 棵不同的生

13、成树。【知识模块】 图8 【正确答案】 D【试题解析】 本题中，符合深度优先遍历顺序的是 1 和 5，其他三个序列均不符合。【知识模块】 图9 【正确答案】 D【试题解析】 由于在具有 n 个顶点 e 条边的无向图中，有 故可求得度为 2 的顶点数为 7 个，从而最多有 16 个顶点。【知识模块】 图10 【正确答案】 A【试题解析】 本题考查关键路径的定义。关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。关键活动：关键路径上的活动称为关键活动。【知识模块】 图11 【正确答案】 C【试题解析】 强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A 错误。图与树的区别

14、是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若 E中的边对应的顶点不是 V中的元素时，则 V和E无法构成图，D 错误。【知识模块】 图12 【正确答案】 C【试题解析】 删除与某顶点 v 相关的所有边的过程如下：先删除下标为 v 的顶点表结点的单链表，出边数最多为 n1，对应时间复杂度为 O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为 O(e)。故总的时间复杂度为 O(n+e)。【知识模块】 图13 【正确答案】 B【试题解析】 n 个顶点构成的无向图中，边数 n(n 一 1)2，将 e=36 代入，有n9，现已知无向图是非连通的，则 n 至少为 10。【知识模块

15、】 图14 【正确答案】 D【试题解析】 选项 D 中，删去 a、b 及其对应的出边后，c 的入度不为 0，因此有边 ，故不是拓扑序列。选项 A、B、C 均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。【知识模块】 图15 【正确答案】 A【试题解析】 此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的 5 个字符作为 5 个顶点，其中A+B 和 A 可共用，所以至少 5 个即可，选 A。【知识模块】 图16 【正确答案】 C【试题解析】 顶点表由两个域组成，vertex 域存储和该顶点相关的信息，firstedge 域指示第一条依

16、附于该顶点的边。边表结点由六个域组成：mark 为标记域，用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于项点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边；info 为指向和边相关的各种信息的指针域。【知识模块】 图17 【正确答案】 D【试题解析】 right 指向右侧的一个非零元素，down 指向下侧的一个非零元素。【知识模块】 图二、综合应用题41-47 小题，共 70 分。18 【正确答案】 顶点 A 到顶点 B、C、D、E 的最短路径依次是 3、18、38、43，按 Dijkstra 所选顶点过程

17、是 B、C、D、E。支撑树的边集合为， ，具体分析如下表所示。 提示：此题考查的知识点是最短路径。【知识模块】 图19 【正确答案】 (1)对有向图，求拓扑序列步骤为：在有向图中选一个没有前驱(即入度为零) 的顶点并输出。在图中删除该顶点及所有以它为尾的弧。重复和步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。(2)从入度为 0 的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。从顶点 1 开始的可能的拓扑序列为12345678、12354678、13456278、13546278。提示：此题考查的知识点是拓扑排序。【知识模块】 图20

18、 【正确答案】 算法 1： int visited=0； 全局变量，访问数组初始化 int dfs(AdjList g，vi) 以邻接表存储的有向图 g，判断 vi 到 vj 是否有通路，返回1 或 0 visitedvi=1； visited 是访问数组，设顶点的信息就是顶点编号 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： while if(!flag)return(0)； 算法 2：输出

19、vi 到 vj 的路径，其思想是用一个栈存放遍历的顶点，遇到顶点 vj 时输出路径。 void dfs(AdjList g，int i) 顶点 vi 和顶点 vj 问是否有路径，如有，则输出 int top=0，stack； stack 是存放顶点编号的栈 visitedi=1 ； visited 数组在进入 dfs 前已初始化 stack+top=i； p=gifirstarc； 求第一个邻接点 while(p) if(P 一adjvex=j) stack+top=j； printf(“顶点 vi 和 vj 的路径为：n”)； for(i=1；iadjvex=0)dfs(g，g 一adjve

20、x)；top-；P=p 一next； 算法 3：非递归算法求解。 int Judge(AdjList g，int i，j) 判断 13个顶点以邻接表示的有向图 g 中，顶点 vi 各 vj 是否有路径， 有则返回 1，否则返回 0。 for(i=1；i0) k=stacktop-；p=gkfirstarc； while(P!=null&visitedp 一adjvex=1)P=p-next； 查第 k个链表中第一个未访问的弧结点 if(p=null)top- ： else i=p 一adjvex； if(i=j)return(1)； 顶点 vi 和 vj 间有路径 elsevisitedi=1

21、；stack+top=i； while return(0)； 顶点 vi 和 vj 间无通路 提示：此题考查的知识点是图的遍历。在有向图中，判断顶点 vi 和顶点 vj 间是否有路径，可采用搜索的方法，从顶点 vi 出发，不论是深度优先搜索(DFS)还是宽度优先搜索 (BFS)，在未退出 DFS 函数或BFS 函数前，若访问到 vj，则说明有通路，否则无通路。设一全程变量 flag，初始化为 0，若有通路，则 flag=1。【知识模块】 图21 【正确答案】 用邻接矩阵存储时，可用以下方法实现：void Print(int v，int start)输出从顶点 start 开始的回路for(i=

22、1；i0|p)p=gstopfirstarc； 第一个邻接点while(p!=null&visitedp 一adjvex=1)P=p 一next； 下一个访问邻接点表if(p=null)top-； 退栈elsei=p 一adjvex； 取邻接点(编号)if(i=v) 找到从 u 到 v 的一条简单路径，输出for(k=1；k=n) 破圈，直到边数 e=nlif(connect(k) 删除第 k 条边若仍连通edgekw=0；eg 一一； 测试下一条边 edgek，权值置 0 表示该边被删除k+； 下条边 whileconnect()是测试图是否连通的函数，可用 DFS 函数或 BFS 函数实现

23、，若是连通图，一次进入 DFS 函数或 BFS 函数就可遍历完全部顶点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈” 结束后，可输出 edge 中W 不为 0 的 n 一 1 条边。提示：此题考查的知识点是最小生成树的定义。连通图的生成树包括图中的全部n 个顶点和足以使图连通的 n 一 1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删，直到剩 n1 条边为止。【知识模块】 图24 【正确答案】 设 C 是有向图 G

24、的邻接矩阵，求最小偏心度的顶点的步骤如下：(1)利用 Floyd 算法求出每对顶点之间的最短路径矩阵 A；(2)对矩阵 A 求出每列 i 的最大值，得到顶点 i 的偏心度；(3)在这 n 个顶点的偏心度中，求出最小偏心度的顶点 k，即为图 G 的中心点。对应的算法如下：int Center(MGraph&G)int AMAXVMAXV，BMAXV ；int i，j，k，m；for(i=0；iadjvex；if(visitedj=1&finishedj=0)flag=0； dis 结束前出现回边else if(visitedj=0)dfs(g，j)；finishedj=1；p=p 一next：

25、whilet=(AreNode*)malloc(sizeof(AreNode)； 申请边结点t-adjvex=v；t-next=final；final=t ； 将该顶点插入链表dfs 结束im dfs_Topsort(Adjlist g)对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回 1，否则返回0i=1；while(flag&i=n)if(visitedi=0)dfs(g，i)；finishedi=1；ifreturn(flag)：提示：此题考查的知识点是图的遍历。对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点 v 出发遍历，在 dfs(v)结束之前，出现从顶点 u到顶点 v 的回边，图中必存在环。由于 dfs 产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量 final，在 dfs 函数退出时，把顶点 v 插入到 final所指的链表中，链表中的结点就是一个正常的拓扑序列。【知识模块】 图