2012年计算机统考真题解析：算法与数据结构

"2012年计算机统考真题及答案解析" 这篇资料是2012年全国硕士研究生入学统一考试的计算机科学与技术学科联考的真题及答案解析，主要涉及计算机学科专业基础综合。试题涵盖多项选择题，测试考生对于计算机科学的基础知识掌握程度。 1. 题目涉及算法的时间复杂度分析。给定的递归算法计算整数n的阶乘，其时间复杂度是O(n)，因为每次递归都会调用自身并将问题规模减少1，直到n=1为止，总共进行了n次递归调用。 2. 该题考察中缀表达式转后缀表达式的运算，需要用到栈来处理运算符的优先级。在这个例子中，最大同时保存在栈中的操作符数量是7，因为在转换过程中，最大的堆栈深度是在处理"(*"、"("、"/"、"-"、"("、")"、"-"这些运算符时。 3. 二叉树的前序和后序遍历可以用来确定树的结构。根据给定的遍历顺序，可以推断出根节点的孩子节点只有e，因为前序遍历中根节点之后的第一个元素是e，而后序遍历中b、c、d都在e之前，表示它们都是e的子节点，而c在d之前，表明c是d的父节点。 4. 平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，这意味着每个非叶结点都有两个子结点，且子树高度差为1。因此，这样的平衡二叉树的结点总数为2^0 + 2^1 + 2^2 + ... + 2^5 = 33。 5. 对于有向图的广度优先遍历，如果使用邻接矩阵存储，算法时间复杂度是O(n+e)，其中n是结点数，e是边的数量，因为需要访问每个结点和边一次。 6. 若邻接矩阵存储的有向图中主对角线以下的元素均为零，这说明图中没有自环，但无法确定是否存在唯一的拓扑序列，因为拓扑序列的存在性和唯一性取决于有向无环图（DAG），而这里的信息不足以判断图是否为DAG。 7. 迪杰斯特拉算法用于寻找有向图中最短路径。在这个问题中，首先找到的目标顶点是距离源点a最近的，依次是b、c，后续目标顶点的顺序可能是d、e、f，因为这些是按照距离a的远近顺序找到的。 8. 最小生成树的叙述中，正确的只有Ⅰ，即最小生成树的代价是唯一的，但并不意味着生成树中的边是唯一的。普里姆算法和克鲁斯卡尔算法可能会得到不同的边集，但它们的总代价是一样的。因此，选项B是正确的。 这些题目涵盖了算法复杂度、二叉树遍历、数据结构（栈的应用）、图的遍历、最小生成树等多个计算机科学基础概念，是考研复习的重要参考资料。