《数据结构》第八章习题参考答案

《数据结构》第八章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。(×)2、有e条边的无向图，在邻接表中有e个结点。（×）3、强连通图的各顶点间均可达。（√）4、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（×）5、一个网（带权图）都有唯一的最小生成树。(×)6、最小生成树问题是构造连通网的最小代价生成树。(√)7、关键路径是AOE网中从源点到终点的最长路径。（√）8、在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（√）9、n个顶点的完全有向图的边数为n(n-1)。（√）10、稀疏图的存储结构采用邻接表比较合适。（√）11、在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。（√）二、单项选择题1．具有4个顶点的无向完全（边数为n*(n-1)/2）图有（A）条边。A．6B．12C．16D．202．下列哪一种图的邻接矩阵是对称矩阵？（B）A．有向图B．无向图C．AOV网D．AOE网3、在图采用邻接矩阵存储时，求最小生成树的Prim算法的时间复杂度为(C)。A.O(n)B.O(n+e)C.O(n2)D.O(n3)4、(1).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是（A）。A．(1),(2),(3)B．(1)C．(1),(3)D．(2),(3)5、下列说法不正确的是（C）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程三、填空题1、判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图_。3、G是一个非连通无向图，共有28条边，则该图至少有__9__个顶点。4、在有n个顶点的有向图中，每个顶点的度最大可达_2(n-1)_____。5、有N个顶点的有向图，至少需要量__N____条弧才能保证是连通的。6、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度__；对于有向图来说等于该顶点的__出度__。7、对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为__n____，邻接表的边结点个数为__2e____。8、求图的最小生成树有两种算法，_克鲁斯卡尔（Kruskal）_算法适合于求稀疏图的最小生成树。四、综合题1、按下图所示，画出它的广度优先生成树和深度优先生成树(A为源点)。【解答】注:答案并不唯一GACBEFDGDFS生成树ACBEFDBFS生成树ACBEFDG2、课本P3928.1题【解答】（1）不是强连通图（2）简单路径如：D-B-C-F（3）略（4）邻接表见图，其他略3、课本P3928.2题【解答】（1）邻接矩阵表示：无向图的边数为矩阵中非零元素的个数/2;有向图的边数为矩阵中非零元素的个数。邻接表表示时：无向图的边数为邻接表中边结点的个数/2；有向图的边数为邻接表中边结点的个数。（2）邻接矩阵表示：顶点i和j是否有边只需看i行j列（或j行i列）矩阵元素是否非零;邻接表表示时：看i顶点（或j顶点）的边结点链表中是否存在地址指向j顶点（或i顶点）的结点。（3）邻接矩阵表示：无向图的任意顶点的度=顶点所对应行（或列）的非零矩阵元素个数。有向图的任意顶点的度=顶点所对应行和对应列的非零矩阵元素个数之和。邻接表表示时：无向图的任意顶点的度=顶点所对应边结点链表中结点个数；有向图的任意顶点的度=邻接表中顶点所对应边链表中结点个数+逆邻接表中顶点所对应边链表中结点个数；4、课本P3928.3题【解答】n个顶点的无向连通图至少有n-1条边，n个顶点的无向强连通图至少有n(n-1)/2条边；n个顶点的有向连通图至少有n条边，n个顶点的有向强连通图至少有n(n-1)条边。5、课本P3928.4题【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。6、课本P3928.5题【解答】一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002=1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），是稀疏矩阵。7、课本P3928.7题【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有的顶点访问一次，时间代价是O(n+e)。ABCDEF132451448.1（4）邻接表8、课本P3928.8题【解答】DFS和BFS遍历可分别采用栈和队列来暂存顶点来实现非递归高效遍历算法。如果要求生成树高度最小，应采用BFS遍历。9、课本P3928.9题【解答】采用邻接表存储的图的DFS遍历类似于二叉树的先序遍历，BFS遍历类似于二叉树的按层遍历。10、课本P3928.10题【解答】DFS和BFS树都不唯一，只是给出了一种解答。11、课本P3938.17题(1)【解答】此工程最早完成时间为43。关键路径为1,33,22,55,6(2)(3)略12、课本P3958.24题【解答】A-B:10A-B-D:15A-B-D-C:17A-B-D-E:178-10DFS123458-10BFS12345