2020天勤计算机考研模拟卷数据结构部分解析

"这是一份2020年天勤计算机考研的数据结构模拟卷，包含选择题，涉及栈、平衡二叉树、出栈顺序、时间复杂度、三叉树、生成树、平衡二叉树构造及快速排序等知识点。" 1. **栈**：题目中提到利用栈来计算表达式的值，栈是一种后进先出（LIFO）的数据结构，常用于解决表达式求值的问题。在处理表达式时，通常会用两个栈，一个用于存储运算符，一个用于存储操作数。题目通过不同表达式考察了栈溢出的情况，分析不同运算符的优先级和结合性，以确定是否会导致栈过满。 2. **出栈顺序**：题目讨论了栈的出栈顺序，对于有限大小的栈，不同的入栈和出栈顺序会产生不同的结果。例如，题目给出了四个选项，考察考生对于栈操作的理解和推理能力。 3. **平衡二叉树**：平衡二叉树是一种特殊的二叉树，其中任何节点的两个子树的高度差不超过1，以确保高效的查找性能。题目中提到的平衡因子是节点左右子树高度之差，插入节点后导致不平衡，需要通过旋转操作恢复平衡。LL、LR、RR、RL代表四种旋转类型，用于调整树的结构。 4. **字符串入栈出栈**：当一个字符串的字符按照一定顺序入栈后，不同出栈顺序可能会导致不同的字符串恢复，题目考察了这一概念。 5. **时间复杂度**：题目中的代码段是一个嵌套循环，外层循环是O(n)，内层循环是对数级别，但乘以5，因此总的时间复杂度是O(n * log5n)。 6. **三叉树**：三叉树是一种每个节点最多有三个子节点的树形结构。题目中提到度为3的节点数等于度为2的节点数，以及叶子节点的数目，要求计算度为2的节点数目。 7. **生成树与连通分量**：生成树是无向图的一个子集，包含了所有顶点且无环，它是图的最小连通子图。题目中询问了生成树与连通分量、无环子图的关系。 8. **平衡二叉树的构建**：题目给出了一组序列，要求根据次序插入元素生成平衡二叉树，然后求度为2的节点数。平衡二叉树的构造方法会影响树的形态，进而影响度为2的节点数量。 9. **快速排序**：快速排序是一种常用的排序算法，它的效率受待排序序列的影响。在最坏情况下，即输入序列已经完全排序或逆序，快速排序的效率最低。题目给出了几种关键字序列，要求判断哪种情况下的排序速度最慢。 这些知识点是计算机科学，特别是数据结构和算法领域的重要内容，对于准备计算机专业考研的学生来说，理解和掌握这些知识点至关重要。