清华大学912考研真题：计算机专业综合知识点回顾

"这份文档是清华大学计算机系912考研真题回忆版，包含了计算机网络、数据结构、计算机组成原理、操作系统等多个领域的考题。这些题目涵盖了广泛的理论知识和实践应用，是准备清华大学计算机专业考研的重要参考资料。" 一、数据结构部分 1. 判断题： - 时间复杂度分析：f(n) = O(g(n)) 并不意味着 f(n) = O(g(n-1))。这是因为在大O表示法中，f(n) 只是表明存在常数c和n0使得当n>n0时，f(n)≤cg(n)，而不是对所有n都成立。所以，f(n)可能是O(g(n))，但不一定是O(g(n-1))。 - 散列表的均匀性：如果散列表的长度使用了不超过其长度的素数，虽然可以减少冲突，但并不能保证关键元素的分布均匀。均匀分布通常需要良好的散列函数实现。 - KMP算法与蛮力算法：KMP算法在处理模式匹配时，相比蛮力算法，能够有效避免回溯，因此它的平均时间复杂度优于蛮力算法，但在字符集概率相等的情况下，两者的时间复杂度接近。 - 哈夫曼树的权值分布：哈夫曼树是一种最优的二叉树，用于编码，其特点是最小带权路径长度，但并不意味着深度较小的节点权值一定小于深度较大的节点权值。 2. 选择题： - 五个互异节点构造的二叉树种类：这个问题涉及二叉树的计算，根据公式，五个互异节点可以构造2^(n-1) = 2^4 = 16种不同的二叉树。 - 直接插入排序比较次数：对于序列(64, 63, ..., 2, 1)，因为是逆序，所以比较次数最多，接近于n*(n-1)/2，即5*(5-1)/2=10次。选项中最接近的是D. 2200。 - 平衡二叉树高度：插入1, 2, 3, 2016后，树的高度不会超过log2(2016)+1，大约为11。 - B树查找次数：搜索B树的第2016个关键字，由于根节点在内存中，需要访问的磁盘块数与B树的高度相关，具体计算需要知道B树的阶数。 3. 算法题： - 最小环问题：使用Floyd-Warshall算法或 bellman-ford算法可找到图中的负权环，时间复杂度为O(n^3)，不符合要求。为了达到O(n*e)的时间复杂度和O(n)的空间复杂度，可以采用邻接矩阵或邻接表来存储图，并利用拓扑排序和深度优先搜索相结合的方法。 二、计算机组成原理部分 - 指令结构：指令通常由操作码和操作数（或地址码）组成。 - 海明码：海明码用于检测和纠正错误，P1P2D1P4D2D3P4中，P代表校验位，D代表数据位。需要具体的数据才能确定错误位数和正确数据。 - DMA传输方式：DMA（直接存储器访问）可以采用周期窃取或DMA控制器的方式与CPU共享总线。 - IEEE浮点数：最小正数是2^(-126)，因为规格化单精度浮点数的最小正非零数值是2^(1-127)。 以上只是部分内容解析，完整的解答需要对每个题目做深入的分析，而这里只提供了简要的思路。对于二叉树的数据结构问题，需要理解后序遍历的性质以及如何实现first()和next()函数。对于后序遍历的时间复杂度分析，通常涉及递归或栈的使用。