考试科目：编译原理与操作系统
科目代号：46#
试题适用专业：计算机软件与理论
一．判断下列命题，凡正确的打上"√"，否则打上"╳"；（4分）
1．素短语也是短语。（2分）
2．变乘法运算为递归加法运算是强度削弱。（2分）
二．已知文法：（25分）
G：S→AB
A→Ab∣bB
B→a∣Sb
1．给出句型Abbaab的语法树。（5分）
2．给出句子babaab得最右，最左推导。（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程序为：
programPRG(input,output)&#59;
Varx,y,z:integer&#59;
a:array[1..10]ofinteger&#59;
procedureP(x,y,z:integer)&#59;
Varr,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分)
3116151090
段号页号位移量
现有一作业的段表及页表如图所示：
段表
段号状态页表大小页表始址
015123000
115124000
211k7000
301k2000
415125000
……
页表（部分）
起始地址页号状态存储块号
……
3000015
3003100
3006217
……
5000011
50031110
……
70000021
……
（1）逻辑地址（4，1，337）对应的存储单元地址是多少？
（2）系统完成一次数据的存取需要访问几次内存？哪几次？
（3）如果系统采用虚拟存储技术，则实现地址重定位可能发生哪些中断？其发生的先后次序是什么？
十，试设计一种实现并发进程之间通信的方案，要求设计出通信所需的简单数据结构和实现通信的算法流程图。（8分）