数据结构答案(7,8,9章)3.docxVIP

第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. 图A．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 50 3 6 1 5 4 2建议：0 1 3 4 2 5 6（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 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（建议：0 1 2 3 4 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棵生成树。（以任意一顶点为起点，得到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.