计算机考研408真题2009-2014：算法与数据结构解析

"这是一份2009年至2014年的计算机考研专业课408真题的完美打印版，主要包含了计算机科学与技术学科联考的专业基础综合试题。" 这部分内容涉及了计算机科学的基础知识，包括算法时间复杂度、中缀表达式到后缀表达式的转换、循环队列的管理、二叉树的操作、森林到二叉树的转换以及前缀编码和有向图的拓扑排序等核心概念。 1. **算法时间复杂度**：题目中的第一个选择题讨论了一个程序段的时间复杂度，这是算法分析的关键部分。这段代码包含两个嵌套循环，外层循环以2的指数增长，内层循环是对n的线性遍历。因此，总的时间复杂度是O(n log n)，选项C是正确的答案。 2. **中缀表达式到后缀表达式转换**：在第二个问题中，中缀表达式转换为后缀表达式（也称为逆波兰表示法）涉及到栈的操作。当扫描到'f'时，需要根据运算符的优先级和结合性来确定栈的状态。这里没有提供完整的表达式，但可以理解这个过程需要理解栈的性质和操作。 3. **循环队列管理**：循环队列是一种高效的队列实现，其队头和队尾可以循环地指向数组的不同位置。队空和队满的判断通常通过队头和队尾的相对位置来确定。在这个问题中，队空的条件是end1 == end2，而队满的条件是end1 == (end2 + 1) mod M，对应选项A。 4. **二叉树线索化**：在第四题中，中序线索化二叉树是为了便于二叉树的中序遍历。节点x的左线索指向其左子节点，右线索指向其右子节点。由于没有提供完整的树结构，我们不能确定x的具体线索。 5. **森林到二叉树转换**：森林到二叉树的转换规则是，森林中的每个树都转换为二叉树，森林中的根节点变为二叉树的根，其子树变为二叉树的左子树和右子树。转换后，叶结点的个数关系是，森林中叶结点的个数等于二叉树中度为1的结点个数加上1，对应选项B。 6. **前缀编码**：前缀编码是一种编码方式，其中任何编码都不会是另一个编码的前缀。例如，选项A、B和C都是前缀编码，而选项D中的"1100"是"100"的前缀，所以D不是前缀编码。 7. **有向图拓扑排序**：拓扑排序是对有向无环图（DAG）的顶点的一种线性排序，使得对于每一条有向边(u, v)，u都在v之前。拓扑排序的结果不唯一，但选项A和C的顺序违反了拓扑排序的规则，因为1不能在3之前，所以可能的拓扑排序是B或D。 这些知识点涵盖了计算机科学的基础部分，包括数据结构、算法、编译原理和计算机系统等多个领域，是计算机专业学生需要掌握的核心内容。