2012计算机考研真题及答案解析

"2012计算机考研真题与答案" 这篇文档是2012年全国硕士研究生入学统一考试的计算机专业基础综合试题，科目代码为408。试卷包含了多项选择题，涉及了计算机科学与技术的基础知识，主要包括算法分析、数据结构、操作系统和计算机网络等多个领域。 1. 题目涉及了递归算法的时间复杂度分析。给定的求阶乘的算法是递归实现的，其时间复杂度为O(n)，因为每个函数调用都会导致n-1次新的调用，形成一个深度为n的递归树。 2. 该题考察的是中缀表达式转后缀表达式（逆波兰表示法）的过程，以及在转换过程中栈的使用。最大同时保存在栈中的操作符个数是在处理"((cd)/e-f)"这部分时，需要同时保存'('、'*'、'/'、'-'和'f'，共5个操作符。 3. 二叉树的前序遍历和后序遍历可以用来确定树的结构。题目中的遍历序列表明，e是根节点，b和c是e的子节点，但d的位置无法确定，因此无法确定e的具体孩子节点，只能确定有e。 4. 平衡二叉树的高度为6且所有非叶节点的平衡因子为1，意味着每层都有一个额外的节点，除了最底层。所以节点总数为2^1+2^2+2^3+2^4+2^5+2^6=2+4+8+16+32+64=126。 5. 对于有向图的广度优先遍历，如果使用邻接表存储，时间复杂度是O(n+e)，其中n是节点数，e是边数。 6. 邻接矩阵中主对角线以下的元素为零的有向图，可能存在多个拓扑序列，但是否唯一无法仅凭此信息确定。 7. 迪杰斯特拉算法用于求解单源最短路径问题，它会按顺序找到最短路径。在给定的有向图中，首先到达的目标顶点是b，然后是c，接下来是f，因为a->b是最短的，接着是a->c，最后是通过b到达d和f。 8. 最小生成树的正确性：I.最小生成树的代价是唯一的，因为一旦构造出一棵最小生成树，就不可能有更低代价的生成树。II.权值最小的边不一定包含在最小生成树中，这是错误的，比如Prim或Kruskal算法可能会跳过某些最小边以保持树的连通性。 这些题目覆盖了计算机科学的一些核心概念，对于准备考研的学生来说，理解和解答这些问题对于深入理解计算机科学的基础原理至关重要。