- 考研 - 考研资料下载

1、 请写出在＝{a,b}上，2、 不3、 是a开头的，4、 以aa结尾的字符串集合的正规表达式，5、 并构造与之等价的状态最少的的DFA。（9分）

6、 给出方法G1：

S aSb P

P bPc bQC

Q Qa a

1、 它是Chomsky哪一型方法？

2、 它生成的语言是什么？

3、 它是不4、 是算符优先文法，5、 请构造算符优先关系表证实之。

6、 请证实所有（a）左递归文法（b）有公共左因子的文法均不7、 是ll(1)文法。

8、 文法G1消除左递归，9、 提取公共左因子后是不10、 是ll(1)文法？请证实。 （共15分）

三、给出文法G2:S SaS SbS cSd eS f

1、 请证实这是一个二义文法；

2、 给出什么的约束条件，3、 可构造出无冲突的LR分析表？请证实你的论点。（8分）。

四、给出下列代码序列：

(1) a:=b-c

(2) d:=a+4

(3) e:=a-b

(4) f:=c+e

(5) b:=b+c

(6) c:=b-f

(7) if b

(8) b:=b-c

(9) f:=b+f

(10) a:=a-f

(11) if a=c goto (3)

(12) halt

1、 请划分基本块，2、 并构造流图。

3、 假定各基本块出口之后的活跃变量均为a.c.f,循环中可用作固定分配的寄存器为R0和R1,固定分配给循环中哪二个变量，4、 可使执行代价省得最多？ （10分）

五、下列基本块内代码：

t1:=3*a

t2:=2*c

t3:=t1+t2

t4:=t3+5

t5:=2*c

t6:=3*a

t7:=t6+t5

t8:=t7-1

t9:=t4-t8

1、 请问dag进行局部优化。

2、 基本块出口时t9衡为6，3、 是否有进一步优化的方法，4、 可获得此结果？

（共8分）

操作系统原理部分

1、 你认为下列哪几种指2、 令应该在核心状态下执行：（10分）

（1） 屏蔽所有中断；

（2） 读时钟周期；

（3） 设置时钟日期；

（4） 改变存储映像图；

（5） 存取某地址单元的内容；

（6） 停机。

3、 请用信号量实现对某数据库的读者＿写者（reader-writer）互斥，4、 （10分）其要求是：

.读者与写者之间，写者与写者之间互斥；

.读者之间不互斥。

5、 一台计算机有8台磁带机，6、 它们由n个进程竞争使用，7、 每个进程可能需要3台磁带机，8、 请问n为多少时，9、 系统没有死锁危险，10、 请说明其原因。 （6分）

11、 当前磁盘读写位于柱面号20，12、 此时有多个磁盘请求以下柱面号顺序送至磁盘驱动器：10，13、 22，14、 20，15、 2，16、 40，17、 6，18、 38。寻道（track）时，19、 移动一个柱面需6MS，20、 按下列三种算法计算所需寻道时间（柱面移动顺序及所需时间，21、 总寻道时间；忽略最近指22、 定柱面后所需寻道时间）

（1） 先到先服（2） 务

（3） 下一个最邻近柱面

（4） 电梯算法（当前状态：向上）（10分）

23、 一台计算机有4个页推，24、 装入时间，25、 上次引用时间和它们的R(读)和M(修改)位如下所示（时间单位：滴答），26、 请问NRU、FIFO、LRO和第二次机会算法将替换哪一页？ (10分)

页 装入时间 上次引用时间 R M

0 126 279 0 0

1 230 260 1 0

2 120 272 1 1

3 160 280 1 1

6、在unix系统中，如果当前上当是/usr/wang,那么相对路径为../last/,文件的绝对路径是什么？ （4分）