数据结构单元8练习参考答案

《数据结构单元8练习参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单元练习8一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）图可以没有边，但不能没有顶点。（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。（ㄨ）（3）邻接表只能用于有向图的存储。（√）（4）一个图的邻接矩阵表示是唯一的。（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（ㄨ）（6）有向图不能进行广度优先遍历。（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（√）（8）存储

2、无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。二．填空题（1）图常用的存储方式有邻接矩阵和邻接表等。（2）图的遍历有：深度优先搜和广度优先搜等方法。（3）有n条边的无向图邻接矩阵中，1的个数是_2n____。（4）有向图的边也称为_弧___。（5）图的邻接矩阵表示法是表示__顶点___

3、_之间相邻关系的矩阵。（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的__出度____。（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。（9）设有一稀疏图G，则G采用_邻接表____存储比较节省空间。（10）设有一稠密图G，则G采用_邻接矩阵____存储比较节省空间。（11）图的逆邻接表存储结构只适用于__有向____图。（12）n个顶点的完全无向图有n(n-1)/2_条边。（13）有向图的邻接表表示适于

4、求顶点的出度。（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的入度。（15）对于具有n个顶点的图，其生成树有且仅有n-1条边。（16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e个结点。（17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。（18）无向图的邻接矩阵一定是对称矩阵。（1）一个连通网的最小生成树是该图所有生成树中权最小的生成树。（2）若要求一个稠密图G的最小生成树，最好用Prim算法来求解。三．选择题（1）在一个图中，所有顶点的度数之和

5、等于图的边数的(C)倍。A．1/2B.1C.2D.4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B)倍。A．1/2B.1C.2D.4（3）对于一个具有n个顶点的有向图的边数最多有（B）。A．nB．n(n-1)C．n(n-1)/2D．2n（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。A．nB．n+1C．n-1D．n/2（5）有8个结点的有向完全图有(C)条边。A．14B.28C.56D.112（6）深度优先遍历类似于二叉树的(A)。A．先序遍历B．中序遍历C．后序遍历D．

6、层次遍历（7）广度优先遍历类似于二叉树的(D)。A．先序遍历B．中序遍历C．后序遍历D．层次遍历（8）任何一个无向连通图的最小生成树(A)。A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在（9）无向图顶点v的度是关联于该顶点（B）的数目。A．顶点B．边C．序号D．下标（10）有n个顶点的无向图的邻接矩阵是用（B）数组存储。A．一维B．n行n列C．任意行n列D．n行任意列（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。A．n-1B．n+1C．nD．n+e（12）在图的表示法

7、中，表示形式唯一的是（A）。A．邻接矩阵表示法B．邻接表表示法C．逆邻接表表示法D．邻接表和逆邻接表表示法（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。A．nB．eC．2nD．2e（14）下列图中，度为3的结点是（B）。12354A．V1B.V2C.V3D.V412354（15）下列图是（A）。A．连通图B.强连通图C.生成树D.无环图（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。abcfdeA．a，b，e，c，d，fB．a，c，f，e，b，dC.a

8、，e，b，c，f，dD.a，e，d，f，c，b（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。abcfdeA.a，b，e，c，d，fB.a，b，e，c，f，dC.a，e，b，c，f，dD.a，e，d，f，c，b（18）最小生成树的构造可使用（A）算法。A．prim算法B．卡尔算法C．哈夫曼算法D．迪杰斯特拉算法（19）