已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第7章 图(2008年1月) 9、假设有向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为()A、nB、eC、2eD、ne10、如图所示的有向无环图可以得到的不同拓扑序列的个数为()A、1B、2C、3D、422、已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为_。28、已知有向图的邻接表如图所示,(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;(2) 画出该有向图的逆邻接表。(1)(2)33、设有向图邻接表定义如下; typedef struct VertexNode adjlistMax VertexNum; int n,e; /图的当前顶点数和弧数 ALGraph; /邻接表类型vertexfirstedge其中顶点表结点VertexNode结构为:边表结点EdegNode结构为:adjvexnext阅读下列算法f33,并回答问题:(1)已知有向图G的邻接表如图所示, 写出算法f33的输出结果;(2)简述算法f33的功能。void dfs (ALGraph *G,int v)EdgeNode * p;visitedv=TRUE;printf(%c,G-adjlistv.vertex);for(p=(G-adjlistv).firstedge; 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、 DoutB、 Dout-1C、 Dout+1D、 n9、如图所示的有向无环图可以得到的拓扑序列的个数是( )A、 3B、 4C、 5D、 610、如图所示的带权无向图的最小生成树的权为( )A、 51B、 52C、 54D、 5622、n个顶点且含有环路的无向连通图中,至少含有 条边。27、图的邻接表的类型定义如下所示:#define MaxVertexNum 50typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct VertexType vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVertexNum;typedef struct AdjList adjlist;int n, e;ALGraph;为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明。题27图(2009年1月) 10、已知含6个顶点(v0,v1,v2,v3,v4,v5)的无向图的邻接矩阵如图所示,则从顶点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、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF22、若用邻接矩阵表示有向图,则顶点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, int 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+) if ( ! visitedi ) DFS(G, i) ;(1)(2)(2009年10月) 11、若非连通无向图G含有21条边,则G的顶点个数至少为()A、7B、8C、21D、2212、如图所示的有向图的拓扑序列是()A、c,d,b,a,eB、c,a,d,b,eC、c,d,e,a,bD、c,a,b,d,e22、求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_的数目正相关。28、已知无向图G的邻接表如图所示,(1)画出该无向图;(2)画出该图的广度优先生成森林。30、阅读下列算法,并回答问题:(1)无向图G如图所示,写出算法f30(&G)的返回值;(2)简述算法f30的功能。#define MaxNum 20int 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,4C、5,1,6,3,4,2 D、5,1,2,6,4,312、以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是( )A、v1,v2,v3,v4,v5,v6,v7 B、v1,v2,v5,v4,v3,v7,v6C、v1,v2,v3,v4,v7,v5,v6 D、v1,v2,v5,v6,v7,v3,v422、已知有向图如下所示,其中顶点A到顶点C的最短路径长度是_。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、15B、16C、17D、1811、在下图中,从顶点1出发进行深度优先遍历可得到的序列是( )A、1 2 3 4 5 6 7B、1 4 2 6 3 7 5C、1 4 2 5 3 6 7D、1 2 4 6 5 3 721、若无向图G中有n个顶点m条边,采用邻接矩阵存储,则该矩阵中非0元素的个数为_。29、请回答下列问题:(1)英文缩写DAG的中文含义是什么?(2)请给出下面DAG图的全部拓扑排序。(2011年1月) 9、下列叙述中错误的是( )A、图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次B、图的遍历可以采用深度优先遍历和广度优先遍历C、图的广度优先遍历只适用于无向图D、图的深度优先遍历是一个递归过程10、已知有向图G=(V,E),其中V=V1,V2,V3,V4,E=,图G的拓扑序列是( )A、V1,V2,V3,V4B、V1,V3,V2,V4C、V1,V3,V4,V2D、V1,V2,V4,V322、一个有n个顶点的无向连通图,最少有_条边。27、已知有向图的邻接表如图所示,请回答下面问题:(1)给出该图的邻接矩阵;(2)从结点A出发,写出该图的深度优先遍历序列。参考答案(2008年1月) 9、B10、C22、5528、(1)ABDCE(2)ABCDE01234401024333、 (1)0:AB 1:B 2:CEAB 3:DEABC 4:EAB(2)从有向图的每个顶点出发进行深度优先遍历,输出遍历过程中访问到的顶点。(2008年10月) 8、A9、C10、C22、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 /图的定义VertexNode *adjlist;int n, e;ALGraph;(2009年1月) 10、A11、B22、第i列1(非0元)的个数。32、(1)BD(2)输出出度为0的顶点值。(2009年10月) 11、B12、B22、边28、ABDCEFGHI(1)(2)ABDCEFGHI30
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学四年级综合实践活动《童年的发现-我和长辈比游戏》单元教学设计
- 小学一年级道德与法治“吃饭有讲究”情境化教学设计
- 七年级下册数学分式全章教学设计(沪科版新教材13种题型知识清单)
- 小学四年级班队活动教学设计:课间十分钟安全守护行动
- 小学三年级音乐《美丽的黄昏》欣赏教学设计
- 高三地理教学设计:中国国家发展战略举例深度解析与核心素养构建
- 高中化学必修第一册 2.1.3 碳酸钠与碳酸氢钠 教学设计
- 沪科版(五四学制)九年级物理下册《15.1 电磁波》教学设计
- 高中体育与健康必修第一册灵敏素质练习与游戏教学设计
- 高中化学必修第一册 4.1.1 原子结构与核外电子排布 教学设计
- 2026知识产权法考试题(含答案)
- 介入患者的围手术期的护理
- 安徽省建设工程工程量清单计价规程(2026版)
- 2026年中医康复理疗师题库及参考答案
- 长征胜利 90 周年 赓续长征血脉 坚守教书育人初心使命课件
- 2026年广东省职业病诊断医师试题(职业性放射性疾病)(附答案)
- 2026 年掌握消防技能守护生命安全课件
- 2026年道德与法治六年级上册第6课《了解国家机构》教案设计(2课时)
- 广东聚德阀门科技异址新建项目环境影响报告表
- 企业供应商评审实施方案
- 专项3 词语(精讲课件)-【中职专用】2025年对口招生语文二轮复习专项突破(湖南专用)
评论
0/150
提交评论