[数据结构第7章习题答案.doc
文本预览下载声明
第7章 《图》习题参考答案
一、单选题(每题1分,共16分)
( C )1. 在一个图中,所有顶点的度数之和等于图的边数的 倍。
A.1/2 B. 1 C. 2 D. 4
( B )2. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 倍。
A.1/2 B. 1 C. 2 D. 4
( B )3. 有8个结点的无向图最多有 条边。
A.14 B. 28 C. 56 D. 112
( C )4. 有8个结点的无向连通图最少有 条边。
A.5 B. 6 C. 7 D. 8
( C )5. 有8个结点的有向完全图有 条边。
A.14 B. 28 C. 56 D. 112
( B )6. 用邻接表表示图进行广度优先遍历时,通常是采用 来实现算法的。
A.栈 B. 队列 C. 树 D. 图
( A )7. 用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。
A.栈 B. 队列 C. 树 D. 图
( C )8. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是
( 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. 中序遍历 C. 后序遍历 D. 层次遍历
( D )13. 广度优先遍历类似于二叉树的
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
( A )14. 任何一个无向连通图的最小生成树
A.只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
(注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一)
二、填空题(每空1分,共20分)
1. 图有 邻接矩阵 、 邻接表 等存储结构,遍历图有 深度优先遍历 、 广度优先遍历 等方法。
2. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 出度 。
3. 如果n个顶点的图是一个环,则它有 n 棵生成树。 (以任意一顶点为起点,得到n-1条边)
4. n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为 O(n2) 。
5. n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 O(n+e) 。
6. 设有一稀疏图G,则G采用 邻接表 存储较省空间。
7. 设有一稠密图G,则G采用 邻接矩阵 存储较省空间。
8. 图的逆邻接表存储结构只适用于 有向 图。
9. 已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。
10. 图的深度优先遍历序列 不是 惟一的。
11. n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为 O(n2) ;若采用邻接表存储时,该算法的时间复杂度为 O(n+e) 。
12. n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为 O(n2) ;若采用邻接表存储,该算法的时间复杂度为 O(n+e) 。
13. 图的BFS生成树的树高比DFS生成树的树高 小或相等
显示全部