资源描述：
《数据结构教学全套课件(李学刚)电子资源同步训练及参考答案 单元5 同步训练及答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、单元5同步训练一、单项选择题1．在一个图中,所有顶点的度数之和等于所有边数的（）倍。A．1/2B．1C．2D．42．在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．1/2B．1C．2D．43．一个有n个顶点的无向图最多有（）条边。A．nB．n(n-1)C．n(n-1)/2D．2n4．具有4个顶点的无向完全图有（）条边。A．6B．12C．16D．205．具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A．5B．6C．7D．86．在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。A．nB．n+1C．n-1D．n/27．对于一个具有n个顶点的无
2、向图,若采用邻接矩阵表示,则该矩阵含元素的个数是（）。A．nB．(n-1)2C．n-1D．n28．含n个顶点的连通图中的任何一条简单路径，其长度不可能超过（）。A．1B．n/2C．n-1D．n9．对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（）。A．nB．n+1C．n-1D．n+e10．已知无向图如图5-19所示,若从顶点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,b12^34^342254^^5^^4^^图5-20选择题第11题的图图
3、5-19选择题第10题的图abcedf11．已知一有向图的邻接表存储结构如图5-20所示。根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是（）。A．v1,v2,v3,v5,v4B．v1,v2,v3,v4,v5C．v1,v3,v4,v5,v2D．v1,v4,v3,v5,v212．已知一有向图的邻接表存储结构如上图所示，根据有向图的广度度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。A．v1,v2,v3,v4,v5B．v1,v3,v2,v4,v5C．v1,v2,v3,v5,v4D．v1,v4,v3,v5,v213．采用邻接表存储的图的广度优先遍历算法类似于二叉树
4、的（）。A．先序遍历B．中序遍历C．后序遍历D．按层遍历14．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。A．eB．2eC．n2-eD．n2-2e15．任何一个无向连通图的最小生成树（）。A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在 二、问题解答题1．在图5-21所示的有向图中：①该图是强连通的吗?若不是，则给出其强连通分量。②请给出所有的简单路径。③请给出每个顶点的度，入度和出度。1图5-21第1题的图V1V2V3V43242211221abdefghc图5-22第4题的图2．对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题
5、？①图中有多少条边?：②任意两个顶点i和j是否有边相连?③任意一个顶点的度是多少?3．用Prim和Kruskal求最小生成树的时间复杂度各为多少?它们分别适合于哪类图?4．对图5-22所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。5．对下图所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态。V5图5-24第6题的图V2V0V4V3V6V1图5-23第5题的图5263416．试写出如图5-24所示有向图的所有拓扑序列。三、算法设计题1．试分别写出求DFS和BFS生成树(或生成森林)的算法，要求
6、打印出所有的树边。2．试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径。单元5参考答案一、选择题1、C2、B3、C4、A5、A6、C7、D8、A9、D10、D11、B12、D二、解答题1、答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：v1v2、v1v3、v2v4、v3v4、v4v1、v1v2v4、v1v3v4、v2v4v1、v3v4v1、v4v1v2、v4v1v3、v1v3v4、v1v2v4v1、v1v3v4v1、v2v4
7、v1v2、v2v4v1v3、v3v4v1v3、v3v4v1v2、v4v1v2v4、v4v1v3v4(3)每个顶点的度、入度和出度：D(v1)=3，ID(v1)=1，OD(v1)=2；D(v2)=2，D(v2)=1，OD(v2)=1；D(v3)=2，ID(v3),1，OD(v3)=1；D(v4)=3，ID(v4),2，OD(v4)=1。2、答：①图中有多少条边?：邻接矩阵表示：无向图：邻接矩阵中非零元个数的一半或上三角矩阵非零元的个数或下三角矩阵非零元的个数。有向图：邻
