1、计算机专业基础综合（图）-试卷 1 及答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：18，分数：36.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.在有向图 G 的拓扑序列中，若顶点 v i 在顶点 v j 之前，则下列情形不可能出现的是( )。（分数：2.00）A.G 中有弧 i，v hB.G 中有一条从 v i 到 v j 的路径C.G 中没有弧 i，v jD.G 中有一条从 v j 到 v i 的路径3.以下关于图的说法中正确的是( )。 一个有向图的邻接表和逆邻接表中的结点个数一定相等
2、 用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（分数：2.00）A.，B.，C.，D.仅有4.下列关于 AOE 网的叙述中，不正确的是( )。（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成5.一个二部图的邻接矩阵 A 是一个( )类型的矩阵。（分数：2.00）A.rtxn 矩阵B.分块对称矩阵C.上三角矩阵D.下三角矩阵6.求解
3、最短路径的 Floyd 算法的时间复杂度为( )。（分数：2.00）A.O(n)B.O(n+C)C.O(n 2 )D.O(n 3 )7.下列 4 组含 C1C7 的结点序列中，( )是下图所示的有向图的拓扑序列。 （分数：2.00）A.Cl，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C68.如果具有 n 个顶点的图是一个环，则它有( )棵生成树。（分数：2.00）A.n 2B.nC.n 一 1D.19.如下图所示，在下面的 5 个序列中，符合深度优先遍历的序列有( )个。ae
4、bfdc acfdebaedfcb aefdbc aecfdb （分数：2.00）A.5B.4C.3D.210.无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有( )个顶点。（分数：2.00）A.11B.12C.15D.1611.对 AOE 网络中有关关键路径的叙述中，正确的是( )。（分数：2.00）A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，
5、关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间12.以下关于图的叙述中，正确的是( )。（分数：2.00）A.强连通有向图的任何顶点到其他所有顶点都有弧B.图与树的区别在于图的边数大于或等于顶点数C.无向图的连通分量指无向图中的极大连通子图D.假设有图 G=V，E，顶点集 V“V，E“E，则 V 和E“构成 G 的子图13.假设有 n 个顶点 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为( )。（分数：2.00）A.O(n)B.O(e)C.O(n+e)D.O(ne)14.若 G 是
6、一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 的结点数至少是( )。（分数：2.00）A.11B.10C.9D.815.已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=，。对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。（分数：2.00）A.a，d，c，b，eB.d，a，b，c，eC.a，b，d，c，eD.a，b，c，d，e16.用有向无环图描述表达式(A+B)*(A+B)A)，至少需要顶点的数目为( )。（分数：2.00）A.5B.6C.8D.917.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构
7、和边表结点结构如下图所示： （分数：2.00）A.vertex 存储的是结点的数值域的内容B.firstedge 域指示第一条依附于该顶点的边C.mark 指向下一条依附于结点的边D.info 为指向和边相关的各种信息的指针域18.以下关于十字链表的说法中，不正确的是( )。（分数：2.00）A.十字链表是有向图的另一种链式存储结构B.行指针 row 为矩阵中的行位置，列指针 col 为矩阵中的列位置C.数值 val 为矩阵中的值D.right 指针指向矩阵中的行位置，down 指针指向矩阵中的列位置_二、综合应用题(总题数：10，分数：22.00)19.综合应用题 41-47 小题。_20.
8、对于如下的加权有向图，给出算法 Dijkstra 产生的最短路径的支撑树，设顶点 A 为源点，并写出生成过程。 （分数：2.00）_21.对于有向无环图，叙述求拓扑有序序列的步骤。（分数：2.00）_22.对于以下的图，写出它的 4 个不同的拓扑有序序列。 （分数：2.00）_23.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)（分数：2.00）_24.假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可
9、)。(注意：图中不存在顶点到自己的弧)（分数：2.00）_25.已有邻接表表示的有向图，请编程判断从第 u 顶点至第 v 顶点是否有简单路径，若有则打印出该路径上的顶点。（分数：2.00）_26.“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)（分数：2.00）_27.设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为： MAX从 w 到 v 的最短距离w 属于 V(G) 如果 v 是有向图 G 中具有最小偏心
10、度的顶点，则称顶点 v 是 G 的中心点。（分数：2.00）_对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减 1，并对其未访问的、入度为 0的邻接到的顶点进行递归。（分数：6.00）(1).给出完成上述功能的图的邻接表定义。（分数：2.00）_(2).定义在算法中使用的全局辅助数组。（分数：2.00）_(3).写出在遍历图的同时进行拓扑排序的算法。（分数：2.00）_计算机专业基础综合（图）-试卷 1 答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：18，分
11、数：36.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.在有向图 G 的拓扑序列中，若顶点 v i 在顶点 v j 之前，则下列情形不可能出现的是( )。（分数：2.00）A.G 中有弧 i，v hB.G 中有一条从 v i 到 v j 的路径C.G 中没有弧 i，v jD.G 中有一条从 v j 到 v i 的路径 解析：解析：此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点 v i 与顶点 v j 有一条弧，则拓扑序列中顶点 v i 必在顶点 v j 之前。若有一条从 v j 到 v i 的路径，则顶
12、点 v i 不可能在顶点 v j 之前。所以应选 D。3.以下关于图的说法中正确的是( )。 一个有向图的邻接表和逆邻接表中的结点个数一定相等 用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（分数：2.00）A.， B.，C.，D.仅有解析：解析：说法是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都等于有向图中的边的个数。 说法是正确的，邻接矩阵的空间复杂度为 D(n 2 )，与边的个数无关。 说法是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。4.下
13、列关于 AOE 网的叙述中，不正确的是( )。（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成解析：解析：此题考查的知识点是图的关键路径。在 AOE 网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。关键路径上的活动称为关键活动。A、C、D 的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选 B。5.一个二部图的邻接矩阵 A 是一个(
14、)类型的矩阵。（分数：2.00）A.rtxn 矩阵B.分块对称矩阵 C.上三角矩阵D.下三角矩阵解析：解析：此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图 G=的顶点集 V 划分成两个子集 V1 和 V2(V1V2=?)，使得 G 中任何一条边的两个端点一个属于 V1，另一个属于 V2，则称G 为二部图。由于其特点，其存储矩阵必为分块对称的，所以选 B。6.求解最短路径的 Floyd 算法的时间复杂度为( )。（分数：2.00）A.O(n)B.O(n+C)C.O(n 2 )D.O(n 3 ) 解析：7.下列 4 组含 C1C7 的结点序列中，( )是下图所示的有向图的拓扑序列
15、。 （分数：2.00）A.Cl，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C6 解析：解析：考查拓扑排序的算法。 以 1 开头的拓扑排序过程，如下图所示： 以 5 开头的拓扑排序过程，答案中的过程如下图所示：8.如果具有 n 个顶点的图是一个环，则它有( )棵生成树。（分数：2.00）A.n 2B.n C.n 一 1D.1解析：解析：因为 n 个顶点构成的环共有 n 条边，去掉其中任意一条便是一棵生成树，共有 n 种情况，所以可以有 n 棵不同的生成树。9.如下图所示，在下面
16、的 5 个序列中，符合深度优先遍历的序列有( )个。aebfdc acfdebaedfcb aefdbc aecfdb （分数：2.00）A.5B.4C.3D.2 解析：解析：本题中，符合深度优先遍历顺序的是 1 和 5，其他三个序列均不符合。10.无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有( )个顶点。（分数：2.00）A.11B.12C.15D.16 解析：解析：由于在具有 n 个顶点 e 条边的无向图中，有 11.对 AOE 网络中有关关键路径的叙述中，正确的是( )。（分数：2.00）A.从开始顶点到完
17、成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间 B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间解析：解析：本题考查关键路径的定义。 关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。 关键活动：关键路径上的活动称为关键活动。12.以下关于图的叙述中，正确的是( )。（分数：2.00）A.强连通有向图的任何顶点到其他所有顶点都有弧B.图与树的区别在于
18、图的边数大于或等于顶点数C.无向图的连通分量指无向图中的极大连通子图 D.假设有图 G=V，E，顶点集 V“V，E“E，则 V 和E“构成 G 的子图解析：解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A 错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若 E“中的边对应的顶点不是 V“中的元素时，则 V“和E“无法构成图，D 错误。13.假设有 n 个顶点 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为( )。（分数：2.00）A.O(n)B.O(e)C.O(n+e) D.O(ne)解析：解析：删除与某顶点 v 相
19、关的所有边的过程如下：先删除下标为 v 的顶点表结点的单链表，出边数最多为 n 一 1，对应时间复杂度为 O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为 O(e)。故总的时间复杂度为 O(n+e)。14.若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 的结点数至少是( )。（分数：2.00）A.11B.10 C.9D.8解析：解析：n 个顶点构成的无向图中，边数n(n 一 1)2，将 e=36 代入，有 n9，现已知无向图是非连通的，则 n 至少为 10。15.已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=，。对该图进行拓扑排序，下
20、面序列中不是拓扑排序的是( )。（分数：2.00）A.a，d，c，b，eB.d，a，b，c，eC.a，b，d，c，eD.a，b，c，d，e 解析：解析：选项 D 中，删去 a、b 及其对应的出边后，c 的入度不为 0，因此有边，故不是拓扑序列。选项 A、B、C 均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。16.用有向无环图描述表达式(A+B)*(A+B)A)，至少需要顶点的数目为( )。（分数：2.00）A.5 B.6C.8D.9解析：解析：此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的 5 个字符作为 5 个顶点，其中 A
21、+B 和 A 可共用，所以至少 5 个即可，选 A。17.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示： （分数：2.00）A.vertex 存储的是结点的数值域的内容B.firstedge 域指示第一条依附于该顶点的边C.mark 指向下一条依附于结点的边 D.info 为指向和边相关的各种信息的指针域解析：解析：顶点表由两个域组成，vertex 域存储和该顶点相关的信息，firstedge 域指示第一条依附于该顶点的边。边表结点由六个域组成：mark 为标记域，用以标记该条边是否被搜索过；ivex 和 jvex
22、 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点jvex 的边;info 为指向和边相关的各种信息的指针域。18.以下关于十字链表的说法中，不正确的是( )。（分数：2.00）A.十字链表是有向图的另一种链式存储结构B.行指针 row 为矩阵中的行位置，列指针 col 为矩阵中的列位置C.数值 val 为矩阵中的值D.right 指针指向矩阵中的行位置，down 指针指向矩阵中的列位置_ 解析：解析：right 指向右侧的一个非零元素，down 指向下侧的一个非零元素。二、综合应用题(总题数：10，分数：22.00)19.综
23、合应用题 41-47 小题。_解析：20.对于如下的加权有向图，给出算法 Dijkstra 产生的最短路径的支撑树，设顶点 A 为源点，并写出生成过程。 （分数：2.00）_正确答案：(正确答案：顶点 A 到顶点 B、C、D、E 的最短路径依次是 3、18、38、43，按 Dijkstra 所选顶点过程是 B、C、D、E。支撑树的边集合为 ，具体分析如下表所示。 *)解析：21.对于有向无环图，叙述求拓扑有序序列的步骤。（分数：2.00）_正确答案：(正确答案：对有向图，求拓扑序列步骤为： 在有向图中选一个没有前驱(即入度为零)的顶点并输出。 在图中删除该顶点及所有以它为尾的弧。 重复和步，直
24、至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。)解析：22.对于以下的图，写出它的 4 个不同的拓扑有序序列。 （分数：2.00）_正确答案：(正确答案：从入度为 0 的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。从顶点 1 开始的可能的拓扑序列为12345678、12354678、13456278、13546278。)解析：23.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)（分数：2.00）_正确答案：(正确答案：算法 1：
25、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=O)dfs(g，j)； P=P 一next： while if(!flag)return(0)； 算法 2：输出 vi 到 vj 的路径，其思想
26、是用一个栈存放遍历的顶点，遇到顶点 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-adjvex)；top-；p=p-next； 算法 3：非递归算法求解。 int Judge(AdjList g，int i，j) 判断 n 个顶点以邻接表示的有向图 g 中，顶点 vi 各 vj 是否有路径， 有则返回 1，否则返回 0。 for(i=1；i0) k=stacktop 一一；P=gkfirstarc； while(P!=null t 一next=final；final=t； 将该顶点插入链表 dfs 结束 intdfx_Topsort(Adjlist g) 对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回 1，否则返回 0 i=1； while(flag )解析：
