大连东软数据结构题库全5

《大连东软数据结构题库全5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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个顶点的连通图中的任意一条简单路径，其长度

2、不可能超过（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

3、（n﹥0）个顶点的连通无向图各顶点的度之和最少为__2(n-1)______。4②具有n个顶点的无向完全图，边的总数为__n(n-1)/2_______条；而具有n个顶点的有向完全图边的总数为__n(n-1)_______条。5②在有n个顶点的有向图中，每个顶点的度最大可达__2(n-1)_______。6②在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__n____条弧。【合肥工业大学2000】7②n个顶点的连通无向图，其边的条数至少为__n-1____。【哈尔滨工业大学2000】8②N个顶点的连通图的生成树含有_n-1_____条边。【中山大学

4、1998】9②一个连通图的__生成树____是一个极小连通子图。【重庆大学2000】三、判断题（T）1①如果无向图中各个顶点的度都大于2，则该图中必有回路。（F）2①一个图的子图可以是空图，顶点个数为0。（T）3①有n（n≥1）个顶点的有向强连通图最少有n条边。（T）4②树中的结点和图中的顶点就是指数据结构中的数据元素。【青岛大学2001】（F）5②在n个结点的无向图中，若边数大于n-1，则该图必是连通图。【中科院软件所1997】（T）6②强连通图的各顶点间均可达。【北京邮电大学2000】（F）7②强连通分量是无向图的极大强连通子图。【北京邮电大学2002】（F）8

5、②连通分量指的是有向图中的极大连通子图。【燕山大学1998】四、简答题1③设连通图G如图所示。（1）如果有关结点，请找出所有关结点。（2）如果想把该连通图变成重连通图，至少在图中加几条边？如何加？图5.591题图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．对称矩阵3②对于一个有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（D）。A．

6、NB．（N－1）*（N－1）C．N－1D．N*N4③设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（A）。2A．O（n）B．O（e）C．O（n+e）D．O（n）5②对于具有e条边的无向图，它的邻接表中有（D）个边结点。A．e-1B．eC．2（e-1）D．2e6③下面结构中最适于表示稀疏无向图的是（E），适于表示稀疏有向图的是（D）。【北京工业大学2001】A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表二、填空题1①用邻接矩阵存储图，占用存储空间数与图中顶点个数___n有_____关，与边数__无______关。2①

7、邻接表和十字链表适合于存储___有向______图，邻接多重表适合于存储____无向_____图。3②在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是__第i列非零元素个数____。【青岛大学2002】4②在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的___度______；对于有向图来说等于该顶点的___出度______。【燕山大学2001】5②对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为__n____，邻接表的边结点个数为__2e____。【青岛大学2002】三、判断题（T）1①用邻接矩阵存储一个图时，