1.(4分)
设有语言L(G)={adaR|aÎ(a,b)*,aR为a之逆}，试构造产生此语言的上下文无关文法G。

2.(10分)
设有语言L(G)={a2nb2n+1a2n|n30}
①给出描述语言的正则表达式R；
②直接画出识别该语言的状态转换图。

3.(8分)
LR分析器与优先分析器在识别句柄时的主要异同是什么？

4.(6分)
什么是规范句型的活前缀？引进它的意义何在？

5.(9分)
(简答下列问题)
①批处理、分时和实时操作系统各有什么特点？
②文件有那几种逻辑结构？有哪几种物理结构？
③产生死锁的必要条件是什么？

6.(9分)
某系统的进程状态图如下所示：
图1进程状态图
①说明一个进程发生变迁3、4、6的原因；
②下述因果变迁是否会发生？若会，在什么情况下发生？
(a)3®5;(b)6®4;(c)6®7;
③根据此进程状态图，说明该系统的CPU调度策略和调度效果。

7.(9分)
某一系统采用请求分页式虚存管理，页面淘汰算法为LRU(最近最少使用)法。每个作业占15页主存，其中一页用来存放程序，每一页存放200个整型变量。考虑下列程序：
var A,B:array[1..20,1..100] of integer;
i,j:integer;
begin
for i:=1 to 20 do
for j:=1 to 100 do
A[i,j]:=0;
for i:=1 to 20 do
for j:=1 to 100 do
B[i,j]=A[i,j];
end;
设数组A,B均按行存储，程序页已调入主存，变量i,j存放在程序页中。问此程序会产生多少次缺页中断？运行结束后，留在内存中有哪些页？