21清华大学计算机考研真题回忆.docx

新祥旭 21 清华大学计算机考研真题回忆数据结构第一题复杂度 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 个分组，其中第二个超时，各要多久