2017年清华计算机真题回忆：数据结构与算法详解

本资源是一份2017年清华大学计算机考研912科目的真题回忆版文档，涵盖了数据结构、计算机组成原理等多个知识点。以下是详细的内容分析： 1. 数据结构部分： - **判断题** a. 提供了一个关于时间复杂度的判断：虽然函数f(n)的时间复杂度为O(g(n))，但并不意味着f(n)等于O(g(n-1))，这表明理解时间复杂度的等价关系是考试中的重要考察点。 b. 散列表的性能与其哈希函数及负载因子有关，使用不超过素数长度的哈希表并不能保证存储的关键字分布均匀，需要考虑负载因子的控制。 - **选择题** a. 询问了五个互异节点构造二叉树的不同形态，涉及二叉树的构建和计数问题，考察了考生对基本构造的理解。 b. 直接插入排序对于特定序列的比较次数与序列特点有关，计算次数需要考虑递减序列中相邻元素的差距，这里给出了一个具体数值的选择。 c. 描述了平衡二叉树中插入关键字后的高度变化，涉及平衡二叉树的性质和维护规则。 d. 询问了B树搜索第2016个关键字所需的I/O次数，涉及到B树的索引结构和查询效率。 e. 考察了逆波兰表达式的计算，要求考生识别运算符和顺序。 2. **算法题** - 要求设计一个广度优先遍历算法寻找图中的最小环，需考虑遍历策略并保证时间复杂度为O(n*e)和空间复杂度为O(n)。算法思想可能涉及队列辅助，先广度优先搜索整个图，然后回溯查找环，找到环后继续搜索更短的环。 - 需要编写伪代码，如使用栈或队列来保存节点，以及如何标记已访问节点以避免重复。 3. **计算机组成原理** - 指令的组成包括操作码和操作数字段。 - 海明码纠错题，给出了一个错误的海明码串，要求确定错误位置和修正后的正确值，涉及到编码理论的基本概念。 - DMA（直接存储器访问）的两种方式，通常包括独立请求和周期挪用，考生需了解这两种模式的区别和适用场景。 - IEEE规格化的单精度浮点数表示范围，这是浮点数数据类型的底层细节。 4. **二叉树结构实现** - 提供了二叉树和实际二叉树的定义，以及first()和next()函数的作用，考察对后序遍历的理解和函数实现。 - 后序遍历的时间复杂度是线性的，因为每个节点仅被访问一次，证明遍历时间复杂度为O(n)。 这份题目全面覆盖了计算机科学的基础和核心领域，对于准备参加清华大学计算机考研的学生来说，理解和解答这些问题有助于提高考试应试能力。