清华大学 - 话题

[CS]04考题回忆v0.1

数据结构:
一. 判断
总共十小题，隔的太久，详细的内容记不清了，好像第一题是说线性表的各项类
型必须相同？还考了几道关于图的概念题（整张卷子就这里提到了图），不是很难
，比较基础的说。

二.从C++语法和软件工程的角度判断程序片断的对错，有则改之。

这个题型以前没有出现过，我自己也做的糊里糊涂，总共5题，只有一道记得比
较深刻(大概意思如下)

type retvalue (type *p) //时间长了，有可能有些地方不对

{

if(p == null ) return 0;

return *p;

}

这个函数的意思是根据返回值自动判断指针p是否为空，我觉得应该是错的，如
果p指向的值为0 ，那么就判断的有问题了

三.关于树的遍历的填空题。应该是03年或者02的第一大题的最后一道小题，由根结
点的中序遍历的序号，填写根结点左子树和右子树根节点的中序遍历序号。

四.关于线索树遍历的程序题，共两小题。具体的题目记不太清了，好像是由中序线
索树推倒前序遍历的next()函数？第二个是接着第一题问的，由next函数写出全部
的前序遍历？

五.关于排序的问答题。那段程序是shell排序（缩减增量排序？）的一个变种，第
一小题回答是什么排序，第二小题根据一个实际的排序例子写出排序过程中一趟的
详细情况,比较简单吧。

六.关于程序复杂度的计算题。大意是一个O(n2)的排序算法，20个数据时时间是t1
,那么200个数据时时间是多少？我感觉这道题要么出得很弱，要么难得没人能做得
出来，hiahia

七.算法题。根据一个实现队列功能的类提供的操作模拟一个栈，好像是书上的一个
习题吧？

操作系统:

一.名词解释，还算比较基本吧，如果把清华出的那本操作系统书上的习题部分看一
遍就没什么大问题了，好像考了一道“进程和线程的区别”？

二.有关进程调度的问题，也是比较基本吧，像轮转，先来先服务，优先级，最短时
间优先等算法都考到了，并且结合了一个具体的例子，写出每种算法情况下的cpu执
行过程.

三.一个有关磁盘读写次数的问题，它是和文件系统的索引部分和起来考的，大意是
考察不建索引和建了索引的访问过程与访问次数(好像清华以前没考过类似的问题，不过
北大考过)

四.pv操作。标准的写者优先前提下的读者写者问题。第四版上有详细的说明。

五.关于存储系统的访问的一个问答题，和分页的知识混在了一起。大意是描述怎样
通过页表，cache,磁盘 进行寻址？

欧洲通用货币是什么？

考研论坛提示：
1、请勿发布个人联系方式或询问他人联系方式，包括QQ和手机等。
2、未经允许不得发布任何资料出售、招生中介等广告信息。
3、如果发布了涉及以上内容的话题或跟帖，您在考研网的注册账户可能被禁用。