1、全国自考数据结构导论（图）模拟试卷 1 及答案与解析一、单项选择题1 在无向图中，所有顶点的度数之和等于边数之和的_倍。（A）12（B） 1（C） 2（D）32 在有向图中，所有顶点的人度之和是所有顶点出度之和的_倍。（A）12（B） 1（C） 2（D）33 以下有关完全图的叙述中，不正确的是_。（A）在完全图中，任意两个顶点之间均有边相连（B）含有 n 个顶点的完全图具有 n(n 一 1)条边（C）完全图是无向图（D）完全图是有向图4 以下有关连通分量的说法中，正确的是_。（A）连通分量是有向图中的极小连通子图（B）连通分量是无向图中的极小连通子图（C）连通分量是有向图中的极大连通子图（D）
2、连通分量是无向图中的极大连通子图5 以下哪个路径不是简单路径_。（A）v1，v2，v4，v2（B） v1，v2，v4，v5（C） v1，v2，v5，v4（D）v1，v2，v3，v56 在一个含 n 个顶点的连通图中，任意一条简单路径的长度都不可能超过（A）n2（B） n 一 1（C） n（D）n+17 十字链表适用于_。（A）完全图（B）连通分量（C）无向图（D）有向图8 具有 n 个顶点的连通图，其最小生成树具有_条边。（A）n2（B） n-1（C） n（D）n+19 任何一个带权的无向连通图，其最小生成树一定有_。（A）1 棵（B） n 棵（C） 1 棵或 n 棵（D）0 棵10 如下图所
3、示的有向图，其深度优先搜索遍历序列为_。（A）ABEFDC（B） ABEDCF（C） ACDBEF（D）ADEFCB11 对于如图所示的有向图，其广度优先搜索遍历序列为_。（A）ABCDFE（B） ABCDEF（C） ABECDF（D）ADCBEF12 对于如图所示的有向图，其拓扑排序序列为_。（A）ADCFEB（B） CEBFDA（C） ABDFCE（D）CBFEDA13 使用_算法可以确定从源点到图中其余顶点的最短路径。（A）迪杰斯特拉（B）弗洛伊德（C）克鲁斯卡尔（D）普里姆14 判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用_。（A）深度优先搜索遍历算法（B）广度优
4、先搜索遗历算法（C）普里姆算法（D）克鲁斯卡尔算法15 以下有关关键路径的叙述中，不正确的是_。（A）关键路径上的活动是关键活动（B）关键路径是从源点到汇点之间具有最大路径长度的路径（C）关键路径可以构成回路（D）关键活动的时间余量为 0二、填空题16 有向图的极大连通子图称为_。17 一个具有 n 个顶点的完全无向图的边数为_；一个具有 n 个顶点的完全有向图的弧数为_。18 在有向图中，顶点的度等于_。19 一个有 n 个顶点的无向图，采用邻接矩阵作为存储结构，则求图中边数的方法是_。求任一顶点的度的方法是_。20 一个有 10 个顶点的有向图，它最多能有_条边。21 无向图 G=(V，E
5、)，其中：V=a，b，c，d，e ，f，E=(a，b)，(a，e) ，(a，c)，(b，e)，(c，f) ，(f，d)，(e，d)，对该图进行深度优先遍历，得到的顶点序列是_。22 _算法是按路径长度递增的次序产生最短路径的算法。23 图的基本存储结构主要有_和_。24 图的遍历方法主要有_和_两种。25 构造图的最小生成树的方法主要有_和_两种。26 用图中的顶点表示活动，用弧表示活动问的先后关系，这样的有向图称为_。27 事件 vk 的最早发生时间是从源点到顶点 vk 的_。28 在 AOE 网中，从源点到汇点之间具有最大路径长度的路径称为_。29 有 29 条边的无向连通图，至少有_个顶
6、点，至多有_个顶点；有29 条边的无向非连通图，至少有_个顶点。有 29 条边(弧)的有向连通图，至少有_个顶点，至多有_个顶点；有 29 条边的有向非连通图，至少有_个顶点。30 Prim 算法适用于求_的最小生成树，Kruskal 算法适用于求_的最小生成树。三、应用题31 对下图所示的有向图，请回答以下问题。 (1)该图是强连通图吗? 若不是，请给出其强连通分量。 (2)请给出每个顶点的度、人度和出度。32 给出如图所示有向图的邻接矩阵、邻接表和逆邻接表。33 对如图所示的有向图，请给出从 A 开始的深度优先搜索遍历序列和广度优先搜索遍历序列。34 已知一个无向图的邻接表如下图所示，请给
7、出从顶点 v。开始的深度优先搜索遍历序列和广度优先搜索遍历序列。35 已知如图所示的网，请给出从顶点 A 开始按 Prim 算法构造的最小生成树，并给出构造顺序。36 已知如图所示的网，请给出按 Kruskal 算法构造的最小生成树，并给出构造顺序。37 对于如图所示的 AOE 网，写出其关键路径。38 对于如图所示的 AOE 网，求出关键路径，并写出关键活动。39 对如图所示的网，求顶点 v0 到其他顶点之间的最短路径和最短路径长度。40 对如图所示的网，求任意两个顶点之间的最短路径。41 一个函数，根据用户输入的偶对(以输入 0 表示结束)建立其有向图的邻接表。42 已知图采用邻接表存储方
8、式，试写出删除边(v i，v i)(对于无向图)或删除弧i，V i(对于有向图)的算法。43 已知 n 个顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。44 对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序，写出在遍历图的同时进行拓扑排序的算法。45 假定 Anxn 是一个无向简单图 G 的邻接矩阵，其中 n 是图 G 的顶点数。对Anxn 采用顺序的方法存储其下三角，然后写出对 G 进行宽度优先搜索的算法。全国自考数据结构导论（图）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 C【知识模块】 图2 【正确答案】 B【知识模块】
9、图3 【正确答案】 D【知识模块】 图4 【正确答案】 D【知识模块】 图5 【正确答案】 A【知识模块】 图6 【正确答案】 B【知识模块】 图7 【正确答案】 D【知识模块】 图8 【正确答案】 B【知识模块】 图9 【正确答案】 C【知识模块】 图10 【正确答案】 D【知识模块】 图11 【正确答案】 B【知识模块】 图12 【正确答案】 C【知识模块】 图13 【正确答案】 A【知识模块】 图14 【正确答案】 A【知识模块】 图15 【正确答案】 C【知识模块】 图二、填空题16 【正确答案】 强连通分量【知识模块】 图17 【正确答案】 n(n 一 1)2n(n 一 1)【知识模
10、块】 图18 【正确答案】 顶点的人度与顶点的出度之和【知识模块】 图19 【正确答案】 矩阵中 1 的个数除以 2 计算该行中 l 的个数【知识模块】 图20 【正确答案】 90【知识模块】 图21 【正确答案】 a ，e ，d ，f，c，b【知识模块】 图22 【正确答案】 迪杰斯特拉【知识模块】 图23 【正确答案】 邻接矩阵邻接表【知识模块】 图24 【正确答案】 深度优先搜索遍历广度优先搜索遍历【知识模块】 图25 【正确答案】 普里姆算法克鲁斯卡尔算法【知识模块】 图26 【正确答案】 AOV 网【知识模块】 图27 【正确答案】 最大路径长度【知识模块】 图28 【正确答案】 关
11、键路径【知识模块】 图29 【正确答案】 9 30 10 6 29 7【试题解析】 对于 n 个顶点的无向连通图 G，为完全图时边数达到最多：共 n(n一 1) 2 条边，满足不等式 n(n 一 1)229 最大的 n 为 8，即 8 个顶点的连通无向图最多 28 条边，因此有 29 条边的连通无向图至少有 9 个顶点；当 G 为树时边数达到最少：共 n 一 1 条边，因此有 29 条边的连通图中至多 30 个顶点。因为 29条边 9 个顶点的无向图必定是连通的，29 条边的非连通无向图至少有 10 个顶点(一个子图为含 8 个顶点的完全图，另一个子图为含两个顶点的完全图)。因为 5 个顶点的
12、有向完全图最多 20 条边，6 个顶点的有向完全图最多 30 个结点。因此有 29条弧的有向连通图至少有 6 个顶点，至多 29 个顶点。29 条边 6 个顶点的有向图必定是连通的，要不连通至少有 7 个顶点。【知识模块】 图30 【正确答案】 稠密图 稀疏图【知识模块】 图三、应用题31 【正确答案】 (1)该图不是强连通图。强连通分量为：(2)每个顶点的度、入度和出度：D(A)=3ID(A)=10D(A)=2D(B)=4ID(B)=20D(B)=2D(C)=3ID(C)=10D(C)=2D(D)=2ID(D)=20D(D)=0【知识模块】 图32 【正确答案】 【知识模块】 图33 【正确
13、答案】 深度优先搜索遍历序列：AEDBC ；广度优先搜索遍历序列：AEBDC。【知识模块】 图34 【正确答案】 深度优先搜索遍历：v 0 v1 v2 v3； 广度优先搜索遍历：v v 1 v3v2。【知识模块】 图35 【正确答案】 【知识模块】 图36 【正确答案】 【知识模块】 图37 【正确答案】 关键路径：v 0，v 2，v 3，v 5。【知识模块】 图38 【正确答案】 关键活动：a 0，a 2，a 2，a 4。 关键路径： v0，v 1，v 3 和v0，v 1，v 2，v 3。【知识模块】 图39 【正确答案】 v 0 到 v1：最短路径 v0，v 3，v 1；最短路径长度 7；
14、v 0 到 v2：最短路径 v0，v 3，v 1，v 2；最短路径长度 15；v 0 到 v3：最短路径 v0，v 3；最短路径长度2；v 0 到 v4：最短路径 v0，v 3，v 1，v 2，v 4；最短路径长度 22。【知识模块】 图40 【正确答案】 【知识模块】 图41 【正确答案】 voidCreateAdjList(ALGrahp *输入图 G 的顶点数*for(i=0;iadjvex=j；P 一nextare=Gverticesifirstare；Gverticesifrrstare=p；Scanf(break；elsepre=p;P=P 一nextarc；)P=G vertic
15、esjfirstarc；pre=NULL； *查找另一个顶点的邻接点*while(p)if(P 一adjvex=i)if(pre：=NULL)Gverticesjfirstarc=P 一nextarc ；else pre 一nextarc=P 一nextarc；free(p)；break；elsepre：pjP=P 一nextarc；【试题解析】 本题只给出对无向图的操作，由于图采用邻接表存储，根据输入的边(Vi， vj)，分别找出两顶点在图中的位置 i 和 j，然后在各自的邻接表链表中删除相应的结点。算法描述如下。【知识模块】 图43 【正确答案】 void SortPath_Floyd(M
16、GrophG) *求有 n 个顶点的有向图 G 的任意两顶点之间的路径，顶点 i 和顶点 J 之间的最短路径*存放在数组 sortpathij*for(i=0;inextarc)if(visitedp-adjvexflaqp 一adjvex=1；【试题解析】 对有向图进行深度优先搜索，可以判定图中是否有回路。若从有向图的某个顶点 v 出发深度优先遍历，在 DFS(v)结束前，出现顶点 n 到顶点 v 的回边，图中必有环。用数组 flagi=1，表示其邻接点已全部被搜索完。由于深度优先搜索得到的序列是逆拓扑排序序列。因此用队列存放所访问的顶点。算法描述如下。【知识模块】 图45 【正确答案】 v
17、oid BFSTraverse(MGraphG ，int B)* 对采用压缩存储的无向图 G 进行广度优先搜索*for(i=0;iGvexnum；i+) *转换*for(j=0;jGvexnum；j+)Bk+=Garcsijadj；for(v=0；vGvexnum；v+)visitedv=0；row=1；InitQueu(Q)； *记住每行的首元素位置 *for(v=0；vGvexnum ；v+)if(!visitedv) visit(Q)；visitedv=1 ；EnQueue(Q，v)；while(!EmptyQueue)(Q)DeQueue(Q，v) ； i=row；j=V：while(iG vexnum)k=i(i+1)2+j；if(Bk)=1&!visitedi)f visit(i)；visitedi=1；EnQueue(Q，i)；i+； row+；【知识模块】 图
