2012计算机考研模拟试题精选：栈与二叉树相关题目

本资源是一份针对2012年计算机考研的模拟试题，包含多项选择题，主要考察了栈和队列的基本操作、数据结构理论、树与图的性质、搜索算法以及图的拓扑排序等核心知识点。以下是具体内容解析： 1. **栈与运算符优先级表达式**： - 问题1涉及栈的操作，出栈序列合法性，不同选项展示了栈的不同出栈方式。正确理解栈的后进先出(LIFO)特性是关键，A选项的序列中最后出栈的元素不是最先入栈的，因此是非法的。 2. **栈与运算符优先级计算**： - 题目2通过栈模拟运算表达式求值，考察栈在处理括号和运算符优先级时的能力。C选项没有嵌套括号，因此不会发生溢出。 3. **树的度和节点数**： - 题目3考查了树的度数定义（度为连接分支的数目），计算度为0（叶子结点）的结点数量，需要知道树的度数分布规律。 4. **二叉树的遍历与序列**： - 题目4涉及中序、层序和后序遍历，用于重建或识别二叉树结构，后序遍历的顺序是先左子树、后右子树、最后根节点，根据给定序列推断后序序列。 5. **二叉排序树的性质**： - 题目5考察二叉排序树的性质，包括前序遍历的升序性（I正确）、最小/最大值子树关系（II正确），新插入的节点位置（III错误，新插入的节点可能位于非底层）、及插入后的影响（IV错误，插入后可能改变结构）。 6. **平衡二叉树的维护**： - 题目6涉及平衡二叉树的调整，插入后可能导致不平衡，需要了解如何通过旋转恢复平衡。 7. **图的性质和结点数**： - 题目7涉及图论中的无向图，36条边且非连通意味着至少存在两个连通分量，最低结点数是连通分量数加1。 8. **有向图的拓扑排序**： - 题目8考查拓扑排序，给定向量图的顶点，判断哪些序列是正确的拓扑排序。拓扑排序遵循有向无环图(DAG)中节点的依赖关系。 9. **折半查找算法**： - 最后一个问题涉及到折半查找的步骤，查找元素75时，需要找到表中合适的分割点进行比较，由于75在70和82之间，所以会先与70比较。 这些题目涵盖了计算机考研中常见的数据结构、算法、图论等基础知识点，对于准备考研的学生来说，是复习的重要参考资料。