在校内找到了2006,2005.2004清华大学计算机系研究生入学考试专业课试题【详细回忆版】，在这儿贴出来分享给准备2007年考清华计算机的同学，希望对他们有所帮助。
【免费分享】2006清华大学计算机系研究生入学考试专业课初试试题
计组部分
一、填空题
1. a,b为两个1位2进制数，Carryin为低位进位，Carryout为高位进位，用and,or写出带进位的1位加法器的Carryout并化简，Carryout=____
2. 5段流水线分别为IF,__,EX,__,WB.
3. 一个串行程序可并行部分占%90，规模不变的情况下，串行程序并行化后加速比不超过_______
4. 二进制补码1111 1111 1111 1111 1111 1111 1111 1011化为十进制后为_______
二、判断题
1.CISC计算机比RISC计算机指令多。
2.速度为10MIPS的计算机一定比速度为5MIPS的计算机快。
3.SRAM比DRAM的速度快，成本高。
4.SCSI硬盘与SATA硬盘的速度，价格比较.
5.PCI-Express与AGP都可用于显卡接口
6.SPECCPU 2000基准测试程序可用于测I/O性能。
7.IEEE 754是计算机中的二进制整数算术标准。
8.全相联与直接映象Cache的比较
9.INTEL P4功率小于10w
10.64位CPU一般比32位CPU快一倍
11.增加流水线段数可提高CPU频率
12.VHDL是硬件描述语言。
13.EPIC是VLIW的发展
三、简答题
1.试说明为何编译程序要进行如下优化
for(j=0;j<200;j++)
{for(i=0;i<20;i++)
{
A[j]=A[j]+1;
}
}
编译优化后
for(i=0;i<20;i++)
{for(j=0;j<200;j++)
{
A[j]=A[j]+1;
}
}
2.硬盘平均寻道时间为12ms，传输速率为10MB/s，磁盘控制器延时为2ms,则一个转速为7200r/min的硬盘写1KB数据时间为多少?
3.为什么要设置二叉分支预测指令？画出2bit转移预测的状态图
数据结构
证明题:
1 证明在一棵满二叉树中分支B与叶子节点n0满足关系 B=2(n0-1)
2.证明，完全无向图中,两个顶点之间简单路径书目为:
1 + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2)
其中A(m,n)是m取n的排列数。
作图题:
给了一个Dijkstra无向连通图的最小生成树算法描述，要你根据该描述作出最小生成树及并查集的变化。
程序填空
给了一段排序算法，用静态链表描述的
1 问你这是什么排序算法（里面写着selectsort）
2 把挖去的5个空填上 （发现只有4个）
程序设计题
用链表表示的多项式
1 写类的描述
2 insert算法，如果相同指数合并，没有就插入
3 利用insert,给出多项式乘法的算法
操作系统
1 给出一个并发程序的描述:
semaphore X1=X2=Y=1;
int c1=c2=0;
procedure f1:
p(X1)
if (++c1 = 1) p(Y)
v(X1)
compute A
p(X1)
if (--c1 = 0) v(Y)
v(X1)
procedure f2:
p(X2)
if (++c2 = 1) p(Y)
v(X2)
compute B
p(X2)
if (--c2 = 0) v(Y)
v(X2)
问computeA和computeB各自能有多少并发执行，会不会出现饿死？
2 给出一个cpu的频率，使用基于时间片的轮转队列调度，并给出了参数。求调度的效率和响应时间。
3 使用多级页表，给出一些参数，如虚实地址空间大小、页大小、页表项大小等，问:
a) 多级页表的优点
b) 如果页表限制在一个页面里，问有多少页表项？
c) 进程页表占用多少内存？
4 把一个UNIX文件卷复制到另一个磁盘上，问:
a) UNIX文件卷由哪几部分组成？
b) 只复制文件数据，包括目录之后，不能访问，为什么？
c) 终于搞好了之后，发现有重复的硬链接，为什么？
5 给出了一个使用pthread的程序代码，里面系统调用包括fork()，thread()，join()等等，中间穿插print HELLO。问最后一共打印了多少个HELLO。
2005cs专业课题目
2005cs专业课题目
数据结构:
第一题:15分
1。线性表的定义，表中元素是否必须是同一个类型，为什么？
2。线性表有两种存储形式，定义如下，然后给了一个线性链表类的空架字，一个
静态数组实现类，一个单链表实现类，后两个继承于第一个。问使用时如何选用哪
种类型的实现。
3。二叉树给你前序和中序排列，求后序
所给序列已经记不清了，可能是前序ABDEFCFHIJ，中序DBCEAFCHIJ。
4。B树相关计算
一个磁盘块大小4，000（实际为4096，但是为计算方便，按4000算），一个地址指
针需要5个字节。有一个有20，000，000条记录的文件。一个关键字占5个字节，求
B树的最大阶数，当记录不是按顺序排列时，求索引需要占用的磁盘块数。
5。散列有n个位置，0~n-1。判断散列函数是否正确，插入和查找是否能正确执行
，如正确，判断好坏，不正确说明原因。random(n)函数能随机产生0~n-1之间的数
。
1) H(Key)=Key/n；
2) H(Key)=1;
3) H(Key+random(n))%n;
4) H(Key)%p(n)，其中p(n)是比n小的素数
第2题:5分
证明:在前序序列、中序序列和后序序列中叶节点相对(前后)的排列位置不变
第3题:15分
AVL树的插入和删除
1) 从空树开始插入数值,(数值序列也记不清楚了,只能写个大概,大家参考20,12,
9,27,22,17,16,15,18,10),画出插入后的状态,如需旋转,标明旋转的种类(有单右
旋转,单左旋转,先左后右旋转,先右后左旋转).
2) 从刚才生成的AVL树中删除22,...,9和10,画出删除后的状态和旋转的类型.删除
的非叶子结点用中序前趋结点代替.
第4题:
图类
template <class T> class Graph{
int numberOfVectise(Graph<class T> G){}//返回图中顶点数
.
.
.
}
1) 在图中用dijsktla算法求从u点出发到各个点的最短路径算.5分
template <class T> void shortestdist(Graph <class T> G,int v, float
*dist,int *path){
//在图G中求由点c出发到各点的最点路径,路径长度放在数组dist中,路径放在数组
path里,maxWeight是float型所能表示的最大值
int n=numberOfVectise(G);
int *S=new int[n];
for(int i=0;i<n;i++)
{
......
if(value(u,i)<maxWeight)1_____;
else path=-1;
....
后面有两个空是if（）中&&之前的第一个判断条件
}
}
整个函数太长,我记不得了，书上应该是有的.
2) 在一个图中,从u点出发,到图中各个点的最短路径中距离最长的叫做点u在这个
图中的偏心距.图中偏心距最小的点叫做中心.设计算法求一个图的中心.函数头为
template int centre(Graph<class T> G, float &mindist);
函数返回值是中心点编号,mindist返回的是最小偏心距.10分
这个题我记得练习册上有原题,只是换了一种表述,实质是一样的.
操作系统:
第一题:
1) TLB快表的结构、原理、作用
2) 内存能放1024页,CPU访问一个页表项用100ns,TLB有32个页表项,CPU访问TLB里
的一个页表项需要5ns,现在CPU访问一个页表项的时间是25ns,求快表的命中率.
第二题:
1) 反置页表的原理.(这个题的表述记不太清了,大概是这样的吧.把反置页表的结
构作用弄明白就没有问题了)
2) 外存有2^64字节存储空间,主存有256MB(2^28字节),一个页面有4KB(2^12字节
),计算一个进程可能的最大页表项数(用2^*表示),如果用反置页表表示,最大有多
少页表项.
第3题:
1) 写出unix文件系统的结构
2) 计算一个包含10个直接索引、一个一级间接索引、一个二级间接索引的最大文
件大小,要写出计算过程
第四题:
学生选课最多可以选3们，但是如果王同学选了3门C1C2C3后，想把C3换成C4，王同
学就得先退选C3再申请选修C4.但是这个时候可能C4已经选满了,而王同学想再选回
C3的时候可能已经被人选满,不能再选了.为了解决这个问题,使用一个函数
TradeCourse(user,course1,course2)将课程course1换成course2.下面给出一种实
现.如果有不正确,给出所有错误的执行情况,并给出你认为正确的实现.要有适当注
释.15分.
TradeCourse（user，course1，course2）{
course1->p(); //申请课程course1数据结构的互斥信号量
course1->drop(user); //退选课程course1
course2->p(); //申请课程course2数据结构的互斥信号量
if(course2->isFull()==false){//课程course2没有选满
course2->add(user);//申请选修课程course2
course2->v(); //释放课程course2数据结构的互斥信号量
course1->v(); //释放课程course1数据结构的互斥信号量
}
}
组成原理:
第一题:填空，每空1.5分，共18分
1、多处理机存储的两种组织类型是_____和_____
2、写出3种多处理机高性能通信网络________________________
3。硬盘的接口的两种类型____________________
4。举例应用局部性原理的两种系统_________________和________________
5。显卡的两种总线接口___________和_________
6。IA32机的最大主存空间是__________
第二题:20分
1。什么叫disk array,它的作用。3分
2。什么叫cache，它的原理和作用。6分
3。什么叫SMP,它个cluster（集群系统）比较有什么区别和联系。3分
4。写出RISC、CISC、VLIW的基本思想。5分
5。嵌入式cpu和普通 cpu比较有哪些特点？3分
第三题:选择，每个3分，共12分。选择题基本上都是历年出过的真题，去核对一
下就知道了。
1。浮点数的尾数3位，符号为1位，用补码表示；阶数2位，符号1位。x的尾数是
-0.875，阶数为1。y的尾数是0.625，阶数是2。则z=x-y规格化后的结果是:
A、1011011 B、******* C、******* D以上均不对
2。cache用组相联映射，一块大小为128字节，cache共64块，4块分一组。主存有
4096块。地址共需多少位:
A、19 B、18 C、17 D、****
3。指令的执行分为取指令用时△t，译址用时2△t，执行用时3△t。当流水执行的
时，时间接近:
A 1n△t B、2n△t C、3n△t D、6n△t
4。总线分同步总线和异步总线，其中同步总线具备的性质是:
1成本高、2成本低、3逻辑复杂、④逻辑简单、⑤⑥后两个想不起来了。
A、2、3、6 B、1、3、5 C、1、4、5 D、2、4、6
04 cs
[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,磁盘 进行寻址？ |
收藏
点赞!
反对!
楼主