清华大学计算机系912考研真题2019年

preview
需积分: 0 31 下载量 167 浏览量 更新于2020-12-06 2 收藏 104KB DOC 举报
【清华大学计算机系912考研真题2019年】涵盖了计算机科学多个核心领域的知识点,包括数据结构、计算机网络、计算机组成原理和操作系统。以下是这些领域的详细解析: **数据结构部分** 1. 时间复杂度分析:题目涉及了时间复杂度的比较,如nlogloglogn与Ο(⌊logn⌋!)的关系,以及KMP算法的时间复杂度分析。 2. 哈夫曼树编码:交换不同深度的节点会影响编码长度。 3. 伸展树(Splay Tree):讨论了其局部性和分摊复杂度,强调局部性对于维持O(logn)时间复杂度的重要性。 4. 插入排序和逆序对:交换逆序对会减少总逆序对数,这是冒泡排序和插入排序优化的一个基础概念。 5. 堆的性质:在插入操作中,如果键值独立均匀分布,平均操作复杂度为O(1)。 **简答题** 1. 逆波兰表达式:讨论了其计算效率高于普通表达式的原因,以及转换的意义。 2. DFS搜索图:涉及前向边和后向边的标记时机。 3. 插入排序与选择排序的对比:插入排序的优点,如稳定性及部分有序数据的效率。 4. Dijkstra算法与多叉堆:在稠密图中多叉堆的使用及其分叉数的确定。 5. 散列方法:开放散列与封闭散列的优缺点,如查找效率和冲突解决策略。 6. 锦标赛树与败者树:败者树在查找最小元素时的效率优势。 7. 红黑树与AVL树:红黑树在保持平衡的同时提供了更快的插入和删除速度。 8. KMP算法与蛮力算法:KMP在模式匹配中的优势,尤其是在存在公共前缀的情况下。 **算法题** 1. 后序遍历找第K大节点:要求使用不超过O(depth(x))的时间和空间复杂度,考察了二叉树的高效遍历技巧。 **计算机组成原理部分** 1. 流水线技术:MIPS五级流水线的数据冲突及其解决方法。 2. 计算机存储器:RAID级别的容错能力,静态与动态存储器的工作原理,虚拟内存与实际内存的比较。 3. 总线技术:并行与串行总线的速度比较,同步与异步总线,以及单总线与双总线。 4. 缓存缺失类型:了解缓存工作原理中的不同缺失类型。 5. MIPS处理器延迟计算:涉及到各种操作的延迟时间,以及流水线设计下的延迟优化。 综合以上内容,清华大学计算机系912考研真题2019年的涵盖范围广泛,对考生的理论理解、问题解决能力和算法应用能力都有较高要求。考生需要扎实掌握计算机科学的基础知识,才能在这样的考试中取得好成绩。
身份认证 购VIP最低享 7 折!
30元优惠券