四川大学1999年硕士研究生入学考试编译原理与操作系统

四川大学1999年硕士研究生入学考试编译原理与操作系统考试科目：编译原理与操作系统 科目代号：46# 试题适用专业：计算机软件与理论 一．判断下列命题，凡正确的打上"√"，否则打上"╳"；（4分） 1．素短语也是短语。（2分） 2．变乘法运算为递归加法运算是强度削弱。

四川大学1999年硕士研究生入学考试编译原理与操作系统考试科目：编译原理与操作系统 
科目代号：46# 
试题适用专业：计算机软件与理论 
一．判断下列命题，凡正确的打上"√"，否则打上"╳"；（4分） 
1． 素短语也是短语。（2分） 
2． 变乘法运算为递归加法运算是强度削弱。（2分） 
二．已知文法：（25分） 
G：S→A B
A→A b∣b B
B→a∣S b 
1． 给出句型A b b a a b的语法树。（5分） 
2． 给出句子b a b a a b得最右，最左推导。（4分） 
3． 消除文法G的左递归，令所得到的文法为G’。（2分） 
4． 计算文法G’每个非终结符及其后选的First。（6分） 
5． 计算文法G’每个非终结符的Follow。（4分） 
6． 判定文法G’是否是LL（1）的，若是则构造出其预测分析表。（4分） 
三，给出X：= -(a*b)+(-c+d)-(a*b-c)的间接三元式和四元式系列。（8分） 
四，已知Pascal程序为： 
program PRG (input,output)&#59;
Var x,y,z:integer&#59;
a:array[1..10] of integer&#59;
procedure P(x,y,z:integer)&#59;
Var r,s,t: integer&#59;
begin
read (r,s,t)&#59;
Z:=x*r+y+s+z-t&#59;
end
begin
read(x,y,z)&#59;
p(x,y,z)&#59;
Write(x,y,z)
end.
给出程序执行过程语句p(x,y,z),在完成参数传递并进入过程P 时的栈示动态分配内存图像。（13分） 
五． 多项选择题（在每小题的5个备选答案中选出1至5个正确的答案）（5分） 
1．分时系统和实时系统的特点是________
（1）交互性 （2）实时性 （3）多道性
（4）批量性 （5）独立性 
2．地址重定位实现的是________的映射。
（1） 外存空间到内存空间 （2）逻辑空间到物理空间
（2） 址空间到存储空间 （4）程序在内存存放位置（5）虚地址到实地址 
3. 操作系统中的作业控制方式一般可分为_________
(1) 直接控制和交互式控制 （2）脱机控制和交互控制式
（3）联机控制和批处理控制 （4）批处理控制和直接控制（5）自动控制和脱机控制 
4．加快开文件操作能够做到_________
(1)加快文件的查找速度 （2）建立文件与用户的 关系
（3）将文件内容读入内存 （4）验证用户对文件的使用权（5）件文件目录读入内存 
5 .系统发生死锁的原因是________西 
（1） 系统满足产生死锁的四个必要条件之一 
（2） 系统发生软/硬件故障 
（3） 系统资源不足支持多道程序的并发 
（4） 并发进程之间存在循环等待 
（5） 并发进程之间不适当的交*执行顺序 
六.判断题(判断下列各题的正误,并对错误的进行修改)L10分) 
1. 主存中出现"零头"问题的主要原因是每一个程序都占用连续的物理空间. 
2. 存储保护和文件的意义是相同的.所以采用的方法也是相同的. 
3. 特权指令是已注册用户调用操作系统程序时所用的特殊指令,一般用户不能使用. 
4. 同一文件在不同的存储介质上可以采用不同的物理组织方式,可以用不同的文件名. 
5. 银行家算法是系统防止死锁的一种有效方法. 
七.名次解释(10分) 
多道程序设计 可再入程序 位示图
抖动 设备独立性 
八.将要回答问题(12分) 
1. 处理机三级调度之间的关系是什么? 
2. 操作系统如何提高内存空间利用率? 
3. 文件系统中那些措施可提高磁盘文件的访问速度? 
九.在某一段页式存储管理系统中,其逻辑地址结构如下L5分) 
31 16 15 10 9 0
段号 页号 位移量
现有一作业的段表及页表如图所示：
段表 
段号 状态 页表大小 页表始址
0 1 512 3000
1 1 512 4000
2 1 1k 7000
3 0 1k 2000
4 1 512 5000
…… 
页表（部分）
起始地址 页号 状态 存储块号
…… 
3000 0 1 5
3003 1 0 0
3006 2 1 7
…… 
5000 0 1 1
5003 1 1 10
…… 
7000 0 0 21
…… 
（1） 逻辑地址（4，1，337）对应的存储单元地址是多少？ 
（2） 系统完成一次数据的存取需要访问几次内存？哪几次？ 
（3） 如果系统采用虚拟存储技术，则实现地址重定位可能发生哪些中断？其发生的先后次序是什么？ 
十， 试设计一种实现并发进程之间通信的方案，要求设计出通信所需的简单数据结构和实现通信的算法流程图。（8分）