上海交通大学一九九八年硕士研究生入学考试试题.docx

上海交通大学一九九八年硕士研究生入学考试试题
上海交通大学一九九八年硕士研究生入学考试试题
试题名称：编译原理及操作系统
试题编号20
操作系统部分（共50分）
1、进程p1,p2, 它是chomsky哪一型文法？请证aaabbbccc是G1的一个句子。（5分）


3、文法G2:PaPbQ
QbQcbSc
SSaa
1、请构造它的SLR分析表，
2、以说明它是不
3、是SLR文法。（７分）
２、在消除左递归、提取公共因子后可得等价文法Ｇ２，它是不是ll(1)文法。（６分）
四、求与正规R=(ab)*a(ab)*a(ba)*等价的minＤＦＡ（８分）
五、文法Ｇ3及相应翻译方案为
pbQb {print:”1”}
QcR {print:”2”}
Qa {print:”3”}
RQab {print:”4”}
1、该文法是不
2、是算符优先文法，
3、请构造算符优先关系表证实
之。（５分）
4、输入串为bcccaadadb时，
5、该翻译方案的输出是什么？（４分）


1、三维数组a[2:5,-2:2,5:7]首址为101,每个数组元素占４个存储单元，
2、求数组
元素a(3,1,6)的地址。（５分）
3、下列程序段若以Ｂ表示循环体，
4、Ａ表示初始化，
5、Ｉ表示增量，
6、Ｔ
表示测试。
上海交通大学一九九八年硕士研究生入学考试试题
试题名称：编译原理及操作系统
试题编号20
操作系统部分（共50分）
1、进程p1,p2,…..pn都含有对同
2、一共享数据进行存取的临界区（），
3、
请用锁（lock）和信号量（semaphore）各说明或设计一种临界区互斥机制，
4、除实现互斥执行外，
5、它们还能使欲进入临界区的进程不


6、会无限
期等待。（12分）
7? 1、进程用户态图象（映象）通常由哪些段组成？它们的作用和区别是什么？（6分）
2、在C语言程序中，如果没有对外部变量，静态局部变量和动态局部变量赋初值，则它们的初值是什么，请说明其原因。（7分）
三、1．请说明页式虚拟存储器的地址变换过程，并指出哪些操作是由操作系统完成的。（5分）
2．在上述地址变换过程中，3．进程状态有