您好,欢迎访问三七文档
。-可编辑修改-数据结构与算法上机作业第四章图。-可编辑修改-一、选择题1、在一个无向图中,所有顶点的度数之和等于所有边数的C倍。A.1/2B.1C.2D.42、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的B倍。A.1/2B.1C.2D.43、G是一个非连通无向图,共有28条边,则该图至少有D个顶点。A.6B.7C.8D.94、有n个顶点的图的邻接矩阵使用B数组存储的。A.一维B.n行n列C.任意行n列D.n行任意列5、对于一个具有n个顶点和e条边的无向图,采用邻接表表示,则表头数组大小至少为(假设下标为0的数组参与使用)A。A.n-1B.n+1C.nD.n+e6、下列说法正确的是C。A.有向图的邻接矩阵一定是不对称的B.有向图的邻接矩阵一定是对称的C.无向图的邻接矩阵一定是对称的D.无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的A:A.先根遍历B.中根遍历C.后根遍历D.层次遍历8、广度优先遍历类似与二叉树的D:A.先根遍历B.中根遍历C.后根遍历D.层次遍历9、下列关于开放树(FreeTree)的说法错误的是C:。-可编辑修改-A.具有n个结点的开放树包含n-1条边B.开放树没有回路C.开放树可以是非连通图D.在开放树中任意加一条边,一定会产生回路10、在如下图所示的图中,从顶点a出发,按深度优先遍历,则可能得到的一种顶点的序列为。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b11、在如上图所示的图中,从顶点a出发,按广度优先遍历,则可能得到的一种顶点的序列为。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,e,b,c,f,dD.a,e,d,f,c,b12、设网(带权的图)有n个顶点和e条边,则采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为C。A.O(n)B.O(n+e)C.O(n2)D.O(n3)13、设图有n个顶点和e条边,求解最短路径的Floyd算法的时间复杂度为O。A.O(n)B.O(n+e)C.O(n2)D.O(n3)14、最小生成树是指C。。-可编辑修改-A.由连通网所得到的边数最少的生成树。B.由连通网所得到的顶点数相对较少的生成树。C.连通网中所有生成树中权值之和为最小的生成树。D.连通网的极小连通子图。15、下面关于工程计划的AOE网的叙述中,不正确的是B。A.关键活动不按期完成就会影响整个工程的完成时间。B.任何一个关键活动提前完成,那么整个工程将会提前完成。C.所有关键活动都提前完成,那么整个工程将会提前完成。D.某些关键工程若提前完成,那么整个工程将会提前完成。16、在AOE网中,始点和汇点的个数为C。A.1个始点,若干个汇点B.若干个始点,若干个汇点C.若干个始点,1个汇点C.1个始点,1个汇点17、在下图所示的无向图中,从顶点v1开始采用Prim算法生成最小生成树,算法过程中产生的顶点次序为B。A.v1,v3,v4,v2,v5,v6B.v1,v3,v6,v2,v5,v4C.v1,v2,v3,v4,v5,v6D.v1,v3,v6,v4,v2,v518、在上图所示的途中,采用Cruskal算法生成最小生成树,过程中产生的边的次序是C。A.(v1,v2),(v2,v3),(v5,v6),(v1,v5)B.(v1,v3),(v2,v6),(v2,v5),(v1,v4)。-可编辑修改-C.(v1,v3),(v2,v5),(v3,v6),(v4,v5)D.(v2,v5),(v1,v3),(v5,v6),(v4,v5)19、如下图所示的图中,其中一个拓扑排序的结果是A。A.v1→v2→v3→v6→v4→v5→v7→v8B.v1→v2→v3→v4→v5→v6→v7→v8C.v1→v6→v4→v5→v2→v3→v7→v8D.v1→v6→v2→v3→v7→v8→v4→v520、在下图所示的AOE网中,活动a9的最早开始时间为B。A.13B.14C.15D.1621、在上图所示的AOE网中,活动a4的最迟开始时间为DA.2B.3C.4D.522、设图有n个顶点和e条边,当用邻接表表示该图时,则求解最短路径的Dijkstra算法的时间复杂度为O。A.O(n)B.O(n+e)C.O(e)D.O(n2)。-可编辑修改-二、填空题1、若无向图G中顶点数为n,则图G至多有n(n-1)/2条边;若G为有向图,则图G至多有n(n-1)条边。2、图的存储结构主要有两种,分别是邻接表和邻接矩阵。3、若G是有向图,则把邻接到顶点v的顶点数目或边数目称为顶点v的入度;把邻接于顶点v的顶点数目或边数目称为顶点v的出度。4、已知一个图的邻接矩阵表示,计算第j个顶点的入度的方法是第j行非0元素的个数,计算第j个顶点的出度的方法是第j列非0元素的个数。5、若将图中的每条边都赋予一个权,则称这种带权的图为网络。6、无论是有向图还是无向图,顶点数n、边数e和各顶点的度D(vi)之间的关系为:。7、若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为回路或环。8、如果图中任意一对顶点都是连通的,则称此图是连通图;非连通图的极大连通子图叫做连通分量。9、创建一个邻接矩阵图的复杂度是O(n*n);创建一个链接表图的复杂度是O(n+e)。10、图的遍历有深度优先遍历和广度优先遍历等方法。。-可编辑修改-11、在深度优先搜索和广度优先搜索中,都采用visited[i]=0(false)的方式设置第i个顶点为new,而采用visited[i]=1(true)的方式标识第i个结点为old。12、由于深度优先算法的特点,深度优先往往采用递归的方式实现。13、由于广度优先算法的特点,在广度优先实现过程中,往往要借助于另一种数据结构队列实现。14、在深度优先搜索和广度优先搜索中,在搜索过程中所经过的边都称为搜索边。15、连通而且无环路的无向图称为开放数。16、对于含有n个顶点e条边的连通图,利用Prim算法求其最小生成树的时间复杂度为O(n*n),利用Kruscal算法求最小生成树的时间复杂度是O(e*lge)。3、顶点表示活动的网简称为AOV;边表示活动的网简称为AOE。17、一个含有n个顶点的无向连通图,其每条边的权重都是a(a0),则其最小生成树的权重等于(n-1)*a。18、具有n个顶点的有向图,如果采用邻接矩阵表示该图,则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是O(n*n);如果采用邻接表表示该图,则时间复杂度为O(e)。19、在用Dijkstra算法求单源最短路径的过程中,将顶点集合V划分为两个集合S和V-S,其中S中的点为最短路径已确定的顶点集合,V-S中的点为最短路径未确定的顶点集合。20、求每一对顶点之间的最短路径,可以用两种方法,一种是分别对每个顶点采用算法,另一种方法是。。-可编辑修改-21、假设有向图的邻接矩阵C的传递闭包为A,则A[i][j]=1表示。22、有向图的中心点是指具有最小偏心度的顶点。三、已知一个无向图如下图所示,试给出该图的邻接矩阵和邻接表存储示意图(画图,分别用矩阵和数组链表图表示),并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。代码:#includeiostreamusingnamespacestd;#definemax_vexNum26//最大顶点个数typedefstruct{intvex_num,arc_num;//顶点数,边数intcount;//记录当前顶点数charvexs[max_vexNum];//顶点向量doublearcs[max_vexNum][max_vexNum];//邻接矩阵}Graph;。-可编辑修改-//添加一个新的顶点charNewNode(Graph*G,charv){G-vexs[G-count]=v;G-count++;returnv;}//寻找某个顶点的位置intFindPosition(Graph*G,charv){for(inti=0;iG-count;i++){if(v==G-vexs[i])returni;}}voidDelete(Graph*G,charv){//先删除点inti,j;。-可编辑修改-inttemp_count=G-count;i=FindPosition(G,v);for(j=i;jtemp_count;j++)G-vexs[j]=G-vexs[j+1];G-count--;//删除边//先删除行intp=i;//记住位置for(i=p;itemp_count-1;i++)for(j=0;jtemp_count;j++)G-arcs[i][j]=G-arcs[i+1][j];//再删除列for(i=p;itemp_count-1;i++)for(j=0;jtemp_count;j++)G-arcs[j][i]=G-arcs[j][i+1];}。-可编辑修改-//建立v1与v2的一条边voidSetSoucc(Graph*G,charv1,charv2){//先找到对应的定的位置inti,j;inttemp_count=G-count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//没有找到return;//找到后,A[i][j]=0;vexs[j][i]=0;G-arcs[i][j]=1;G-arcs[j][i]=1;}voidDelSucc(Graph*G,charv1,charv2){inti,j;inttemp_count=G-count;i=FindPosition(G,v1);。-可编辑修改-j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//没有找到return;//找到后,A[i][j]=0;vexs[j][i]=0;G-arcs[i][j]=0;G-arcs[j][i]=0;}//判断v1y与v2是否连接boolisEdge(Graph*G,charv1,charv2){inti,j;inttemp_count=G-count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//没有找到return-1;。-可编辑修改-if(G-arcs[i][j]==1)returntrue;returnfalse;}voidPrint(Graph*G){inti,j;for(i=0;iG-count;i++){for(j=0;jG-count;j++)coutG-arcs[i][j];coutendl;}coutendl;}Graph*G=newGraph;//初始化intmain(){G-count=0;。-可编辑修改-NewNode(G,'A');NewNode(G,'B');NewNode(G,'C');NewNode(G,'D');//插入边SetSoucc(G,'A','B');SetSoucc(G,'A','D');SetSoucc(G,'C','B');Print(G);//删除一个顶点Delete(G,'C');Print(G);//删除边DelSucc(G,'A','D');Print(G);if(isEdge(G,'A','B'))coutA与B右边endl;。-可编辑修改-return0;}四、已知一个有向图如下图所示,试给出图的邻接矩阵和邻接表存储示意图(画图,分别用矩阵和数组链表图表示),并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。代码:#includeiostream#incl
本文标题:南工大第四章-图
链接地址:https://www.777doc.com/doc-5662710 .html