中科大1991年编译原理和操作系统研究生考试试卷.doc

中国科学技术大学一九九一年招收硕士学位研究生入学考试试题试题名称:编译原理和操作系统编译原理部分(50分)一. 填空(10分)1. Chomsky定义的四种形式语言文法是(1)_文法(又称_文法)(2)_文法(又称_文法)(3)_文法(又称_文法)(4)_文法(又称_文法)2. 程序设计语言的语法分析方法可分为两大类,_和_;其中,前者采用_分析方法;后者采用_或_分析方法;3. 逻辑表达式的计算有_和_两种方式,选择哪种计算方式取决于_.4. 在一遍扫描的编译程序中,我们必须采取_手段来解决转移目标不明确的困难.5. Lex是用于_的工具;Yacc是用于_的工具.6. 根据连接在文法符号上的属性间的依赖关系,属性被分为_ , _互不相交的二大类.7. 参数传递方式有_ , _ , _等几种.二. 简答题(4分)1. 整数和实数的算术运算是可兼容的,为什么编译器要区分它们?2. 什么是代码优化?举出至少三种用于代码优化的手段.三. 下列文法是否属于LR(1),若是,则给出分析表;若不是,指出原因(分析过程中可能遇到的麻烦),并考虑能否使其成为LR(1)文法,如何做?为什么? (10分)S ASES | AS | fE Ea | EbA c | d四. 说明Pascal语言和C语言的变量定义对编译程序实现的影响.(8分)例: Pascal的变量说明: VAR a, b, c : integer ;C的变量说明: int a, b, c; 五. Pascal程序设计语言不允许越过父过程或函数调用其中的子过程或函数,例如:procedure Aprocedure Bprocedure Cprocedure D在过程D中不允许调用过程B,试解释其原因(8分).六. 给出将二进制数直接翻译成十六进制数的翻译方案.假定属性hex用于存放十六进制位串,串并置采用算符|.二进制数文法如下:S BS | BB 0 | 1操作系统部分(50分)一. 填空(每空1分,共15分)1. 操作系统的基本特征是_和_.2. _是用户和外设、外存之间的接口.3. 产生死锁的原因是_和_.4. 有一个530字的程序.考虑如下访问内存的逻辑地址序列:10,11,104,107,73,526,185,245,246,309,458,364,442,247,248,434.假定页面大小为100字,则其对应的页面走向序列为:_.如每个进程最多可分给300字内存空间,且采用LRU算法,则其缺页次数为_次,其缺页率为_.5. 段表中设“改变位”的目的是_.6. 为了_而引入多道程序设计.7. 逻辑设备是_.8. JCB的作用是_和_,它由_建立.9. 临界资源是_.二. 选择(四择一,每题1分,共5分)1. 软件共享的必要性是为了( ).A. 节约内存空间B. 缩短运行时间C. 减少内外存对换信息量C. A和C2. 请求页面存储管理采用( ).A.动态定位,静态分配,静态链接B.动态定位,动态分配,动态链接C.动态定位,动态分配,静态链接D.静态定位,静态分配,静态链接3. 用户的虚拟CPU功能( ).A.和物理CPU完全一样B.可以执行所有机器指令以及软件“指令”C.不能执行特权指令D.可以执行除特权以外的机器指令以及软件“指令”4. 虚拟存储管理中,段(或页)表需要( ),而快表中可以没有它.A.中断位B.引用位C.改变位D.B和C5. OPEN操作的目的是为了( ).A.将制定的文件记录复制到内存中B.将制定的 文 件 复制到内存中C.将制定的文件说明复制到内存中D.将制定的共享文件复制到内存中三. 判断并改正(前4题各1分,第5题6分,共10分)1. ( )虚拟存储器空间的大小由外存容量决定.2. ( )在生产速度和消费速度完全相同时,只要用单缓冲就可以完全并行工作.3. ( ) 进程间的同步与互斥工具也是一种通讯工具.4. ( ) 虚拟设备和物理设备一一对应.5. 设有n个环形缓冲区1,2,3,n和一个无穷序列, 甲进程序列顺序逐个的把信息写入环形缓冲区中,而乙进程则逐个的把缓冲区信息读出.(1) 请叙述甲、乙二进程的相互制约关系(2) 下列用P、V操作表示的同步算法有何错误.初值 := 0 ; := n;甲进程乙进程V()P() 读出写入 P()V()(3) 用P、V操作写出正确的同步算法.四. (10分)1. 叙述请求页面存储管理所需要的数据结构、软件支持和硬件支持.2. 叙述(或加说明画出)执行一条访内指令的过程.五. (10分)设有四个进程、,有二组缓冲区: 由7个缓冲区组成;: 由100个缓冲区组成.、的功能: 不断的往中送初始信息;的功能: 不