华中师大C语言数据结构：图的自测卷解析

《华中师大c语言数据结构》第7章 图的自测卷解答，包括单选题，涉及图的性质、遍历算法等概念。 1. **有向完全图的边数**：在有向图中，如果任意两个不同的结点之间都有一条有向边，这样的图称为有向完全图。对于8个结点的有向完全图，每个结点都可以指向其他7个结点，所以每个结点有7条出边，但因为边是双向的，所以总边数是每个结点的出边数乘以结点数，即7 * 8 = 56条边。正确答案是C（56条边）。 2. **路径的定义**：在图中，路径是由顶点和相邻顶点序偶构成的边所形成的序列。正确答案是A。 3. **连通分量**：在无向图中，如果有n个结点，最少有一个连通分量，即所有结点都是连通的。正确答案是B（1个连通分量）。 4. **深度优先遍历与二叉树遍历**：深度优先遍历类似于二叉树的先序遍历，先访问根节点，然后递归地访问左子树和右子树。正确答案是A（先序遍历）。 5. **有向图的度数关系**：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这是因为每条有向边恰好贡献了一个入度和一个出度。正确答案是B（1倍）。 6. **深度优先遍历的实现**：通常使用栈来实现深度优先遍历，因为它支持后进先出（LIFO）操作，适合用于递归回溯。正确答案是A（栈）。 7. **深度优先遍历的结点序列**：根据题目中的算法，从特定顶点出发的深度优先遍历顺序可能会有所不同，这里给出了一个具体例子，例如从顶点0出发的结点序列。正确答案是C（0423165）。 8. **无向连通图的最少边数**：一个无向连通图，为了保持所有结点的连通，最少需要的边数是结点数减去1，即7条边。正确答案是C（7条边）。 9. **广度优先遍历的实现**：通常使用队列来实现广度优先遍历，因为它支持先进先出（FIFO）操作，确保同一层的结点按照访问顺序被处理。正确答案是B（队列）。 10. **最小生成树**：在一个无向图中，最小生成树是指连接所有结点且边权之和最小的树，对于任何无向连通图，最小生成树是唯一的。正确答案是A（只有一棵）。 11. **广度优先遍历的结点序列**：广度优先遍历会先访问距离起点近的结点，再逐渐扩展到更远的结点。正确答案是B（0136425）。 12. **广度优先遍历的结点序列**：再次出现的题目，结点序列可能因算法实现而略有差异。正确答案是C（0123465）。 13. **广度优先遍历的结点序列**：根据算法，给出的序列可能是正确的广度优先遍历顺序。正确答案是C（0123456）。 14. **广度优先遍历的结点序列**：题目中给出了邻接表结构，广度优先遍历的结点序列与算法实现有关。正确答案是A（0243156）。 15. **广度优先遍历与二叉树遍历的类比**：广度优先遍历类似于二叉树的层次遍历，先访问根节点，然后依次访问每一层的结点。正确答案是D（层次遍历）。 16. **有向无环图（DAG）描述表达式**：为了表示给定的表达式，至少需要5个顶点来构建没有环的有向图。正确答案是A（5个顶点）。 这些知识点涵盖了图的基本概念，如图的类型、连通性、遍历算法（深度优先和广度优先）、度数和最小生成树等，这些都是数据结构中关于图的重要内容。