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

1、中国科学技术大学一九九一年招收硕士学位研究生入学考试试题试题名称:编译原理和操作系统编译原理部分(50 分)一. 填空(10 分)1. Chomsky定义的四种形式语言文法是(1)_文法又称_文法)(2)_文法又称_文法)(3)_文法又称_文法)(4)_文法又称_文法)2. 程 序 设 计 语 言 的 语 法 分 析 方 法 可 分 为 两 大 类 ,_ 和_;其中,前者采用_分析方法;后者采用_或_分析方法;3. 逻辑表达式的计算有_和_两种方式,选择哪种计算方式取决于_.4. 在一遍扫描的编译程序中,我们必须采取_手段来解决转移目标不明确的困难.5. Lex是用于_的工具;Yacc是用于_

2、的工具.6. 根据连接在文法符号上的属性间的依赖关系 ,属性被分为_ ,_互不相交的二大类.7. 参数传递方式有_ , _ , _等几种.二. 简答题(4 分)1. 整数和实数的算术运算是可兼容的,为什么编译器要区分它们?2. 什么是代码优化?举出至少三种用于代码优化的手段.三. 下列文法是否属于 LR(1),若是,则给出分析表;若不是指出原因(分析过程中可能遇到的麻烦),并考虑能否使其成为 LR(1)文法如何做? (10 )S ASES | AS | fE Ea | EbA c | d四. 说明 Pascal 语言和 C 语言的变量定义对编译程序实现的影响.(8 分)例: Pascal的变量

3、说明: 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. _是用户和外设、外存之间的接口.

4、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. 临界资源是_.

5、二.选择(四择一每题1 分共5 分)1. 软件共享的必要性是为了( ).A. 节约内存空间B. 缩短运行时间C. 减少内外存对换信息量 C. A和 C2. 请求页面存储管理采用( ).A.动态定位,静态分配,静态链接B.动态定位,动态分配,动态链接C.动态定位,动态分配,静态链接D.静态定位,静态分配,静态链接3. 用户的虚拟 CPU功能( ).A.和物理 CPU完全一样B.可以执行所有机器指令以及软件“指令”C.不能执行特权指令D.可以执行除特权以外的机器指令以及软件“指令”4. 虚拟存储管理中,段(或页)表需要( ),而快表中可以没有它.A.中断位C.改变位B.引用位D.B和 C5. OP

6、EN操作的目的是为了( ).A.将制定的文件记录复制到内存中B.将制定的 文 件 复制到内存中C.将制定的文件说明复制到内存中D.将制定的共享文件复制到内存中三.判断并改正(前4 题各1 分第5 题 6 分共10 分)1. ( ) 虚拟存储器空间的大小由外存容量决定.2. ( ) 在生产速度和消费速度完全相同时 ,只要用单缓冲就可以完全并行工作.3. ( ) 进程间的同步与互斥工具也是一种通讯工具.4. ( ) 虚拟设备和物理设备一一对应.5. 设有n个环形缓冲区,n和一个无穷序列 ,a , 甲进程序1列顺序逐个的把信息写入环形缓冲区中 ,而乙进程则逐个的把缓冲区信n息读出.(1) 请叙述甲、乙二进程的相互制约关系(2) 下列用 P、V 操作表示的同步算法有何错误.初值 S := 0 ;S := n;21甲进程乙进程V(S )P(S )11读出写入P(S )V(S )22(3) 用 P、V 操作写出正确的同步算法.四. (10 分)1. 叙述请求页面存储管理所需要的数据结构、软件支持和硬件支持.2. 叙述(或加说明画出)执行一条访内指令的过程.五. (10 分)设有四个进程P 、P 、P 、P ,有二组缓冲区:1: 由 7 个缓冲区组成;234: 由 100 个缓冲区组成.、P 的功能: 不断的往Q 中送初始信息;21P 的功能: 不断的取Q