内容发布更新时间 : 2024/6/24 2:59:14星期一 下面是文章的全部内容请认真阅读。

第7章 图 自测卷解答 姓名 班级

题号 题分 得分 一 16 二 20 三 24

四 10 五 30 总分 100 一、单选题（每题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出发按深度优先遍历的结点

?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??A．0 2 4 3 1 5 6

B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 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 3 4 2

5 6

（ B ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

A． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2

5 6

（ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历

的结点序列是

A． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5

6

（ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3

（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是

A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

（ A ）14. 深度优先遍历类似于二叉树的

A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ D ）15. 广度优先遍历类似于二叉树的

A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ A ）16. 任何一个无向连通图的最小生成树

A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存

在

（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯

一）

二、填空题（每空1分，共20分）

1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。

2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。

3. 如果n个顶点的图是一个环，则它有 n 棵生成树。

4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。

5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。

6. 设有一稀疏图G，则G采用 邻接表 存储较省空间。