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