2020清华计算机考研题回顾：数据结构与计算机组成原理知识点总结

本资源主要聚焦于2019年12月清华大学计算机专业的研究生入学考试题目，涉及数据结构、计算机组成原理以及操作系统等多个核心领域。首先，在数据结构部分，考察了诸如快速排序的时间复杂度（O(nlogn)）、跳转表和塔的期望高度、败者树与胜者树、完全二叉堆、Crane算法、AVL树的局部重构、红黑树等数据结构理论及其应用。还涉及到基于比较式的算法如封闭散列和开放散列，以及DFS（深度优先搜索）和基数排序算法。模式串、文本串以及KMP算法在字符串处理中的应用也有所涉及。 在计算机组成原理方面，讨论了流水线设计中的段数、处理器的CPI（每指令周期数）、缓存优化对程序执行速度的影响，以及不同RAID级别（如RAID1和RAID5）在磁盘空间占用上的差异。此外，还涵盖了处理器缓存的结构、内存带宽计算、指令格式和冲突解决策略，如流水线延迟、数据旁路和分支预测。 操作系统部分涉及死锁的概念、SJF（短作业优先）调度算法、FIFO策略（Belady现象）以及页式存储管理。讨论了符号链接（软链接）的原理，以及UNIX文件索引结构的存储位置。动态分区和段式存储管理方法被提及，包括存储分配和回收操作。系统调用是另一个重要知识点，包括系统调用的分类、Getpid请求的具体执行过程，以及用户态代码片段如何支持系统调用，如寄存器使用、参数传递和返回值的处理。 整体来看，这份试题全面地检验了考生对计算机科学基础理论和实践的理解，要求具备扎实的数据结构、计算机硬件和操作系统知识，以及一定的问题分析和算法设计能力。对于备考的学生来说，这是一份深入且具有挑战性的复习资料。