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 )解析:
copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1