2012计算机考研408真题详解：算法、数据结构与应用

2012年的计算机考研408统考真题涵盖了计算机科学与技术学科的专业基础综合测试，主要考察了考生对计算机基础知识的理解和应用能力。以下是部分题目及其知识点的详细解析： 1. **时间复杂度**： 题目涉及一个递归计算阶乘的算法，其时间复杂度是通过分析递归调用的次数来确定的。此算法中，每次递归调用n都会产生一次n-1的递归调用，直到n=1结束。因此，总调用次数为n到1的累加，时间复杂度为O(n)，因为每个n都会被处理一次。 2. **后缀表达式**： 考察中缀表达式到后缀表达式的转换，利用栈来保持操作符的优先级。在转换过程中，遇到左括号"("时入栈，遇到右括号")"时出栈，遇到运算符时，如果当前栈顶是左括号或优先级低于栈顶运算符，就将栈顶的运算符弹出并加入后缀表达式。题目中给出了中缀表达式的例子，推断栈中同时保存操作符的最大个数取决于括号的数量，以及运算符的优先级规则。根据题目描述，栈中最多可以保存7个操作符（5个运算符加上初始空栈）。 3. **二叉树遍历**： 前序遍历（根-左-右）和后序遍历（左-右-根）相结合，可以确定根节点的孩子结点。由于后序遍历中b,c,d,e出现顺序与前序遍历相反，说明根节点不是b,c,d或e，而是它们的父节点。前序遍历先输出a，所以根结点可能是e，其孩子结点为b和d（排除B、C和D）。 4. **平衡二叉树**： 平衡二叉树的高度为6，且所有非叶结点的平衡因子为1，这意味着每个非叶结点有两个子树高度差不超过1。在这种情况下，一个高度为6的平衡二叉树最多有31个结点（2^6 - 1）。由于叶子结点数量是高度减1，即5，所以总结点数是叶子结点加上所有非叶结点，即31+5=36，但题目中给的是33，这表明可能存在错误或题目的描述不完整，这里选C，因为32是正确的答案。 5. **广度优先遍历时间复杂度**： 对于有向图的邻接表存储，广度优先遍历的时间复杂度是O(e)，因为算法需要访问每条边，而边的数量等于图的边数e。 6. **有向图的拓扑排序**： 邻接矩阵中主对角线以下的元素均为零，意味着从某顶点出发没有边指向其他顶点，这有助于确定图的拓扑序列。题目没有明确说明图是否强连通，因此无法确定是否存在拓扑序列，选项D表示不确定。 7. **迪杰斯特拉算法**： Dijkstra算法用于寻找带权图中最短路径，第一和第二条最短路径是从源点a到目标顶点的。题目中给出的第一条是b，第二条是c，这意味着a到这两个点的路径是最短的。由于后续的最短路径会逐渐扩展，其余目标顶点的顺序应按路径长度递增排列，但具体是d,e还是f取决于实际图的权重。 8. **最小生成树**： 最小生成树问题中，选项I正确，最小生成树的代价（边的权值总和）是唯一的；选项II错误，权值最小的边可能不会出现在所有最小生成树中，因为最小生成树的选择依赖于算法策略；选项III错误，用Prim算法从不同顶点开始得到的最小生成树可能不同，因为算法的起点不同，可能会找到不同的树。 以上知识点展示了部分计算机考研408真题中涉及的基础理论，对于备考者来说，理解和掌握这些概念是提高分数的关键。复习时不仅要理解题目本身，还要理解这些概念背后的原理和应用场景。