2012计算机考研真题：统考+答案+评分标准解析

"2012年计算机统考+标准答案+评分参考" 这篇资料是针对2012年全国硕士研究生入学统一考试计算机科学与技术学科联考的计算机学科专业基础综合真题，包含了考试的注意事项、题型以及部分试题内容。其中，试题包括单项选择题，涉及了算法分析、中缀表达式到后缀表达式转换、二叉树遍历和平衡二叉树等核心计算机科学概念。 1. 题目中提到的时间复杂度问题，考察的是递归算法的时间复杂度计算。给定的求整数阶乘的算法`int fact(int n)`是一个递归函数，其时间复杂度是线性的，即O(n)，因为每次递归调用都会进行一次乘法操作，总共需要n次这样的操作。 2. 第二题涉及中缀表达式到后缀表达式的转换，这是一个典型的操作符栈的应用。在转换过程中，需要将操作符压栈，直到遇到优先级较低的操作符或括号。最大栈深度发生在处理括号嵌套时，本题中最大个数为7，对应于`(c + d) * (e - f)`这个子表达式。 3. 第三题关于二叉树的前序和后序遍历，前序遍历中根节点通常是第一个访问的，而后序遍历中根节点是最后访问的。根据给定的遍历序列，可以推断出a是根节点，但孩子节点只能确定有e，因为b、c、d在后序遍历中出现的顺序不确定。 4. 平衡二叉树是一种特殊的二叉搜索树，每个节点的两个子树高度差不超过1。如果高度为6，且所有非叶节点的平衡因子均为1，表示每个非叶节点都有一个孩子节点是叶节点，另一个孩子节点高度为5。因此，该树的节点总数可以通过公式2^(h+1) - 1计算得出，即2^(6+1) - 1 = 127 - 1 = 126，但题目给出了错误选项，所以可能是题目本身有误。 5. 对于有n个顶点、m条边的有向图，使用邻接表存储，进行广度优先遍历的时间复杂度是O(n + m)，因为它需要遍历所有顶点和边。 6. 最后一题是关于有向图的邻接矩阵表示和拓扑排序。当邻接矩阵的主对角线以下元素均为零时，意味着图中没有有向环，因此可能存在多个拓扑排序序列，但无法确定唯一性。 以上是对2012年计算机统考中部分内容的解析，涵盖了算法复杂度、数据结构（二叉树和图）以及表达式转换等多个关键知识点。这些知识点在计算机科学的学习和实践中都非常重要，对于准备计算机相关考试或进行编程问题解决都有实际指导意义。