考试科目：编译原理与操作系统
科目代号：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);
Var x,y,z:integer;
a:array[1..10] of integer;
procedure P(x,y,z:integer);
Var r,s,t: integer;
begin
read (r,s,t);
Z:=x*r+y+s+z-t;
end
begin
read(x,y,z);
p(x,y,z);
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分）
科目代号：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);
Var x,y,z:integer;
a:array[1..10] of integer;
procedure P(x,y,z:integer);
Var r,s,t: integer;
begin
read (r,s,t);
Z:=x*r+y+s+z-t;
end
begin
read(x,y,z);
p(x,y,z);
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分）