数据结构第7章习题答案

《数据结构第7章习题答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第7章《图》习题参考答案一、单选题（每题1分，共16分）（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。A.1/2B.1C.2D.4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。De4A.1/2B.1C.23.有8个结点的无向图最多有.A.14B.28条边。C・56D.1124.有8个结点的无向连通图最少有A.5Be6条边。C.7D.85.有8个结点的有向完全图有.A.14B.28条边。C・56D.112来实现算法的。D.图（叵］）&已知图的邻接矩阵，根据算法思想则从顶点0出发按深度优先遍历的结点序列是_011110r10010011000100

2、1100110101101000011011100010A.0243156B.0136542C.0134256D.0361542用邻接表表示图进行广度优先遍历时，通常是采用A.栈B.队列C.树（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A.栈B.队列C.树D.图（D）9.已知图的邻接矩阵同上题8,根据算法，则从顶点0出发，按深度优先遍历的结点序列是A.0243156B.0135642C・0423165D・0123465（D）10.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是L123/n)—0—2/v013/(*2Va

3、—0一2/A.0132C・0321B・0231D・0123（A）H・已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是VL321/n)V20/V231!・0/'w一201/(A)12.深度优先遍历类似于二叉树的A・0321C・0132B・0123D・0312A.先序遍历B.中序遍历C.后序遍历D.层次遍历C.后序遍历D・层次遍历C.一定有多棵D.可能不存在(D)13.广度优先遍历类似于二叉树的A.先序遍历B.中序遍历(A)14.任何一个无向连通图的最小生成树A.只有一棵B.一棵或多棵(注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯

4、一)二、填空题(每空1分，共20分)1.图有邻接矩阵、邻接表等存储结构,遍历图有深度优先遍历、广度优先遍历等方法。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。3.如果n个顶点的图是一个环，则它有n棵生成树。(以任意一顶点为起点，得到n・l条边)4.n个顶点e条边的图，若釆用邻接矩阵存储，则空间复杂度为0(()。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为Om+c)。6・设有一稀疏图G,则G采用邻接表存储较省空间。7.设有一稠密图G,则G釆用邻接矩阵存储较省空间。&图的逆邻接表存储结构只适用于有向图。9.已知一个图的邻接矩阵表示，删除所

5、有从第i个顶点岀发的方法是骼邻接矩阵的第i行全部置。10・图的深度优先遍历序列不是惟一的。11・n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(i>2)；若采用邻接表存储时，该算法的时间复杂度为O(n+e)。12・n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为0(()；若采用邻接表存储，该算法的时间复杂度为O(n+e)。13.图的BFS生成树的树髙比DFS生成树的树高」小或相等。13.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为()(『)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是()(elo跑

6、e)若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。16.若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。17.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。18・拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。三、简答题(每题6分，共24分)1.【严题集7・1①】已知如图所示的有向图，请给出该图的:(1)每个顶点的入/出度;(2)邻接矩阵；(3)邻接表;(4)逆邻接表。7.1(1)答案:顶点123456入度321122岀度022313(3)邻接表顶点123456

7、入度出度(2)邻接矩阵'010010010010001000100000001010'01100.(4)逆邻接表XX548°°6O88858206ggX63O2XX987O3XXX55076543505888540559gXXro43xxxxL°°最小生成树f1.【严题集7.7②】请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树o解：设起点为ao可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）！邻接矩阵为：PRIM算法（横向变化）:V