2012年计算机统考真题解析与答案

"2012年全国硕士研究生入学统一考试计算机统考真题包含了计算机科学与技术学科的专业基础综合，主要涉及计算机领域的基础知识点，如算法分析、数据结构、操作系统和编译原理等。试题形式包括选择题，要求考生在答题卡上规范作答，并在考试结束后将答题卡、答题纸和试题一起交回。" 知识点详解: 1. **算法时间复杂度**：题目中提到的求整数阶乘的算法`int fact(int n)`是一个递归函数，时间复杂度为O(n)，因为每次递归都会调用自身一次，总共需要递归n次。选项B正确。 2. **中缀表达式转后缀表达式**：在转换过程中，需要使用栈来存储操作符，最大数量取决于中缀表达式的结构。转换过程中，最多会同时保存7个操作符在栈中：`+`、`-`、`( `、`) `、`*`、`/` 和 `^`。所以答案是B，最大个数为7。 3. **二叉树遍历**：前序遍历序列是`a e b d c`，后序遍历序列是`b c d e a`，可以推断出根节点`a`的孩子节点为`e`。因此答案是A，只有`e`。 4. **平衡二叉树**：平衡因子为1表示左子树和右子树高度差为1。若高度为6的平衡二叉树所有非叶节点平衡因子为1，则结点总数为2^(h+1) - 1 = 2^(6+1) - 1 = 127。但题目可能是考虑了错误的平衡因子，若平衡因子为1，结点总数应该是2^(h-1) = 2^(6-1) = 32。因此答案是C。 5. **图的遍历**：对于有向图的广度优先遍历，使用邻接表存储时，时间复杂度是O(V+E)，其中V是顶点数，E是边数。题目中提到有V个顶点和E条边，答案是B，时间复杂度为O(V+E)。 6. **有向图的拓扑排序**：如果邻接矩阵的主对角线以下都是零，这意味着没有从低编号的顶点到高编号的顶点的边，这样的图的拓扑排序可能存在多个，因为可能存在多条从高编号到低编号的边。答案是C，存在，可能不唯一。 这些题目覆盖了计算机科学中的基本概念，如算法效率分析、数据结构（二叉树）、图的遍历以及表达式转换等核心知识点。准备这类考试需要对这些基础知识有深入理解和掌握。