清华912计算机专业基础综合考研历年真题回忆

盛世清北，专注清华北大考研辅导近10年，盛世清北-清华考研辅导班开设清华912计算机专业基础综合考研辅导系列课程。上清华北大，就上盛世清北！

2018年清华大学912计算机专业基础考研真题(回忆版)

第一部分数据结构(70分)
1、判断题10×2'
T(n)=T(n/2)+O(1)的解总是T(n)=O(log n)
比较算法CBA的排序与时间复杂度O(nlog n)
2、单选题8×3'
非法表达式+逆波兰式
evaluate()表达式求值算法

3、算法题6'+4'+3'
单峰向量:设计算法

4、算法题6'+4'+3'
最大和区间:设计算法求出一组数的最大和区间

2017清华大学计算机考研912真题(回忆版)

后序遍历中，first()函数和next()函数。(10分)

first()函数是求出后序遍历的第一个点，写出算法思路、伪代码

next()函数是求出当前节点后序遍历中的后一个结点，，写出算法思路、伪代码

由题意可知，通过first和next就能求出树的后序遍历，分析一下，这种方法与正常求后序遍历的方法有什么差异。

利用广度优先遍历的思想，求图中最小的围长，围长就是图中环的权加和，要求空间复杂度为O(n)，时间复杂度为O(ne)，e为边的个数，n为点的个数。(15分)

1.算法思路

2.伪代码

3.时间空间复杂度

我的思路是，对每一个结点都加一个信息，就是该结点父亲的信息。

按照广度优先遍历将所有结点入队，如果图中有环，会出现两个相连信息相同的结点。

找到相邻且相同的结点，根据父亲结点的信息，递归出环的所有结点，结束条件就是两个结点的父亲相同。

求出环的圈长，循环检查所有环，实时更新，最后输出最小圈长。

stl中的归并排序与正常归并排序的代码有些不同，下面给出stl中归并排序的源码(15分)

1.补全上文中确实的代码

2.解释上文划线代码的含义

3.这种归并排序与正常的归并排序相比有什么优缺点