|
发信人: caeser_zy(^*^金牛座BB仔) 整理人: jasminwen(2003-04-13 18:15:46), 站内信件 |
| 中科院计算机技术研究所1998年硕士生入学试题 编译原理和操作系统
一.(10分)某操作系统下合法的文件名为 device:name.extension 其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,画出实现这种文件名的确定有限自动机. 二.(10分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法. S->S and S|S or S|not S|p|q|(S) 三.(10分)把表达式 - (a+b)*(c+d)+(a+b+c) 翻译成四元式. 四.(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,根据此表可以正确识别输入串是否为响应语言的句子.对于非二义非LR(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则? 五.(10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1. 试分析为什么会有这不同的结果. int fact() { static int i=5; if(i=0) {return(1); } else { i=i-1; return(( i+abs(1))*fact()); } } main(){ printf("factor or 5=%d\n",fact()); } 六.名词解释(每小题2分,共10分) 1) 线程 2)管程 3)管道 4)I/O重定向 5)动态地址重定位 七.填空(每空0.5分, 共10分) 1.为了赋予操作系统以某些特权,使得操作系统更加安全可靠地工作,实际操作系统中区分程序执行的两种不同的运行状态是___;___态程序不能执行特权指令. 2.引起进程调度的原因有:___,___和___. 3.在一个请求式页式存储系统中,一个程序的页面走向为1,2,1,4,3,2,3,5,1,2,1,3.假定分配给该程序的存储块数为4,则采用FIFO,LRU和LFU 页面置换算法时,访向过程中的缺页次数分别为___,___和___. 4.通道技术的引入,实现了___与___的并行;___与___的并行;___与___的并行. 5.设备分配程序除了向提出I/O请求的进程分配设备外,还要为他分配___,___和___ 6.文件系统通常向用户提供的接口有__接口和__接口. 7.UNIX文件系统中通过引入__索引结点来提高文件的检索效率. 八.简答题(共10分) 1.(5分)试述缺页中断的处理步骤;与一般中断相比,主要的区别是什么? 2.(5分)UNIX文件系统使用的地址索引结构是什么?与一般的地址索引结构相比有什么优点?付出的代价是什么? 九.算法题(共10分) 遵循同步机制的四条准则,写出用锁机制实现的解决读者--写者问题的同步算法. 十.(10分)简述UNIX系统V中块设备数据缓冲池的管理技术,给出缓冲池的结构和缓冲区的分配与释放操作. ----   |
|
[关闭][返回] |