精品大学课件--上海交大计算机电子-编译原理与操作系统九九.doc

标准美女-出售国内外标准、论文、大学课件、考研资料等本文档由标准美女（标准王国）整理，仅作学习交流使用。如文档存在缺页、字迹模糊、乱码等情况，请大家通过论坛消息与我联系。 上海交通大学一九九九年硕士生入学考试试题 试题序号20 试题名称：编译原理及操作系统。编译原理部分（共50分）1、请写出在a,b上，2、不3、是a开头的，4、以aa结尾的字符串集合的正规表达式，5、并构造与之等价的状态最少的的DFA。（9分）6、给出方法G1： S aSb PP bPc bQCQ Qa a1、它是Chomsky哪一型方法？2、它生成的语言是什么？3、它是不4、是算符优先文法，5、请构造算符优先关系表证实之。6、请证实所有（a）左递归文法（b）有公共左因子的文法均不7、是ll(1)文法。8、文法G1消除左递归，9、提取公共左因子后是不10、是ll(1)文法？请证实。 （共15分） 三、给出文法G2:S SaS SbS cSd eS f1、请证实这是一个二义文法；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 bc goto (10)(8)b:=b-c(9)f:=b+f(10)a:=a-f(11)if a=c goto (3)(12)halt1、请划分基本块，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-t81、请问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 M0 126 279 0 0 1 230 260 1 0 2 120 272 1 13 160 280 1 16、在unix系统中，如果当前上当是/usr/wang,那么相对路径为./last/,文件的绝对路径是什么？