2012年考研计算机统考标准答案详解

本资源提供的是2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合的标准答案。考试包含单项选择题，涉及计算机科学的基础理论和算法设计。 1. **算法时间复杂度**： 题目中给出了一个递归计算整数阶乘的算法，其时间复杂度是分析递归调用的次数。在这个算法中，每次调用都会减少一个参数n的值，直到n为1时结束，因此时间复杂度是O(n)，即选项C。 2. **中缀表达式转后缀表达式**： 转换过程涉及括号管理和运算符优先级，题目描述的操作符包括加减乘除以及括号。要找到最大同时保存在栈中的操作符个数，考虑最坏情况，即所有的操作符都被推迟到后缀表达式的最后，且每多一个左括号就要进栈一个，但遇到右括号时需要出栈直到遇到左括号。因此，当只剩下一个右括号时，栈中最多可以有5个操作符（包括最后的右括号），选项A。 3. **二叉树遍历**： 前序遍历为△e, b, d, c，后序遍历为b, c, d, e, a。根据后序遍历的特点，最后一个访问的节点是根节点，所以根节点的孩子结点为e，选项A。 4. **平衡二叉树的结点总数**： 平衡二叉树的性质是所有非叶结点的平衡因子为1，这意味着每个非叶结点有两个孩子。对于高度为6的平衡二叉树，根节点没有平衡因子，其余5层每层都有两种情况：有1个平衡因子为1的非叶节点，或者没有。这样算来，第一层有1个，第二层有2个，第三层有4个，第四层有8个，第五层有16个，第六层有32个。但是因为平衡因子为1，所以每层都是上一层的一半，因此实际结点总数为1+2+4+8+16+32=63，选项中没有提供此选项，可能答案有误。 5. **有向图广度优先遍历时间复杂度**： 对于有刀个顶点和召条边的图，使用邻接表存储，广度优先搜索的时间复杂度主要取决于顶点数，因为每个顶点会被访问一次。即使考虑到边的数量，也只需要访问一次每个顶点，因此时间复杂度是O(v)，即选项A。 6. **有向图邻接矩阵特征与拓扑序列**： 邻接矩阵主对角线以下的元素均为零意味着除了自环外，没有直接的前驱关系。这表明图可能存在环，但不影响拓扑排序的存在性。由于邻接矩阵的特性，可能有多条路径连接不同的顶点，因此拓扑序列可能存在多个，选项C正确。 本资源提供了计算机科学基础理论的考试题目及其标准答案，涵盖了算法复杂度分析、表达式转换、二叉树遍历、平衡树节点数计算以及图论相关知识。