第 7 章 《图》习题参考答案一、单选题(每题 1 分，共 16 分)C )1. 在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2B. 1C. 2D. 4B)2. 在一个有向图中，A．1/2所有顶点的入度之和等于所有顶点的出度之和的倍。B. 1C. 2D. 4B)3. 有 8 个结点的无向图最多有条边。A．14B. 28C. 56D. 112C)4. 有 8 个结点的无向连通图最少有条边。A．5B. 6C. 7D. 8C)5. 有 8 个结点的有向完全图有条边。A．14B. 28C. 56D. 112B)6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B. 队列C. 树D. 图A)7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A．栈B. 队列C. 树D. 图C)8. 已知图的邻接矩阵~0 111101~1 0010011 00 010 0110011010110100 00 110 11 10 001 0，根据算法思想，则从顶点 0 出发按深度优先遍历的结点序列是A．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2((((((((( D )9. 已知图的邻接矩阵同上题 8，根据算法，则从顶点 0 出发，按深度优先遍历的结点序列是A． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5( D )10. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是( A )11. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是( A )12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历( D )13. 广度优先遍历类似于二叉树的A．先序遍历B. 中序遍历( A )14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵(注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一)二、填空题(每空 1 分，共 20 分)1.图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。2.有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 出度 。3.如果 n 个顶点的图是一个环，则它有 n 棵生成树。 (以任意一顶点为起点，得到 n-1 条边)4.n 个顶点 e 条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n 2 ) 。5.n 个顶点 e 条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。6.设有一稀疏图 G，则 G 采用 邻接表 存储较省空间。7.设有一稠密图 G，则 G...
