第7章课练答案

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

1、第7章图自测卷解答姓名班级-＞单选题（每题1分，共16分）前两大题全部来自于全国自考参考书!题号—・二三四五总分题分1620241030100得分（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。2.3-4.5.A.1/2B.1C.2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的A.1/2B・有8个结点的无向图最多有.A.14B.28有8个结点的无向连通图最少有.A.5B・6有8个结点的有向完全图有.A.14B.28C.2倍。D.4条边。C・56条边。C.7条边。C-56D・112D・8D・112来实现算法的。D・图（冋）&已知图的邻接矩阵，根据算法

2、思想,则从顶点0出发按深度优先遍历的结点序列是用邻接表表示图进行广度优先遍历时，通常是采用A.栈B.队列C.树（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A.栈B.队列C・树D・图「011110r100100110001001100110101101000011011100010A.0243156B.0136542C.0423165D.0361542建议：0134256（D）9・已知图的邻接矩阵同上题8,根据算法，则从顶点0出发，按深度优先遍历的结点序列是A.0243156B.0135642C・0423165D・0134256（S）10.已知图的

3、邻接矩阵同上题8,根据算法，则从顶点0出发，按广度优先遍历的结点序列是A.0243651B・0136425C・0423156D・0134256（建议：0123465）（C）11・已知图的邻接矩阵同上题8,根据算法，则从顶点0出发，按广度优先遍历的结点序列是A.0243165B.0135642C-0123465D.0123456（D）12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A.0132B・0231C・0321D・0123则从顶点0出发按广度优先遍历的结点序列是A.0321B・0123D・0312C・0132C.后序遍历D.层次遍历C

4、.后序遍历De层次遍历（A）13.已知图的邻接表如下所示，根据算法,（A）14.深度优先遍历类似于二叉树的A.先序遍历B.中序遍历（D）15.广度优先遍历类似于二叉树的A.先序遍历B.中序遍历（A）16.任何一个无向连通图的最小生成树A.只有一棵B.-棵或多棵C.一定有多棵D.可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1.图有邻接矩阵、邻接表等存储结构,遍历图有深度优先遍历、广度优先遍历等方法。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。3•如果n个顶点的图是一个环，则它有n

5、棵生成树。（以任意一顶点为起点，得到n・l条边）4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为0（『）。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O（n+e）。6.设有一稀疏图G,则G釆用邻接表存储较省空间。7.设有一稠密图G,则G采用邻接矩阵存储较省空间。8.图的逆邻接表存储结构只适用于有向图。9.已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的弧方法是」将邻接矩阵的第i行全部置04.图的深度优先遍历序列」4_惟一的。5.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为()(1?)；若采用邻接表存储时，该算法的时间复杂度

6、为O(n+c)。12・ii个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为0(()；若采用邻接表存储，该算法的时间复杂度为O(n+e)。13.图的BFS生成树的树高比DFS生成树的树高小或相等14.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(i?)；用克鲁斯卡尔(Kmskal)算法的时间复杂度是O(elo亞e)。15.若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。16.若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。17.用Dijkstra算法求某一顶点到其余各顶点间的

7、最短路径是按路径长度递增的次序来得到最短路径的。18・拓扑排序算法是通过重复选择具有()个前驱顶点的过程来完成的。三、简答题(每题6分，共24分)1.【严题集7・1①】已知如图所示的有向图，请给出该图的:(1)每个顶点的入/出度;(2)邻接矩阵；(3)邻接表；(4)逆邻接表。答案:顶点123456入度321122出度0223137.1(1)顶点123456入度出度(2)邻接矩阵•o10o1oo1001000100010000000101O'01100_(3)邻接表(4)逆邻接表4IrmAXX548°°6O88858206ggX63O2XX