浙江大学2000年计算机系研究生入学考试试题
考试科目：计算机专业课（甲）
试题1：现有的操作系统对进程状态的定义不尽相同，有的还引入了挂起（suspend）状态。试简要分析挂
起状态的意义。
试题2：下述关于双进程临界区问题的算法（对编号为id的进程）是否正确：
do{
blocked[id]=true;
while(turn !=id
{
while(blocked[I-id]);
turn=id;
}
编号为id的进程的临界区
blocked[id]=false;
编号为id的进程的非临界区
}while(true);
其中，布尔型数组blocked[2]初始值为{false,false}，整型turn初始值为0，id代表进程编号（0或1）。
请说明它的正确性，或指出错误所在。
试题3：信号量如果只能取0或1为值，就变成了二元信号量。二元信号量更容易实现。而且，信号量可以由
二元信号量替换。以下所列函数试图用二元信号量操作waitB()和singalB()替换信号量wait()、signal()
：
wait(semaphore s)
{
waitB(mutex);
s=s-i
if(s<0)
{
signalB(mutex);
waitB(delay);
}
else
signalB(mutex);
}
signalB(semaphore) s}
{
waitB(mutex);
s=s+1;
if(s<=0)
signalB(delay);
signalB(mutex);
}
其中，用于互斥的二元信号量mutex初始化为1，用于进程挂起的二元信号量dealy初始化为0。请指出该
替换算法的错误所在。
试题4：已知某系统页面长4K字节，页表项4字节，采用多层分页策略映射64位虚拟地址空间。叵限定最高
层页表占1页，问它可以采用几层分页策略。
试题5：一进程已分配到4个页帧（page frame），如下表（所有数字都为10进制数，且以0开始）。
虚拟页号 页帧 装入时间 最近访问时间 记问位 修改位
2 0 60 161 0 1
1 1 130 160 0 0
0 2 26 162 1 0
3 3 20 163 1 1
当进程访问第4页时，产生缺页中断。请分别用FIFO（先进先出）、LRU（最近最少使用）、NRU（最近
不用）算法，决定缺页中断服务程序选择换出的页面。
试题6：现代操作系统必须支持多种文件系统类型（如CD-ROM的ISO9660、DOS的FAT等）。若要求用
如下所示的file_system_type结构描述文件系统类型，用vfsmount结构描述一个已安装（mount）的文
件系统：
struct file_system_type {
struct super_block *(*read_super) (struct super_block *, void *, int);
/* read_super所指的函数用于读出该文件系统在外存的超级块 */
const char *name; /*所描述文件系统的类型名，如FAT */
int requires_dev; */支持文件系统的设备 */
struct file_system_type * next; */指向另一种文件系统类型 */
};
struct vfsmount{
kdev_t mnt_dev; /* 文件系统所在设备的主设备号、次设备号*/
char *mnt_devname; /*设备名，如/dev/hdal */
unsigned int mnt_flage; /*安装目录名称 */
struct semaphore mnt_sem; /*设备标志，如ro */
struct super_block *mnt_sb; /*对设备I/O操作时的信号量 */
struct file *mnt_quotas[MAXQUOTAS]; /*指向超级块 */
struct file *mnt_quotas[MAXQUOTAS]; /* 指向配额文件的指针 */
time_t mnt_iexp[MAXQUOTAS]; /*inode有效期 */
time_t mnt_bexp[MAXQUOTAS]; /*数据块有效期 */
struct vfsmount *mnt_next; /*指向另一个已注册的文件系统 */
};
式设计一套数据结构，以描述一操作系统已经安装的文件系统及其类型（答题时，如已知条件不够，请作必
要补充）。
数据库管理系统（DBMS）有哪些主要功能？通常由哪几部分组成？
二、有如下的某工厂管理系统的概念模型，依图说明有哪些实体之间及实体内的值有对应联系，如何对应，
有否联系属性。
三、在关系数据库中，有哪些专门的关系运算？请用集合的形式表示它们。等值连接与自然连接有否有区别
？为什么？
四、有如下“学生_课程”数据库：
S(Sno, Sname, S***, Sage, Sdept)
学号 姓名 性别 年龄 学系
C(Cno, Cname, Cpno, Ccredit)
课号 课程名 先修课号 学分
SC(Sno, Cno, Grade)
成绩
1．用SQL语言定义模式时是如何说明参照完整性的。
2．用SQL语言的带NOT EXISTS谓词的嵌套查询，写出“查询选修了全部课程的学生姓名”的查询语句。
五、下面结论哪些是正确的，哪些是错误的？为什么？
1．任何一个二目关系都是属于BCNF的
2．当且仅当函数依赖A－>B在R上成立，关系R(A，B，C)等于其投影RI（A，B）和R2（A，C）的自
然连接。
3．若R.A－>R.B, R.A－>R.C，则R.A－>R.(B, C)
4．若R.B－>R.A, R.C－>R.A，则R. (B, C)－R. A
5．若R. (B, C)－>R.A, 则 R.B－>R.A, R.C－>R.A
六、并发操作可能会产生哪几类数据的不一致性？
《编译原理》部分试题
一、名词解释
a.句柄
b.上下文无关文法
c.LL(1)文法
d.LR(1)文法
e.语法制导的翻译
二、通过一个简单程序段的编译过程，描述编译程序的组成及工作流程。结合你举的程序段例子，描述每个
组成部分的输入输出，从而说明每个组成部分的功能。
三、写出一个可识别C语言的所有正整数的正规表达式，下面的例子都应当被识别：
0x89ab 0123 45 ‘z’ ‘\t’ ‘|xab|’ ‘\012’
四、下面的文法是LL（1）吗？为什么？如果不是，请把它转换为等价的LL（1）文法。
S à symbol stuff
∣ TOKEN TOKEN stuff
∣ star_list stuff
star_lish à star_lish STAR
∣ /*epsilon */
symbol à TOKEN
stuff à ANOTHER_TOKEN
五、写一个翻译程序，它的输入是含C语言的老式函数定义的方法，其翻译结果是C++的函数定义。例如：
老式函数定义
apostles(mat, mark, luke, juhn,fred)
char * mat;
long mark;
double luke;
{
}
其翻译结果将是C++的函数定义：
apostles(char *mat, long mark, double luke, int john, int fred)
{
}