图论与数据结构考研试题解析：选择题重点

"数据结构与算法考研试题：第七章 图" 这部分内容主要涉及图论的基础知识，涵盖了图的定义、性质、以及相关的算法应用。以下是关键知识点的详细说明： 1. **路径定义**：路径是由顶点和相邻顶点序偶构成的边所形成的序列。在选项A中给出了正确的定义。 2. **无向图边的数量**：无向图的顶点个数为n时，最多有n*(n-1)/2条边，这是因为在无向图中每条边连接两个不同的顶点，形成一个对，因此边的数量是顶点对的一半。所以选项B是正确的。 3. **连通无向图的边数下限**：一个n个顶点的连通无向图，其边的个数至少为n-1，因为最小的连通图是一个树形结构，需要n-1条边连接所有顶点。选项A正确。 4. **有向图连通的条件**：要连通具有n个顶点的有向图，至少需要n-1条边，与无向图的情况类似。选项A正确。 5. **完全有向图的边数**：n个结点的完全有向图含有n*(n-1)条边，因为每个结点可以指向其他n-1个结点。选项D正确。 6. **有向图的最少边数**：一个有n个结点的图，最少有0条边，即所有顶点都不相连。选项A正确。 7. **度数和与边数关系**：在无向图中，所有顶点的度数之和等于所有边数的2倍，因为每条边贡献了两个度数。选项B正确。 8. **表达式的有向无环图表示**：为了表示表达式(A+B)*(A+(B/A))，至少需要6个顶点来代表操作符和操作数，选项B正确。 9. **深度优先遍历(DFS)**：DFS遍历无环有向图并退栈返回时，会得到逆拓扑有序的顶点序列，即依赖关系前的顶点先出现。选项A正确。 10. **稀疏图的表示**：对于稀疏图，通常使用邻接表来节省空间，因为邻接表只存储实际存在的边。选项B正确。 11. **邻接矩阵对称性**：无向图的邻接矩阵是对称的，因为每条边在矩阵中表现为一对相等的非零元素。选项B正确。 12. **检查路径存在**：在邻接矩阵A中，检查第i行第j列的元素是否为零，可以判断顶点Vi和Vj之间是否存在长度为m的路径。如果需要检查长度为m的路径，需要检查Am-1。选项D正确。 13. **图的遍历**：图的遍历包括深度优先遍历(DFS)和广度优先遍历(BFS)，DFS适用于有向图和无向图，选项C不正确。 14. **表示稀疏有向图**：邻接多重表适用于表示稀疏有向图，因为它只存储实际存在的边。选项C正确。 15. **图的遍历性质**：图的深度遍历同样适用于有向图，选项C不正确。 16. **深度优先遍历序列**：无向图G的深度优先遍历可能得到的顶点序列是不确定的，因为遍历顺序依赖于起始顶点和递归过程。给定的选项可能是正确的序列之一。 以上是针对题目内容的详细解释，涵盖了图的基本概念、性质、遍历算法以及图的存储结构。这些知识点是数据结构与算法学习中的重要组成部分，也是考研中的常见考点。