《2023年图历考试及参考超详细解析超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年图历考试及参考超详细解析超详细解析答案.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图历考试及参考答案 2 作者：日期：已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 3 第 7 章 图（2008 年 1 月）9、假设有向图含 n 个顶点及 e 条弧，则表示该图的邻接表中包含的弧结点个数为（）A、n B、e C、2e D、ne 10、如图所示的有向无环图可以得到的不同拓扑序列的个数为（）A、1 B、2 C、3 D、4 2
2、2、已知一个有向网如图所示,从顶点1 到顶点 4 的最短路径长度为_。28、已知有向图的邻接表如图所示,(1)写出从顶点 A 出发,对该图进行广度优先搜索遍历的顶点序列;(2)画出该有向图的逆邻接表。(1)(2)33、设有向图邻接表定义如下；typedef struct VertexNode adjlistMax VertexNum;int n,e;/图的当前顶点数和弧数 ALGraph;/邻接表类型 vertex firstedge 其中顶点表结点 VertexNode 结构为：边表结点 EdegNode 结构为：阅读下列算法 f33，并回答问题：(1)已知有向图 G 的邻接表如图所示,写出
3、算法 f33 的输出结果;adjvex next 已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 4 (2)简述算法 f33 的功能。void dfs(ALGraph*G,int v)EdgeNode*p;visitedv=TRUE;printf(%c,G-adjlistv.vertex);for(p=(G-adjlistv).first
4、edge;p;p=p-next)if(!visitedp-adjvex)dfs(G,p-adjvex);void f33(ALGraph*G)int v,w;for(v=0;v n;v+)for(w=0;wn;w+)visitedw=FALSE;printf(%d:,v);dfs(G,v);printf(n);（1）（2）（2008 年 10 月）8、在一个具有 n 个顶点的有向图中，所有顶点的出度之和为 Dout，则所有顶点的入度之和为（）A、Dout B、Dout-1 C、Dout+1 D、n 9、如图所示的有向无环图可以得到的拓扑序列的个数是（）A、3 B、4 C、5 D、6 已知有向图
5、的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 5 10、如图所示的带权无向图的最小生成树的权为（）A、51 B、52 C、54 D、56 22、n 个顶点且含有环路的无向连通图中，至少含有 条边。27、图的邻接表的类型定义如下所示：#define MaxVertexNum 50 typedef struct node int adjvex;str
6、uct node *next;EdgeNode;typedef struct VertexType vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVertexNum;typedef struct AdjList adjlist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。（2009 年 1 月）10、已知含 6 个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点
7、v0 出发进行深度优先遍历可能得到的顶点访问序列为()A、(v0，v1，v2，v5，v4，v3)B、(v0，v1，v2，v3，v4，v5)C、(v0，v1，v5，v2，v3，v4)D、(v0，v1，v4，v5，v2，v3)11、如图所示有向图的一个拓扑序列是()A、ABCDEF 题27已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 6 B
8、、FCBEAD C、FEDCBA D、DAEBCF 22、若用邻接矩阵表示有向图，则顶点 i 的入度等于矩阵中_。32、设有向图邻接表定义如下：typedef struct VertexNode adjlist MaxVertexNum ;int n，e；图的当前顶点数和弧数 ALGraph；邻接表类型 其中顶点表结点 VertexNode 边表结点 EdgeNode 结构为：阅读下列算法，并回答问题：(1)已知某有向图存储在如图所示的邻接 表 G 中，写出执行 f32(&G)的输出；(2)简述算法 f32 的功能。int visited MaxNum;void DFS(ALGraph*G,i
9、nt i)EdgeNode*p;visited i =TRUE;if(G-adjlist i.firstedge=NULL)printf(%c,G-adjlist i.vertex);else p=G-adjlist i.firstedge;while(p!=NULL)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-next;void f32(ALGraph*G)int i;for(i=0;i n;i+)visited i =FALSE;for(i=0;i n;i+)已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接
10、表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 7 if(!visitedi)DFS(G,i);(1)(2)（2009 年 10 月）11、若非连通无向图 G 含有 21 条边，则 G 的顶点个数至少为（）A、7 B、8 C、21 D、22 12、如图所示的有向图的拓扑序列是（）A、c，d，b，a，e B、c，a，d，b，e C、c，d，e，a，b D、c，a，b，d，e 22、求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时
11、间与图中_的数目正相关。28、已知无向图 G 的邻接表如图所示，(1)画出该无向图；(2)画出该图的广度优先生成森林。30、阅读下列算法，并回答问题：(1)无向图 G 如图所示，写出算法 f30(&G)的返回值；(2)简述算法 f30 的功能。#define MaxNum 20 已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 8 int
12、visitedMaxNum；void DFS(Graph *g，int i)；/*从顶点 vi出发进行深度优先搜索，访问顶点 vj时置 visitedj 为 1*/int f30(Graph *g)int i，k；for (i=0；in；i+)*g-n为图 g 的顶点数目*visitedi=0；for (i=k=0；in;i+)if (visitedi=0)k+；DFS(g，i)；return k；（2010 年 1 月）11、对下面有向图给出了四种可能的拓扑序列，其中错误的是（）A、1，5，2，6，3，4 B、1，5，6，2，3，4 C、5，1，6，3，4，2 D、5，1，2，6，4，3 1
13、2、以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是（）A、v1，v2，v3，v4，v5，v6，v7 B、v1，v2，v5，v4，v3，v7，v6 C、v1，v2，v3，v4，v7，v5，v6 D、v1，v2，v5，v6，v7，v3，v4 22、已知有向图如下所示，其中顶点A 到顶点 C 的最短路径长度是_。已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的
14、类型定义如下所示为便于删除和 9 27、已知一个无向图 G=(V，E)，其中 V=A，B，C，D，E，F，邻接矩阵表示如下所示。请回答下列问题：(1)请画出对应的图 G。(2)画出图 G 的邻接表存储结构。（2010 年 10 月）9、在图G中求两个结点之间的最短路径可以采用的算法是()A、迪杰斯特拉（Dijkstra）算法 B、克鲁斯卡尔（Kruskal）算法 C、普里姆(Prim)算法 D、广度优先遍历(BFS)算法 10、下图G=(V,E)是一个带权连通图，G的最小生成树的权为()A、15 B、16 C、17 D、18 11、在下图中，从顶点1出发进行深度优先遍历可得到的序列是()A、1
15、 2 3 4 5 6 7 B、1 4 2 6 3 7 5 C、1 4 2 5 3 6 7 D、1 2 4 6 5 3 7 21、若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为_。29、请回答下列问题：(1)英文缩写DAG的中文含义是什么？(2)请给出下面DAG图的全部拓扑排序。已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示
16、为便于删除和 10 （2011 年 1 月）9、下列叙述中错误的是（）A、图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B、图的遍历可以采用深度优先遍历和广度优先遍历 C、图的广度优先遍历只适用于无向图 D、图的深度优先遍历是一个递归过程 10、已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4，E=，图 G 的拓扑序列是（）A、V1,V2,V3,V4 B、V1,V3,V2,V4 C、V1,V3,V4,V2 D、V1,V2,V4,V3 22、一个有 n 个顶点的无向连通图，最少有_条边。27、已知有向图的邻接表如图所示，请回答下面问题：(1)给出该图的邻接矩阵；(2)从结点
17、 A 出发，写出该图的深度优先遍历序列。已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 11 参考答案（2008 年 1 月）9、B 10、C 22、55 28、(1)ABDCE(2)33、(1)0:AB 1:B 2:CEAB 3:DEABC 4:EAB(2)从有向图的每个顶点出发进行深度优先遍历，输出遍历过程中访问到的顶点。（2008
18、年 10 月）8、A 9、C 10、C 22、n 条边。27、typedef char VertexType;typedef struct node /边点表结点定义 VertexNode*adjvex;struct node *next;EdgeNode;typedef struct vertexnode /顶点表结点定义 VertexType vertex;struct vertexnode*next;EdgeNode *firstedge;VertexNode;typedef struct A B C D E 0 1 2 3 4 4 0 1 0 2 4 3 已知有向图的邻接表如图所示写出
19、从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 12/图的定义 VertexNode *adjlist;int n,e;ALGraph;（2009 年 1 月）10、A 11、B 22、第 i 列 1（非 0 元）的个数。32、(1)BD(2)输出出度为 0 的顶点值。（2009 年 10 月）11、B 12、B 22、边 28、(1)(2)30、(1)3(2)求连通
20、分量的个数（2010 年 1 月）11、C 12、D 22、35 27、(1)A B D C E F G H I A B D C E F G H I A B D C E F 已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和 13(2)（2010 年 10 月）9、A 10、D 11、B 21、2m 29、(1)有向无环图(2)abdcefg
21、、abdcfeg、adbcefg、adbcfeg（2011 年 1 月）9、C 10、A 22、n-1 27、已知有向图的邻接表如图所示，请回答下面问题：(1)0100100100100000110000110 (2)ABCED A B C D E 0 1 2 3 4 4 0 1 0 1 4 5 F 5 1 3 2 3 1 5 3 2 4 已知有向图的邻接表如图所示写出从顶点出发对该图进行广度优先搜索遍历的顶点序列画出该有向图的逆邻接表设有答问题已知有向图的邻接表如图所示写出算法的输出结果简述算法的功能年月在一个具有个顶点的有向图中所有顶点图的最小生成树的权为个顶点且含有环路的无向连通图中至少含有条边图的邻接表的类型定义如下所示为便于删除和