清华大学计算机系912考研真题2019年
需积分: 0 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年的涵盖范围广泛,对考生的理论理解、问题解决能力和算法应用能力都有较高要求。考生需要扎实掌握计算机科学的基础知识,才能在这样的考试中取得好成绩。

wangkan0202
- 粉丝: 0
最新资源
- 大学计算机考试题库里的全套习题解析.doc
- 电子商务安全的管理保障2.ppt
- 营销力网站如何打造.doc
- 互联网+技术在电力企业人力资源创新中的策略.docx
- 学习《cad2004jichu教程》教学讲义.ppt
- 第2章中文windows操作系统知识讲解.ppt
- 电力通信接入网整体解决方案.doc
- 我国企业物流信息化建设案例分析正文.doc
- 2022年大数据平台分析报告-.doc
- 市场营销案例--莱软教育软件营销策划方案(DOC-15页).doc
- 浅谈企业信息化建设与管理.docx
- PLC原理与实验--第四章梯形图与顺序功能图设计简介方案教学讲义.ppt
- 浅谈高校软件专业的工程实践与差异化教学.docx
- 高级人工智能十二章培训资料.ppt
- 浅谈互联网+时代下医院思想政治宣传工作的三个结合.docx
- [信息与通信]编制办法和费用定额那业君演示教学.ppt