2012计算机统考：答案与评分参考解析

"2012年计算机统考的相关资料，包括标准答案和评分参考，主要涉及计算机科学与技术学科的基础知识，适用于全国硕士研究生入学统一考试。" 本资料涵盖的计算机科学与技术知识点广泛，主要包括算法分析、数据结构、操作系统、编译原理等多个方面。以下是对部分内容的详细解释： 1. **算法分析**： - 题目提到的求整数阶乘的算法`int fact(int n)`是一个递归函数，时间复杂度分析是算法设计与分析中的核心概念。对于这个特定的算法，每次递归调用都会将问题规模减半，因此时间复杂度是O(logn)，选项C正确。 2. **中缀表达式转后缀表达式**： - 这涉及到编译原理中的表达式转换知识，后缀表达式（也称为逆波兰表示法）不需括号就能明确运算顺序。中缀表达式到后缀表达式的转换通常使用栈辅助完成，转换过程中栈中最多保存的操作符数量为7，即在处理`(c+d)*`时，栈内同时有`+`、`*`、`(`这三个操作符，加上之后的`-`、`/`、`g`，总共7个，选项B正确。 3. **二叉树遍历**： - 二叉树的前序遍历和后序遍历可以用来确定树的结构。根据给定的遍历序列，无法唯一确定根节点的孩子结点，因为后序遍历序列没有提供足够的信息，选项D正确。 4. **平衡二叉树**： - 平衡因子为1的二叉树意味着每个节点都是左右子树高度差为1的平衡状态。对于高度为6的平衡二叉树，结点总数可以计算为2^(h+1)-1，所以结点总数为2^7-1=127，但选项中没有此选项，需要进一步分析题目是否正确。 5. **图的遍历**： - 广度优先遍历(BFS)的时间复杂度与图的边数成正比，因为每条边至少被访问一次。对于有n个顶点、m条边的有向图，使用邻接表存储，BFS的时间复杂度是O(m)，选项B正确。 6. **有向图的邻接矩阵**： - 邻接矩阵表示图中节点间的连接关系，主对角线以下的元素均为零，说明图中没有自环。至于拓扑排序，由于图可能是有向无环图(DAG)也可能包含环，因此无法直接得出是否存在唯一的拓扑序列，选项C正确。 这些题目涉及了计算机科学与技术中的基本理论和概念，包括算法复杂度分析、数据结构（二叉树）、编译原理（中缀表达式转换）、图论（图的遍历、拓扑排序）以及运算符优先级处理等。这些知识对于理解和解决计算机科学中的实际问题至关重要。