2019清华大学计算机专业基础综合回忆：数据结构与操作系统关键点

2019年清华大学912计算机专业基础综合考试涵盖数据结构、算法和操作系统等多个核心知识点。以下是考试内容的详细解析： **数据结构部分（70分）** 1. **判断题** - (1) 提供了一个关于大O符号的表述，指出\( n\log\log\log n = \Omega(\lfloor\log n\rfloor !)\) 是错误的，因为阶乘的增长速度远超过对数函数的复合增长。 - (2) 交换哈夫曼树的深度节点会影响编码长度，但不一定会改变，只有当调整的是叶子节点时，编码长度才会变化。 - (3) KMP算法虽然没有使用改进的next表，但通过预处理模式串，仍能保持线性时间复杂度，即使查找失败也能快速回溯。 - (4) Splay树的平均性能为对数时间复杂度，即使不满足局部性原理，其分摊复杂度也不一定是\( \log n \)，而是取决于特定条件下的平均情况。 - (5) 先序和后序遍历无法唯一确定一棵二叉树的层次遍历顺序，因为缺少中序遍历信息。 - (6) 叶节点为2019的真二叉树数量小于由2018对括号表示的所有合法二叉树序列，这是关于递归关系的一个应用问题。 - (7) 叶节点数量为2018的二叉树，其层次遍历队列的容量小于2018，这与二叉树的性质有关。 - (8) 插入排序在最坏情况下，即使没有减少循环节，也可能导致逆序对的数量不变，但不会增加。 - (9) 基数排序稳定性取决于底层算法，不稳定可能导致相同数值的元素排序顺序不一致。 - (10) 函数调用栈中相同的函数可能会多次出现，但不一定紧邻，这涉及函数调用的细节。 **简答题** - 逆波兰表达式（RPN）的优点包括：紧凑，易于实现高效率的计算器，且无需括号来控制运算顺序。 - DFS（深度优先搜索）中，到达目标节点时立即标记为已访问，标记后向边是在回溯过程中完成。 - 败者树（ Tournament Tree）优势在于简化了比较过程，使得排序更高效，特别是对于大量数据。 - 红黑树相较于AVL树在插入和删除操作的平衡调整更简单，插入性能更好，但可能牺牲查找性能。 - 闭散列相比开散列（开放寻址法）的优势在于：减少冲突概率，提高查找效率；插入和删除操作也更直接。 - 插入排序对于部分有序的数据，如近乎有序或少量元素，其性能优于选择排序，因为插入操作更容易合并有序子序列。 - 在稠密图中，多叉堆用于Dijkstra算法是因为它支持多个孩子的操作，适合处理大量边的情况；多叉堆的分叉数m通常基于图的度数分布动态确定。 - KMP算法在模式匹配中优于暴力搜索，当模式串中存在重复子串时，KMP通过预处理next数组可以避免无效的字符比较。 **算法题** - 需求是设计一个后序遍历的高效算法，找到第K个节点，时间复杂度不超过O(depth(x))。这可能涉及到一种递归或迭代的方法，如利用线索二叉树或者栈辅助，通过后序遍历的特点进行优化。 **操作系统部分（30分）** - 填空题涉及进程调度的Stride调度算法，其中stride是进程对资源的需求量，用八位无符号数表示。这部分内容可能考察进程调度策略和内存管理。 综上，2019年清华大学912计算机专业基础综合考试深入考查了考生的数据结构、算法设计和操作系统理论知识，要求考生具备扎实的理论基础和实际解决问题的能力。