数据结构 李学刚 单元5 同步训练及答案

1、单元5 同步训练一、单项选择题1在一个图中, 所有顶点的度数之和等于所有边数的（ ）倍。A1/2B1C2D42在一个有向图中, 所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。A1/2B1C2D4 3一个有n个顶点的无向图最多有（ ）条边。AnBn(n-1)Cn(n-1)/2D2n4具有4个顶点的无向完全图有（ ）条边。A6B12C16D205具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。A5B6C7D86在一个具有n个顶点的无向图中, 要连通全部顶点至少需要（ ）条边。AnBn+1Cn-1Dn/27对于一个具有n个顶点的无向图, 若采用邻接矩阵表示, 则该矩阵含元素的个数是（ ）。AnB(n-1)2Cn-1Dn28含n个顶点的连通图中的任何一条简单路径，其长度不可能超过（ ）。A1Bn/2Cn-1Dn9对于一个具有n个顶点和e条边的无向图, 若采用邻接表表示, 则表头向量的大小为（ ）。AnBn+1Cn-1Dn+e10已知无向图如图5-19所示, 若从顶点a出发按深度搜索法进行遍历, 则可能得到的一种顶点序列为（ ）。Aa,b,e,c,d,fBa,c,f,e,b,d

2、 Ca,e,b,c,f,dDa,e,d,f,c,b123434225454图5-20 选择题第11题的图图5-19 选择题第10题的图abcedf11已知一有向图的邻接表存储结构如图5-20所示。根据有向图的深度优先遍历算法, 从顶点v1出发, 所得到的顶点序列是（ ）。Av1,v2,v3,v5, v4Bv1,v2,v3,v4,v5Cv1,v3,v4,v5,v2Dv1,v4, v3,v5,v212已知一有向图的邻接表存储结构如上图所示，根据有向图的广度度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。Av1,v2,v3,v4,v5Bv1,v3,v2,v4,v5Cv1,v2,v3,v5,v4Dv1,v4, v3,v5,v213 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。A先序遍历B中序遍历C后序遍历D按层遍历14在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。AeB2eCn2-eDn2-2e15任何一个无向连通图的最小生成树（ ）。A只有一棵B一棵或多棵C一定有多棵D可能不存在二、问题解答题1在图5-21所示的有向图中： 该图是强连通的吗? 若不是

3、，则给出其强连通分量。 请给出所有的简单路径。 请给出每个顶点的度，入度和出度。1图5-21第1题的图V1V2V3V43242211221abdefghc图5-22 第4题的图2对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题？图中有多少条边?：任意两个顶点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生成树(或生成森林)的算法，要求打印出所有的树边。2试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(ij)之间是否有路径。单元5参考答案一、选择题1、C2、B3、

4、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、v1v2v4 v1、v1v3v4 v1、v2v4v1 v2、v2v4v1 v3、v3v4v1 v3、v3v4v1 v2、v4v1v2 v4、v4v1v3 v4 (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、答：图中有多少条边?：邻接矩阵表示：无向图：邻接矩阵中非零元个数的一半或上三角矩阵非零元的个数或下三角矩阵非零元的个数。有向图：邻接矩阵中非零元的个数。邻接表表示：无向图：每个顶点边表结点个数的和的一半。有向图：每个顶点边表结点个数

5、的和。任意两个顶点i和j是否有边相连?邻接矩阵表示：无向图：邻接矩阵中第i行第j列（或第j行第i列）元素是否非零。有向图：邻接矩阵中第i行第j列元素是否非零。邻接表表示：无向图：第i个（第j个）顶点的边表是否有值为j（i）的结点。有向图：第i个顶点的边表是否有值为j的结点。任意一个顶点的度是多少?邻接矩阵表示：无向图：顶点vi的度为：第i行（或第i列）非零元的个数。有向图：顶点vi的度为：第i行非零元的个数与第i列非零元的个数的和（顶点vi的出度为：第i行非零元的个数，入度为：第i列非零元的个数）。邻接表表示：无向图：该顶点边表结点的个数。有向图：顶点vi的度为：该顶点边表结点的个数与其他顶点的边表中值为i的结点个数的和。三、算法设计题1、答：(1)求DFS生成树typedef enumFALSE，TRUEBoolean；/FALSE为0，TRUE为1Boolean visitedMaxVertexNum； /访问标志向量是全局量void DFSTraverseTREE(ALGraph *G) /求深度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，/算法完全与此相同,只要将D

6、FSTree(G，i)改为DFSMTree(G，i)即可int i；for(i=0;in;i+)visitedi=FALSE； /标志向量初始化for(i=0;in；i+)if(!visitedi) /vi未访问过DFSTree(G，i)； /以vi为源点开始DFS搜索,求DFS生成树的边/DFSTraversevoid DFSTree(ALGraph *G，int i)/以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树(生成森林)的边EdgeNode *p；visitedi=TRUE； /标记vi已访问p=G-adjlisti.firstedge； /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p-adjvexif (!visitedp-adjvex)/若vj尚未被访问printf(%c,%c)n,G-adjlisti.vertex,G-adjlistp-adjvex.vertex)；/ 打印边DFSTree(g，p-adjvex);/则以Vj为出发点向纵深搜索p=p-next； /找vi的下一邻接点/DFSvoid DFSMTree(MGrap

7、h *G，int i) /以vi为出发点对邻接矩阵表示的图G进行深度优先搜索,打印生成树(生成森林)的边int j；visitedi=TRUE；for(j=0；jn；j+) /依次搜索vi的邻接点if(G-edgesij=1&!visitedj)printf(%c,%c)n,G-vexsi,G-vexsj);/ 打印边DFSMTree(G，j);/(vi，vj)E，且vj未访问过，故vj为新出发点/DFSMTree(2)求BFS生成树typedef enumFALSE，TRUEBoolean；/FALSE为0，TRUE为1Boolean visitedMaxVertexNum； /访问标志向量是全局量void BFSTraverseTREE(ALGraph *G) /求广度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，/算法完全与此相同,只要将BFSTree(G，i)改为BFSMTree(G，i)即可 int i； for(i=0;in;i+) visitedi=FALSE； /标志向量初始化 for(i=0;in；i+)if(!visitedi) /vi未访问过BFSTree(G，i)； /以vi为源点开始BFS搜索,求BFS生成树的边/BFSTraversevoid BFSTree(ALGraph*G，int k)/ 以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边int i；CirQueue Q； /须将队列定义中DataType改为intEdgeNode *p；InitQueue(&Q)；/队列初始化visitedk=TRUE；EnQueue(&Q，k)；/vk已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)； /相当于vi出队p=G-adjlisti.firstedge； /取vi

《数据结构 李学刚 单元5 同步训练及答案》由会员清晨86****784分享，可在线阅读，更多相关《数据结构 李学刚 单元5 同步训练及答案》请在金锄头文库上搜索。