2021清华计算机考研912数据结构与组成原理真题解析

"2021清华计算机考研912真题" 这篇考研真题涵盖了计算机科学中的多个关键领域，包括数据结构、算法、计算机组成原理以及计算机系统架构。以下是根据题目内容提炼出的知识点： 1. **算法复杂度分析**： - 渐进意义下的比较：`f(n)` 和 `g(n)` 的增速比较，考察的是大O记号（Big O notation）用于描述算法运行时间的增长速率。 - 复杂度问题：询问 `f(n) = 2^n log_2 n` 和 `f(n) = 3f(n/9) + O(1)` 的复杂度，涉及递归函数的时间复杂度分析。 2. **数据结构**： - 中缀表达式与后缀表达式（RPN）的转换：考察了表达式求值中的栈操作。 - next表与改进的next表：这是关于正则表达式和编译原理中的概念，用于分析字符串匹配。 - AVL树的平衡调整：讨论AVL树在删除节点时如何保持平衡，涉及节点g、p、v的定义以及旋转策略。 3. **图论**： - 拓扑排序：探讨有向无环图（DAG）是否可以通过深度优先搜索（DFS）的逆序得到拓扑排序，需要理解拓扑排序的基本性质和DFS的执行过程。 4. **二叉查找树（BST）**： - 给出一个算法来计算BST中指定范围内的节点数量，要求时间复杂度为O(h)，空间复杂度为O(1)。这涉及到BST的性质和迭代或递归遍历技巧。 5. **计算机组成原理**： - 字符编码：可能涉及ASCII或Unicode编码，讨论字符表示的内在结构。 - Cache组织方式：全相连（fully associative）和组相连（set associative）的命中率比较。 - DMA与总线控制：理解DMA（Direct Memory Access）在内存访问中的角色，以及它如何与CPU共享总线。 6. **浮点数表示**： - IEEE单精度浮点数的表示范围，涉及浮点数的规格化形式和指数范围。 7. **计算机性能指标**： - CPI（Cycles Per Instruction）与主频的关系，用于评估处理器性能。 - TLB（Translation Lookaside Buffer）的作用和特性，包括其在虚拟地址到物理地址映射中的作用。 8. **并发与同步**： - 冲突解决机制：旁路、阻塞、动态预测和编译器调度等方法。 9. **计算机系统结构**： - 字节顺序：大端和小端表示法下short类型变量的值。 - Cache参数计算：涉及地址映射中的索引和标记位数。 - 冯诺依曼体系结构的特点：强调程序和数据存储在同一内存中。 10. **汇编语言指令**： - LWR、ADDR、SUBR等指令的含义和执行流程，这涉及到计算机指令集的理解。 这些题目涵盖了计算机科学的多个基础和核心概念，反映出考研对考生全面理解和应用知识的能力要求。