第7章图单元测试(答案)

第七章图姓名：学号：一、选择题1．设无向简单图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．n22．一个n个顶点的连通无向图，其边的个数至少为（A）。A．n-1B．nC．n+1D．nlogn；3．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A．1/2B．2C．1D．44．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网5．下列有关图的遍历的说法中，不正确的是（）。A．用邻接表存储的图的深度优先搜索的时间复杂度为O(n＋e)B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征，需要采用队列结构来实现C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点访问且仅被防问一次6.求解最短路径的Floyd算法的时间复杂度为()。A．O（n）B.O（n+c）C.O（n2）D.O（n3）7.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O（n2）D.O（n3）8.右图所示的无向网的最小生成树的权为()。A．11B．9C．14D．129.关键路径是AOE网中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路10．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成二、判断题1.有e条边的无向图，在邻接表中有e个结点。（×）2.强连通图的各顶点间均可达。（√）v0v1v3v4v21472531v562v0v1v3v4v21472531v5623.十字链表是无向图的一种存储结构。（×）4.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（√）5.带权的连通无向图的最小生成树是唯一的。（×）6.AOV网的含义是以边表示活动的网。（×）7.在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（×）三、应用题1.已知一个无向图G的邻接表存储表示如下，试写出从顶点A出发进行深度和广度优先遍历得到的顶点序列，并判断该图的连通性。答：深度优先遍历序列：ABDHECFG广度优先遍历序列：ABCDEFGH该图是连通图。2.下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出你的选择，并写出这n-1条路的总代价。H7G6F5E4D3C2B1A01^203^405^61^71^72^62^53^412345671812510815232520674答：本题就是寻找无向连通网的一棵最小生成树问题，你可以选择prim或Kruscal任一算法求解。最小生成树（略）。最小生成树的代价为：533.叙述拓扑排序的基本思想，并对如下的有向图，写出两个不同的拓扑序列。答：拓扑排序的基本思想a)在图中找一个没有前驱的顶点，并把它输出；b)从图中删除该顶点及与它相关的弧；c)重复第1、2步，直到所有顶点都输出（顶点输出序列为拓扑序列）或剩余顶点中找不到没有前驱的顶点（图中存在回路）。拓扑序列：v1,v6,v4,v3,v2,v5v6,v1,v4,v3,v5,v2四、算法设计题1.已知图的邻接表存储定义如下：#defineMAX_VEX_NUM20;//最大顶点个数typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧v1v2v4v3v6v5}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//顶点个数和弧数intkind;//图的种类标志}ALGraph;(1)试写出计算图中所有顶点的入度算法，并将每个顶点的入度存入数组indegree中；voidFindIndegree(ALGraphG,intindegree[]){for(i=0;iG.vexnum;i++)indegree[i]=0;for(i=0;iG.vexnum;i++)for(p=G.vertices[i].firstarc;p;p=p-nextarc)++indegree[p-adjvex];}(2)试写出计算图中所有顶点的出度算法，并将每个顶点的入度存入数组outdegree中；voidFindOutdegree(ALGraphG,intoutdegree[]){for(i=0;iG.vexnum;i++)outdegree[i]=0;for(i=0;iG.vexnum;i++)for(p=G.vertices[i].firstarc;p;p=p-nextarc)++outdegree[i];}