国防科技大学编译原理和操作系统1996真题

大学计算机编译原理练习题及答案编译原理是计算机科学中的重要基础课程，其目的是让学生了解编译器的工作原理、构造与实现方法。

为了帮助同学们更好地掌握编译原理，以下是一些练习题及其答案，供大家参考学习。

1. 什么是编译器？它的主要功能是什么？编译器是一种将源代码（高级语言）转化为目标代码（机器语言）的软件工具。

它的主要功能包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

2. 简要解释编译器的工作原理。

编译器的工作原理可以分为以下几个步骤：a. 词法分析：将源代码分解成各个词素（tokens）的序列。

b. 语法分析：根据源代码的语法规则，构建语法树。

c. 语义分析：对语法树进行语义检查，确保程序的合法性。

d. 中间代码生成：将语法树转化为中间代码，方便后续的优化。

e. 代码优化：对中间代码进行各种优化，提高程序的性能和效率。

f. 目标代码生成：将优化后的中间代码转化为目标代码（机器语言）。

3. 解释以下概念：词法单元、词法分析器、上下文无关文法、语法分析器。

- 词法单元：是最小的语法单元，是词法分析器生成的结果。

可以是标识符、关键字、常量、运算符等。

- 词法分析器：负责将源代码分解为词法单元序列的工具，将输入的字符流转化为记号流。

- 上下文无关文法：是一种形式语言，用于描述程序中的语法结构，不依赖于上下文环境。

常用于语法分析器进行代码语法分析和生成语法树。

- 语法分析器：根据给定的上下文无关文法，对词法分析器生成的记号流进行语法检查和语法树的构建。

4. 下面是一个简化的算术表达式的上下文无关文法描述，请写出其对应的语法树。

```<expression> -> <term> | <expression> + <term> | <expression> - <term> <term> -> <factor> | <term> * <factor> | <term> / <factor><factor> -> <number> | (<expression>)<number> -> [0-9]+```例如，对于表达式 "3 + 5 * (2 - 1)"，对应的语法树为：```expression/ \expression +/ \ / \term + term| \ / |factor | factor| | |3 term factor/ \ |factor 5 2|term|factor|1```5. 简要解释语义分析的主要任务。

国防科技大学研究生院1999年硕士生入学考试计算机原理与系统结构试题命题标准答案、评分标准一．解释下列名词、术语的含义（每个2分，共20分）1.微指令周期：执行一条微指令所用的时间，包括微指令传送时间t1，执行微指令操作时间t2，形成下条微指令地址时间t3和读取微指令时间t42.形式地址：指令地址部分给出的地址，也称逻辑地址，通常用它不能直接访存，需要经过寻址计算得到有效地址3.机器负数：对1个补码数，国同它的符号位变反后末位加1（即求补）所得的数，称为该补码的机器负数4.字节多路通道：连接多台慢速外设，控制以字节交叉方式交换信息的通道5.脉冲拥挤效应：在磁表面记录信息中，随着记录信息密度的提高，会出现读出信息位间的相互干扰，造成信号幅度下降、峰值偏移、基线漂移等现象，称之为脉冲拥挤效应6.指令系统的规整性：指令系统中的三个元素：操作码、操作数和寻址方式是两两正交的。

7. TLB：即，转换查找缓冲器，用其可以将地址转换结果保存，这样就可以减少主存读写操作中的地址转换工作8. 定向：数据相关问题可以采用一种称为定向（也称为旁路或捷径）的简单技术来解决。

定向技术的基本观点是：在某条指令产生一个计算结果之前，其它指令并不真正需要该计算结果。

如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免暂停9. 相关：相近指令因存在某种关联而不能同时被解释10. Cache块冲突：一个主存块要进入已被占用的Cache块的位置二．填空（每空1分，共20分）（第1——5小题必做，在第6——12小题中，或做第6——9小题，或做第8——12小题）1．(计算机所用电子器件)2．（指令的完备性）、（指令的有效性）、（指令的规整性）3．（0舍1入法）、（恒置1法）4．（AB－C/DE＋F/－）5．（只读光盘）、（一次可写光盘）、（随时读/写光盘）6．（指令系统）、（计算机组成）、（计算机实现）7．（将寻址方式表示在操作码中）、（对每个操作数利用地址描述符表示其寻址方式）8．（水平或横向）、（垂址或纵向）、（混合）9．（RAW写后读）、（WA W写后写）10．（单功能流水线）、（多功能流水线）11．（1/Max（，，…，））12．(b2b1b0), (b1b0b2)。

2022年国防科技大学网络工程专业《操作系统》科目期末试卷B（有答案）一、填空题1、一个程序获得了一个__________和一个__________后，就说创建了一个进程。

2、操作系统中，进程调度通常有先来先服务、__________、__________和分级调度算法等调度算法。

3、同一进程中的各线程__________进程所占用的资源4、UNIX的shell有两层含义，一是指由shell命令组成的Shell命令__________；二是指该命令的__________。

5、主存的“地址越界”中断是属于__________中断。

6、文件存取方式按存取次序通常分__________、__________，还有一类__________。

7、设计实时操作系统时特别要注意两点，第一是__________，第二是__________8、操作系统中，进程可以分为__________和__________两类。

二、选择题9、I/O交通管制程序的主要功能是管理（）的状态信息。

A.设备、控制器和通道B.主存、控制器和通道C.CPU、主存和通道D.主存、辅存和通道10、下列天于管道（Pipe）通信的叙述中，正确的是（）A.一个管道可实现双向数据传输B.管道的容量仅受磁盘容量大小限制C.进程对管道进行读操作和写操作都可能被阻塞D.一个管道只能有一个读进程或一个写进程对其操作11、 CPU输出数据的速度远远高于打印机的速度，为解决这一矛盾，可采用（）。

A.并行技术B.通道技术C.缓冲技术D.虚存技术12、文件的顺序存取是（）。

A.按终端号依次存取B.按文件的逻辑号逐一存取C.按物理块号依次存取，D.按文件逻辑记录大小逐存取13、在系统内存中设置磁盘缓冲区的主要11的是（）。

A.减少磁盘1/0次数，B.减少平均寻道时间C.提高磁盘数据可靠性D.实现设备无关性14、考虑一个文件存放在100个数据块中。

文件控制块、索引块或索引信息都驻留内存。

国防科技大学研究生院2000年硕士生入学考试软件技术试题操作系统部分参考答案（非标准答案）一．（50分）操作系统部分1．（共30分，每小题5分）回答如下问题：（1）进程的现场信息主要包含：所有通用寄存器内容，程序寄存器PC，程序状态字PSW，存储映象寄存器。

这些内容用于在进程转换为执行状态时建立相应的运行现场。

（2）P（S1,S2）:While S1 <= 0 or S2 <= 0 do skip ;S1 : = S1 – 1 ;S2 : = S2 – 1 ;V（S1,S2）:S1 : = S1 + 1 ;S2 : = S2 + 1 ;（3）中断处理原则是对各类中断规定了不同的响应级别，把紧迫程度大致相当的中断源放在同一级，而把紧迫程度差别较大的中断源放在不同的级别，级别高的享有绝对优先响应的权利。

因而，象电源故障应设为最高级别31级；而用户进程应放在较低的中断级上运行。

（4）顺序结构适合对文件的顺序访问，不便于增补和删除；而链接结构空间利用率比顺序结构高，文件操作灵活；而索引结构适合于逻辑记录系散存于外存的各物理介质中，可能文件记录数据达到较大。

（5）系统“抖动”是指系统陷于不断地处理页故障的状态。

主要因素是驻留集太小。

（6）优先图如下：begin {l , m , n 初值为0}Parbeginbegin S1 ; V ( l ) ; end ;begin S2 ; V ( m ) ; end ;begin P ( l ) ; P ( m ) ; S3 ; V ( n ) ; end ;begin P ( n ) ; S4 ; end ;Parend ;end ;2．Begin {initial value of S is 50}。

编译原理_国防科技大学中国大学mooc课后章节答案期末考试题库2023年1.对于文法G(S')，该文法识别活前缀的DFA如下图，状态I5包含的项目有G(S')：(0) S' → S(1) S → iSeS(2) S → iS(3) S → a【图片】答案:S → iSeŸS_S → ŸiSeS_S → ŸiS_S → Ÿa2.(a+b)/(c-d)对应的逆波兰式(后缀式)是答案:ab+cd-/3.表达式(a+b)/c-(a+b)*d对应的间接三元式表示如下，其中三元式表中第(3)号三元式应为间接码表三元式表(1) OP ARG1 ARG2 (2) (1) + a b (1) (2) / (1)c (3) (3) (4) (4) - (2) (3)答案:( *, (1), d)4.设AS 为文法的综合属性集, AI 为继承属性集, 则对于下面的属性文法G(P)定义中，AS和AI正确描述是产生式语义规则P → xQR Q.b:=R.d R.c:=1R.e:=Q.a Q → u Q.a:=3 R → v R.d:=R.c R.f:=R.e答案:AS={ Q.a, R.d, R.f } AI={ Q.b, R.c, R.e }5.考虑下面的属性文法G（S）【图片】过程enter(name, type)用来把名字name填入到符号表中，并给出此名字的类型type。

按照该属性文法，关于语句【图片】 , 【图片】 , 【图片】:integr的语义描述准确的是答案:说明 , , 是integer变量，把 , , 三个名字填入符号表中，并在类型栏中填上integer6.考虑下面的属性文法G(S)【图片】对于输入字符串abc进行自下而上的语法分析和属性计算，设S.u的初始值为5，属性计算完成后，S.v的值为答案:187.关于属性文法，下列说法中正确的是答案:属性文法是对上下文无关文法的扩展。

国防科技大学2002年操作系统考研试题1,将“i/o为主“的进程定义为：当次类进程单独运行时，用于i/o 处理的时间远远多于处理机的处理时间：将”计算机为主“的进程定义为：当此类进程单独运行时，处理机的处理时间原远远多于处理的时间，若系统中运行的主要是这2类进程，才用什么样的调度算法更有利于资源的利用率，为什么？2。

请给出pcb的主要内容，描述当进程发生下面的状态转换是时：就绪—》运行，运行-》阻塞，操作系统要使用/修改pcb 中的那些内容？3。

请问，在一个进程内使用多现程有什么优点？4。

设系统有下面的解决死锁的办法：银行家算发；检测死锁，终止死锁状态的进程，释放该进程所占有的资源资源预分配请问那种办法可以达到最大的并发性，也就是那种办法可以让更多的进程无等待的向前推进？请按并发性的大小排列5。

请描叙页式虚存管理系统中页表项的主要内容，请简要描叙”缺页中断‘的处理过程，并结合该过程，说明其中使用/修改了表项的哪些内容，6。

简述os对文件读/写的系统调用所完成的工作7，简述以程述中断i/o方式，从外设读入一包n个字节的数据块的过程8若可以让文件分别在开始，中间，未尾增长，试讨论在顺述式，链接式以及索引式文件物理组织下的开销9。

（1）给出无忙等待的p，v操作的定义（1）考虑以下p，v操作的定义p(s):if s.value>0thens.value =s.value-1else beginplace this process in s.queue;block;end ;v(s)if there is at least one process waitting on semaphorethen beginremove a process p from s.queueplace process p on ready listendelses.value=s.value +1请问，当使用信号量和p，v操作做进程的同步和互斥控制时，是否可以在不改动程束时的情况下互换的使用（1）（2）中的p，v操作？这2组p，v操作有何不同？10，某工厂有3个生产车间和一个装配车间，3个生产车间分别生产a。

国防科技大学研究生院1996年硕士生入学考试编译原理和操作系统试题（操作系统部分）注意：1．统考生做一、二、三、四、五、七、八、九、十、十一、十二题2．单独考生做一、二、三、四、六、七、八、九、十、十一、十三题3．答案只能写在答题纸上一．选择题（在下列各小题的备选答案中，请把你认为正确答案的题号，填入题干后的括号内。

多选、少选及选错不给分。

每题3分，共15分）1．分时操作系统需要使用下面哪些成份。

（）①多道程序设计技术②作业说明书③终端命令解释程序④中断处理⑤优先级调度⑥系统调用2．进程具有哪些特性。

（）①动态性②共享性③并发性④相互制约性⑤独立性⑥静态性3. 在页式虚存管理系统中，若常发生抖动影响CPU的利用率，从系统管理员的角度，则下面哪些方法可改善CPU的利用率。

（）①用一个更快的CPU ②用一个更大的辅存③减少多道程序的道数④增加多道程序的道数⑤增大主存⑥采用更快的I/O设备4．在文件系统中，为实现文件保护一般应采用下面哪些方法。

（）①口令②密码③访问控制④复制⑤在读写文件之前使用OPEN系统调用⑥在读写文件之后使用CLOSE系统服务5. 从资源分配角度，操作系统把外部设备分为( )①独占型设备②共享型设备③快速型设备④慢速性设备⑤块设备⑥字符型设备⑦虚拟设备二、（9分）对访问串:1,2,3,4,1,2,5,1,2,3,4,5, 指出在驻留集大小分别为3,4时，使用FIFO和LRU替换算法的页故障数。

结果说明了什么？三．（8分）简述文件的二级目录组织形式。

欲实现文件共享如何处理？四．（8分）假设有5道作业，它们的提交时间及运行时间由下表给出：均周转时间。

五．（10分）设有如下图所示的工作模型。

四个进程P0，P1,P2,P3和四个信箱M0,M1,M2,M3进程间借助相邻的信箱传递消息：i P 每次从i M 中取出一条消息，经加工送入4)1(Mod i M 中。

其中M0,M1,M2,M3分别设有3,3,2,2个格子，每个格子放一条消息，初始时，M0装满了三条消息，其余为空。

中国科学技术大学一九九一年招收硕士学位研究生入学考试试题试题名称:编译原理和操作系统编译原理部分(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的变量说明: V AR a, b, c : integer ;C的变量说明: int a, b, c;五.Pascal程序设计语言不允许越过父过程或函数调用其中的子过程或函数,例如:procedure Aprocedure B┇procedure 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 ,…,n a ,… 甲进程序列顺序逐个的把信息写入环形缓冲区中,而乙进程则逐个的把缓冲区信息读出.(1) 请叙述甲、乙二进程的相互制约关系(2) 下列用P 、V 操作表示的同步算法有何错误.初值 1S := 0 ; 2S := n; 甲进程乙进程1) )2))(3) 用P 、V 操作写出正确的同步算法.四. (10分)1. 叙述请求页面存储管理所需要的数据结构、软件支持和硬件支持.2. 叙述(或加说明画出)执行一条访内指令的过程.五. (10分)设有四个进程1P 、2P 、3P 、4P ,有二组缓冲区: : 由7个缓冲区组成; : 由100个缓冲区组成.、2P 的功能: 不断的往1Q 中送初始信息;3P 的功能: 不断的取1Q 满缓冲区的信息加工后存入2Q 的空缓冲区中;的功能: 不断的取2Q 满缓冲区的信息并打印. 请:(1) 列出过程间的相互制约关系; (2) 设置必要的信号量;(3) 用P 、V 操作设计这四个进程的同步算法.(试题完)。

更多学校考研真题：/mydoc-4354614-1.html&folderId=74665国防科技大学研究生院1998年硕士生入学考试计算机原理与系统结构试题注意：1．统考生做一、二、三、四、五题2．单独考生做一、二、三、四、六题3．不用抄题，答案必须写在配发的答题纸上一．解释下列名词、术语的含义（每个2分，共20分）1.RISC2.程序访问局部性原理3. 快表4. “先写后读”相关5. 同构型多处理机6. 总线7. 扇区8. 多重中断9. 稀疏向量10.数组多路通道二．填空（每空1分，共20分）（第1——4小题必做，在第5——13小题中，或做第5——8小题，或做第9——13小题）1．某浮点机采用32位浮点二进制数据表示，其中8位（含1位符号）为移码表示的阶码，24位（含1位符号）为补码表示的规格化尾数，试写出可表示的最大正数（阶码：尾数：）和最小负数（阶码：尾数：）。

2．实现微程序快速转移的方法常有（）、（）、（）。

3．光盘存储器按存储介质可以分为（）、（）和（）三类。

4．刷新的基本要求是：（），（）和刷新期间不允许访存。

5．按照机器指令访问数据的方式，可以将当前绝大多数机器分为（）、（）和（）类型。

6．大多数并行处理机都是由一定数量的（）、一定数量的（）、某种形式的（）和某种形式的控制部件组成。

7．一般在DLX流水线中，分支延迟的三种调度方法是（）、（）和（）。

8．在存储器层次结构中，减少Cache命中时间的技术主要有：采用小且简单的Cache,在Cache 索引期间避免地址变换和（）。

9．Flynn分类法是按指令流和数据流的（）对计算机分类。

按此分类法，ILLIAC-IV属于（）计算机。

10．有效地址（）上界或（）下界，即出现越界错。

11．IBM370中的“测试与置定”指令TS的作用是（）,但它可能导致（）。

12．一个模m=32的多体存储器，其容量为1M字节。

对于给定的地址（二进制）：11010011110101110101，若采用低位交叉编址（二进制）为（）体内地址（二进制）为（）。