2021清华大学计算机考研912计算机基础综合真题回忆版_算法

原标题：2021清华大学计算机考研912计算机基础综合真题回忆版

数据结构

第一题复杂度11分，只记得第二问是f(n)=3f(n/9)+o(1)，问f(n)复杂度，并证明。第一问是比较两个复杂度，一个是n的2020次方

第二题中缀表达式转rpn，书上的例子，一模一样；还有一个next表改进的next构造

第三题快速排序和插入排序，快排整出长度小于等于m的子序列，用它们做最后一次插入排序，整个序列长n,问最后一次插入排序复杂度，并证明

第四题考avl和3+4重构，connect34的4种情况

第五题拓扑排序为啥可以用dfs回溯的逆序，并证明

算法题，在bst中找介于lo和hi之间的元素个数，要求o(h)时间，o(1)空间，写算法并说明

操作系统

8个

判断，考了有僵尸进程和孤儿进程，死锁和不安全状态，opt算法应用(离谱)，其他不太记得

文件大题，考的阅读理解和对文件操作的熟悉，与ucore无关

8分有3分送的

后面5分填inode位图和数据的内容，没时间看了，扔掉

最后六分是判断三个场景用的是信号，管道，消息队列还是信号量

考了有一条linux命令，我是临场蒙对了。就是cat一个txt文件，一个|，后面是grep exam，是考的管道

第一个是杀死进程，第三个是访问修改一个私有数据区

组成原理

不太记得了

流水线大题考的load相关暂停几个周期

还有一个冯诺依曼结构特点(纯送分)

选择有一个ieee754正负数的个数哪个多，当时忘了

计算机网络

考了crc,csma/cd(王道原题)，ip地址,一个tcp的，还有一个dns

路由器大题考了距离矢量算法，和链路状态算法

计算是考的后退n帧，选择

重传，否定性确认(没听说过)，传8个分组，其中第二个超时，各要多久返回搜狐，查看更多

责任编辑：