Free考研资料

标题: 清华大学2006年计算机系专业课考研试题 [打印本页]

作者: yueshen22 时间: 06-10-26 23:18
标题: 清华大学2006年计算机系专业课考研试题
操作系统
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。

数据结构

证明题：

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,给出多项式乘法的算法

欢迎光临 Free考研资料 (http://bbs.freekaoyan.com/)