5.8习题5.8.1知识点：图的基本概念一、选择题1①n个顶点的连通图至少有（A）条边。A．n-1B．nC．n+1D．02①在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（B）。A.顶点序列B.边序列C.权值总和D.边的条数3①具有n个顶点的有向图最多可包含（D）条有向边。A.n-1B.nC.n（n-1）/2D.n（n-1）4①在无向图中定义顶点的度为与它相关联的（B）的数目。A.顶点B.边C.权D.权值5①一个有N个顶点的无向图中，要连通全部顶点至少需要（C）条边。A.NB.N＋1C.N－1D.N/26②含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）。A.1B.N/2C.N－1D.N7②设无向图的顶点个数为n,则该图最多有（B）条边。【清华大学1998】【西安电子科技大1998】【北京航空航天大学1999】A.n-1B.n（n-1）/2C.n（n+1）/2D.n（n-1）8②在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。【哈尔滨工业大学2001】A.1/2B.2C.1D.4二、填空题1②n（n>0）个顶点的无向图中顶点的度的最大值为___n-1____。2②n（n>0）个顶点的无向图最少有___0_______条边。3②n（n>0）个顶点的连通无向图各顶点的度之和最少为__2（n-1）__。4②具有n个顶点的无向完全图，边的总数为__n（n-1）/2___条；而具有n个顶点的有向完全图边的总数为__n（n-1）____条。1/135②在有n个顶点的有向图中，每个顶点的度最大可达__2（n-1）____。6②在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__n___条弧。【合肥工业大学2000】7②n个顶点的连通无向图，其边的条数至少为__n-1____。【哈尔滨工业大学2000】8②N个顶点的连通图的生成树含有_n-1_______条边。【中山大学1998】9②一个连通图的—生成树_______是一个极小连通子图。【重庆大学2000】三、判断题(T)1①如果无向图中各个顶点的度都大于2，则该图中必有回路。(F)2①一个图的子图可以是空图，顶点个数为0。(T)3①有n(n>l)个顶点的有向强连通图最少有n条边。(T)4②树中的结点和图中的顶点就是指数据结构中的数据元素。【青岛大学2001】(F)5②在n个结点的无向图中，若边数大于n-1,则该图必是连通图。【中科院软件所1997】(T)6②强连通图的各顶点间均可达。【北京邮电大学2000】(F)7②强连通分量是无向图的极大强连通子图。【北京邮电大学2002】(F)8②连通分量指的是有向图中的极大连通子图。【燕山大学1998】四、简答题1③设连通图G如图所示。(1)如果有关结点，请找出所有关结点。(2)如果想把该连通图变成重连通图，至少在图中加几条边？如何加？5・8・2知识点：图的存储一、选择题1②在n个顶点的有向无环图的邻接矩阵中至少有(C)个零元素。A.nB.n(n-1)/2C.n(n+1)/2D.n(n-1)2②若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个(D)。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵2/133②对于一个有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是(D)。A.NB.(N—1)*(N—1)C.N—1D.N*N4③设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是(A)。A.O(n)B.O(e)C.O(n+e)D.O(£)5②对于具有e条边的无向图，它的邻接表中有(D)个边结点。A.e-1B.eC.2(e-1)D.2e6③下面结构中最适于表示稀疏无向图的是(E),适于表示稀疏有向图的是(D)。【北京工业大学2001】A.邻接矩阵B.逆邻接表C.邻接多重表D.十字链表E.邻接表二、填空题1①用邻接矩阵存储图，占用存储空间数与图中顶点个数—n有_______关，与边数__无_____关。2①邻接表和十字链表适合于存储有向___________图，邻接多重表适合于存储_____无向_____图。3②在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是__第i列非零元素个数___。【青岛大学2002】4②在图G的邻接表表示中，每个顶点邻接表中