《数据结构》吕云翔编著第6章图习题解答.doc

《《数据结构》吕云翔编著第6章图习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章图习题解答一、选择题1.某无向图的邻接矩阵A=，可以看出该图共有（）个顶点A.3B.6C.9D.以上答案均不正确【解答】A2．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）A上三角矩阵B下三角矩阵C对称矩阵D无规律【解答】C，D3．下列命题正确的是（）。A一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一【解答】B4.在一个具有n个顶点的有向完全图中包含有（）条边：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解

2、答】B5．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。　Ak　Bn　Cn-k　D1【解答】C6．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。　A逆拓扑有序B拓扑有序C无序　D深度优先遍历序列【解答】A7.关键路径是AOE网中（）。A从源点到终点的最长路径B从源点到终点的最长路径C最长的回路　D最短的回路【解答】A二、填空题1.设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)

3、2.任何连通图的连通分量只有一个，即是（）。【解答】其自身3.图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表4.已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和6.有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度7.图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列8.对于含有n个

4、顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)9.如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路10.在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi,vj,vk的相对次序为（）。注：书中题目出错【解答】vi,vj,vk11．在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 【解答】 2  12. n个顶点的强连通图至少有（  ）条边，其形状是（ ）。【解答】  n 环状13

5、含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。 【解答】n-1 14对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。 【解答】n*n15.图的生成树（  ），n个顶点的生成树有（ ）条边。【解答】唯一性不能确定 n-1 16.一个无环子图 ⑺ G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。【解答】9三、算法设计题本章算法题了解即可