2011-2012安徽大学编译原理补考试卷

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

安徽大学2012 -2013学年第一学期《编译原理》（B卷）年级院系专业姓名学号座位号（闭卷时间120分钟）一．简答（20分）Array 1．说明编译方式与解释方式的区别2．什么叫文法？乔姆斯基将文法分为哪四类？3．简述DFA M 与NFA M的异同点4．解释语法分析中自底向上分析的一般过程5．解释名字和标志符的异同点文法G[S]：S S(S)S| ，请判断G[S]是否是二义文法，说明理由三、（15分）有语言L={w|w ∈ (0,1)+，并且 w 中至少有两个 1 ，又在任何两个1之间有偶数个 0 }，试构造接受该语言的确定有限状态自动机（10分）现有文法GE → E+T | E-T | TT → T*F | T/F | F F → (E) | i其中E 是文法的开始符号，求出句型（F ＋i ）－T*(E-T)的短语，简单短语，句柄和素短语 五、（10分）考虑文法 G[S]:S → (T) | a+S | a T → T,S | S消除文法的左递归及提取公共左因子。

请给对文法G[S]进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。

S → S*aA | aA| *aAA→ +aA | +a七、（10分）（1）if a<b OR c<d AND e>f then S1 else S2（2） while (A>B) do if (C<D) then X = Y+Z（3）令A是一个10×20的数组，写出赋值语句A[ I+2, J+1 ] =M+N的四元式序列八、（20分）已知文法G为:（0）S′→ S（1）S → aAd（2）S → bAc（3）S → aec（4）S → bed（5） A → e试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。

南昌航空大学2011—2012学年第一学期期末考试课程名称： 编译原理 闭卷 A 卷 120 分钟一、 单向选择题（在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题目前的表格中。

错1．表达式a-(-b)*c 的逆波兰表示（@为单目减）为 A 、a-b@c*B 、ab@c*-C 、ab@-D 、ab@c-*2．若B 为非终结符，则 A →α.B β 为 A 、移进项目B 、归约项目 C、接受项目 D 、待约项目3．编译原理各阶段工作都涉及 A 、词法分析B 、表格管理C 、语法分析D 、语义分析4．在语法制导翻译中不采用拉链回填技术的语句是A 、跳转语句B 、赋值语句C 、条件语句D 、循环语句5. 在属性文法中，终结符一定具有 属性A 、传递B 、继承C 、综合D 、抽象 6．已知文法G 是无二义的，则对G 的任意句型α：A 、最左推导和最右推导对应的语法树必定相同B 、最左推导和最右推导对应的语法树可能相同C 、最左推导和最右推导必定相同D 、可能存在两个不同的最左推导，但他们对应的语法树相同7. ______不是DFA的成分A、有穷字母表B、多个初始状态的集合C、多个终态的集合D、转换函数8. 代码优化时所依据的是A、语法规则B、词法规则C、等价变换规则D、语义规则9．描述一种语言的文法是 ( )A、唯一的B、不唯一的C、个数有限的D、不能确定10.已知语言｛a n b n c i|n>=1,i>=1｝，则下列哪个文法可以产生该语言 ( )A、S->AB,A->aAb|ab,B->cB|cB、S->aAb,A->aBb,B->cB|cC、S->aAb|A,A->bAc|cD、S->AB,A->aAb|ab,B->cB|ε二、填空题（每空1分，共 20 分）1、文法G产生的____________的全体是该文法所描述的语言。

编译原理A卷第 1 页共 4 页安徽农业大学经济技术学院2012―2013学年第1学期《编译原理》试卷（A 卷）考试形式: 闭卷笔试，2小时适用专业：2009级计算机科学与技术专业试卷总分：100分考试日期：2012年12月题号一二三四五总分评阅人得分一、填空题（请将答案写在答题卡上，每空2分，共14分） 1. 最左推导是指（1） .2. 设有文法G ，S 是它的开始符号。

如S * α且α∈(V ∪T)*，则称α是（2）；3. 设有文法G[E]：E →E+T T →T*F|F F →i|(E) 则非终结符号集V={ （3） }，终结符号集T={ （4） }；4. 设∑={0，1}，则∑上所有以1开头，后跟若干个（最少为1个）010串的句子集合对应的正规式为（5）；5. 词法分析器的输出结果是（6）；6. 一个LR 分析器包括两部分：一个总控程序和（7）；二、选择题（请将答案写在答题卡上，共10小题，每小题2分，共20分） 1. 作为编译程序的源程序不能是（）A 、高级语言B 、C 语言C 、低级语言D 、Java 语言 2. 词法分析所依据的是（） A 、语义规则 B 、构词规则 C 、语法规则 D 、等价变换原则 3. 文法G 产生的（）全体构成该文法描述的语言得分评阅人得分评阅人学院：专业班级：姓名：学号：装订线A、句型B、终结符集C、非终结符集D、句子4. 给定文法A→bA|cc，下面的符号串中为该方法句子的是（）①cc ②bcbc③bcbcc ④bccbcc ⑤bbbcc可选项有：B、①③④⑤C、①④D、①④⑤5. 词法分析器的输入是A、单词符号串B、源程序C、语法单位D、目标程序6. 编译过程中，语法分析器的任务是（）①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构可选项有A、②③B、②③④C、①②③D、①②③④7.（）不可能作为编译程序的目标代码A、汇编指令代码B、可重定位指令代码C、绝对指令代码D、中间代码8. 下列语法分析方法中属于自底向上语法分析方法的有（）①算符优先分析法②LL(1)分析法③预测分析法④LR(0)分析法⑤SLR(1)分析法A、①④⑤B、③④⑤C、②④⑤9. 一个文法所描述的语言是（）A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、具有二义性的文法描述的语言是不唯一的10. 下列能描述语言L(G)={0n|n≥0}的文法是（）A、S→0|0SB、S→ |0SC、S→0SD、S→S0三、判断题（下列说法正确的打“√”错误的打“×”得分评阅人请将答案写在答题卡上。

编译原理复习材料选择题1. 文法S→0S | S1 | 0的语言是( )。

A. { 0 m1m| m >=0 }B. { 0 m1m| m >=1 }C. { 0 m1n | m>=1,n>=0 }D. { 0 m1n | m>=0,n>=1 }2. 描述程序语言所采用的Ⅲ型文法是( )。

A. 短语文法B.正规文法C.上下文无关文法D.上下文有关文法3. 状态转换图实现的简单方法是使每个状态结对应( )。

A.一个终结符B.一个非终结符C.一段小程序D.一个函数4. 规范归约的关键问题是寻找( )。

A. 最左素短语B.句柄C.直接短语D.短语5. 一个算符文法的任何产生式的右部都不含有两个相继的( )。

A.终结符B.非终结符C.终结符和非终结符D.空字6. 算符优先分析法的关键在于规定( )。

A.算符优先顺序和结合性质B.算符优先顺序C.结合性质D.终结符和非终结符之间关系7. 优先函数的优点是( )。

A.形象直观B.便于进行比较运算C.语法分析速度快D.语法分析方法简单8. 文法符号的属性通常分为( )两类。

A. 共用属性和私有属性B.固有属性和可变属性C.语法属性和语义属性D.综合属性和继承属性9. 在程序流图中，组成循环的结点序列应满足( )A. 它们是强连通的B.它们中间有唯一的入口结点C.它们中间有一条回边D.它们是强连通的且有唯一的入口结点10. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。

A. C/B在T1中B. T1在C/B中C. R含有T1, T1在R中D. R含有C/B, C/B在R中1.D2.B3.C4.B5.B6.A7.B8.D9.D 10.C1. 编译方式与解释方式的根本区别在于( )A.是否生成目标代码B.是否生成中间代码C.是否生成汇编代码D.是否生成优化代码2. 编译程序生成的目标程序( )A.一定是机器语言的程序B.不一定是机器语言的程序C.一定不是机器语言的程序D.一定是汇编语言的程序3. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )A.εB. {ε0,1,x,y }C. {ε}D.Φ4. *假设G是一个文法，S是文法的开始符号，如果S===> x,则称x是( )A.短语B.句柄C.句子D.句型5. 一个算符文法的任何产生式的右部都不含有两个相继的( )A.终结符B.非终结符C.终结符和非终结符D.ε字6. 设有文法G[A]：A →Ax|Ay|Aa|Ac|a|b|c，下列哪些是该文法的句子( )(1) aby (2) aycyx (3) aaa (4) bcxyA.(1) (2) (3)B. (1) (2) (4)C.(2) (3) (4)D.全部7. ＬＲ分析器的核心部分是( )A.带先进后出存贮器的DFAB.一张动作表C.一张GOTO表D.一张分析表8. 在程序流图中，组成循环的结点序列应满足( )A.它们是强连通的且有唯一的入B.它们中间有唯一的入口结点口结点C.它们中间有一条回边D.它们是强连通的9. 表达式a≤b＋c∧a＞d∨a＋b≠e的后缀式式为( )。

黄冈师范学院2012—2013学年度第一学期期末试卷参考答案考试课程：编译原理考核类型：考试A卷考试形式：闭卷出卷教师：牛冀平考试专业：计算机科学与技术，软件工程考试班级：计科201001班，软件201001班一、填空（每空0.5分，共 10分）1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。

2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。

另外还有表格管理和（出错处理）。

3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。

4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。

5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。

6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。

（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。

8、表达式（a+b)*c的后缀表达式为（ab+c*）。

9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。

分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）10、代码优化的目的是（减少代码的时空开销）。

11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。

12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。

二、选择题（每题1分，共10分）1、文法的开始符号经多步推导产生的文法符号序列(仅包含终结符)是文法的（D ）。

A.短语B.句柄C.句型D.句子2、构造编译程序应掌握（D）。

A.源程序B.目标语言C.编译方法D.以上三项都是3、不属于循环优化的主要方法的是（B）。

A.强度削弱B.删除无用赋值C.删除归纳变量D.代码外提4、使用（A）可以定义一个程序的含义。

编译原理考试题
1. 编译器的作用是什么？简述编译器的基本工作流程。

2. 解释什么是词法分析。

描述词法分析器的基本工作原理。

3. 什么是语法分析？描述语法分析器的基本工作原理。

4. 解释语义分析的概念。

语义分析器的基本工作原理是什么？
5. 请简要解释编译器的前端和后端分别是做什么的。

6. 什么是中间代码？为什么编译器要生成中间代码？
7. 解释什么是符号表。

符号表在编译过程中起到什么作用？
8. 简述优化在编译过程中的作用。

列举并解释两种常见的优化技术。

9. 解释静态链接和动态链接的区别。

10. 请解释解释器和编译器之间的区别。

描述它们各自的工作
原理。

11. 解释冲突解析算法中的"移进-归约"冲突和"归约-归约"冲突。

12. 简述LL(1)文法和LR(1)文法的特点及区别。

13. 解释编程语言中的数据类型检查和类型推导的概念。

14. 简要描述语法制导翻译的概念和基本原理。

15. 请解释正则表达式和有限自动机之间的关系。

注意：以上为编译原理考试相关的问题，文中不含有标题相同的文字。

安徽大学计算机操作系统期末考试题及答案 Revised as of 23 November 2020安徽大学2011―2012 学年度第二学期一、单项选择题（每题1分，共20分）1．操作系统的发展过程是( C )A、原始操作系统，管理程序，操作系统B、原始操作系统，操作系统，管理程序C、管理程序，原始操作系统，操作系统D、管理程序，操作系统，原始操作系统2．用户程序中的输入、输出操作实际上是由( B )完成。

A、程序设计语言B、操作系统C、编译系统D、标准库程序3．进程调度的对象和任务分别是( C )。

A、作业，从就绪队列中按一定的调度策略选择一个进程占用CPUB、进程，从后备作业队列中按调度策略选择一个作业占用CPUC、进程，从就绪队列中按一定的调度策略选择一个进程占用CPUD、作业，从后备作业队列中调度策略选择一个作业占用CPU4．支持程序浮动的地址转换机制是( A、动态重定位 )A、动态重定位B、段式地址转换C、页式地址转换D、静态重定位5．在可变分区存储管理中，最优适应分配算法要求对空闲区表项按( C )进行排列。

A、地址从大到小B、地址从小到大C、尺寸从小到大D、尺寸从大到小6．设计批处理多道系统时，首先要考虑的是( 系统效率和吞吐量 )。

A、灵活性和可适应性B、系统效率和吞吐量C、交互性和响应时间D、实时性和可靠性7．当进程因时间片用完而让出处理机时，该进程应转变为( B )状态。

A、等待B、就绪C、运行D、完成8．文件的保密是指防止文件被( C )。

A、篡改B、破坏C、窃取D、删除9．若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由( D )临界区构成。

A、2个B、3个C、4个D、5个10．按逻辑结构划分，文件主要有两类：（记录式文件）和流式文件。

A、记录式文件B、网状文件C、索引文件D、流式文件11．UNIX中的文件系统采用（、流式文件）。

A、网状文件B、记录式文件C、索引文件D、流式文件12．文件系统的主要目的是（ A ）。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。

(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。

(×)3．一个算符优先文法可能不存在算符优先函数与之对应。

(√ )4．语法分析时必须先消除文法中的左递归。

(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

(√)6．逆波兰表示法表示表达式时无须使用括号。

(√ )7．静态数组的存储空间可以在编译时确定。

(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。

(× )10．一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式M 1 和M 2 等价是指_____。

A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。

2011～2012学年第1学期期末考试试卷答案《编译原理》（共4页）（考试时间：2011年12月25日）一、选择题（每题1分，共10分）1.B2.D3.A4.D5.D6.C7.B8.C9.D 10.B二、简答题（每题5分，共20分）1．何谓二义性文法？试举一例说明。

答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。

产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。

例子：给定文法G[<R>]：<R>→<R>*|<R><R>|a|b考察句子ab*，它有两棵不同的推导树，如下所示：<R><R> <R>a<R> *b<R><R> *<R> <R>aab2．通过合并LR(1)文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？为什么？答：可能会产生归约-归约冲突，一定不会产生移进-归约冲突。

因为在对LR(1)合并同心集合时，有可能将原本没有冲突的同心集的项目集合并后造成一些归约项目向前搜索符集合的交集不是空，产生归约-归约冲突。

但是由于文法本身已经是LR(1)文法，因此可知，在项目集中一定不存在移进-归约冲突，也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。

这样，在将同心集合并之后，移进项目要求输入的终结符和归约项目的向前搜索符集合的交集也还是空集。

3．自顶向下的预测分析方法为什么不能分析具有左递归的文法？答：在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将识别符号以及非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断替换的规则，造成无穷递归求解过程。

4．设G=（V N，V T，P，<S>）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？答：上下文无关文法的产生式形式为：A→α，其中，A∈V N，α∈（V N∪V T）*正则文法产生式形式为：A→aB，或A→a（右线性文法）其中，A,B∈V N，a∈V TA→Ba，或A→a（左线性文法）其中，A,B∈V N，a∈V T三、推导题（共70分）1．对于文法G[S]：S→aAcB|Bd A→AaB|c B→bScA|b（1）求句型aAaBcbbdcc和aAcbBdcc的句柄。

2013届毕业生毕业前补考《编译原理》试卷注意事项：本试卷适用于09级本科、11级专升本计算机科学与技术、软件工程专业学生。

一、单项选择题（在下列每题的四个选项中，只有一个选项是符合试题要求的。

请把答案填入答题框中相应的题号下。

每小题1分，共15分）1．编译的基本任务是（）。

A．将源语言程序翻译成目标语言程序B．将源语言程序翻译成等价的目标语言程序C．将高级语言翻译成机器语言D．将高级语言翻译成等价的机器语言2．构造编译程序应掌握（）。

A．源程序B．目标语言C．编译方法D．以上三项都是3．一个规范句型的句柄是它的（）。

A．最左直接短语B．最左素短语C．任意直接短语D．任意素短语4．给定文法G：A→xAx|y，其描述的语言是（）。

A．xyx B．xy n x C．x n yx n D．x n yx5．一个最小化的DFA是（）。

A．无多余状态的DFAB．无等价状态的DFAC．既无多余状态又无等价状态的DFAD．任意确定化有穷自动机6．设有语言L={α|α∈{a,b}+,且α不以b开头，但以bb结尾}，描述该语言的正规表达式为（）。

A．abb B．a(a|b)*bb C．aa*b*bb D．a(a*|b*)bb7．产生正规语言的文法为（）。

A．0型B．1型C．2型D．3型8．使用（）可以定义一个程序的意义。

A．语义规则B．词法规则C．产生规则D．语法规则9．以下（）不是优化技术。

A．删除公共子表达式B．强度削弱C．局部优化D．循环不变运算外提10．中间代码生成时所遵循的是（）。

A．语法规则B．词法规则C．语义规则D．等价变换规则11．局部优化是在基本块上进行的优化，所谓基本块是指（）。

A．一个入口、一个出口、顺序执行的语句序列B．循环体C．一个入口、一个出口的语句序列D．分程序12．给定文法G：Z→bMbM→(L|aL→Ma)则b和(的优先关系为（）。

A．b( B．b( C．b( D．不存在优先关系13．由文法的开始符号经0步或多步推导产生的文法符号序列是（）。

2011级一、填空题（每小题2分，共12分）1、编译各阶段的工作都要涉及到的工作是和。

2、设有字母表A={a,b,c},与A+ 等价的正则表达式是。

3、规范归约是指。

4、一个LR分析器的逻辑结构一般会包含、、等三个部分。

5、继承属性依赖于的属性。

6、词法分析是基于文法进行，即识别的单词是该文法的句子。

二、判断题（每小题1分，共10分）（）1、一个文法G的文法符号不属于V N就属于V T。

（）2、一棵语法树反映了其叶子结点从左到右连接成句型的一种推导情况。

（）3、（a|b）*与(ab)*是等价的正规式。

（）4、{ a n b n c n | n>0 }和{ a n b n | n>0 }都能用上下文无关文法产生。

（）5、依赖图是用于描述分析树中节点的属性及属性间依赖关系的有向图。

（）6、自上而下语法分析的“下”是指分析树的根结点或文法的开始符号。

（）7、SLR(1)与LR(1)中的“1”含义无区别。

（）8、最左素短语一定是短语。

（）9、对于任何一个编译程序，产生中间代码是不可缺少的。

（）10、逆波兰表示法用于表示表达式时不需要括号。

三、简答及简单应用题（每小题5分，共计20分）1、设计文法，其产生的语言L={a n b m c k | n<m+k,k≤n 以及m,n,k ≥1}2、在C语言中可以用如下两种方式建立符号常量：#define M 100 与const int m=100，请说明这两种方式的有何区别（结合编译的知识）。

3、有文法G[S] ：S → aAcB|Bd A → AaB|c B → bScA|b(1)试求句型aAaBcbbdcc 的句柄；(2) 写出句子acabcbbdcc 的最左推导过程。

4、文法G3[S]：S → a S b S | b S a S | ε是否为算符优先文法，说明理由。

四、属性文法G[S]如下：4S → ABCD { x = 11 * x + 1; }D → d { x = 7 * x + 1; }C → cc { x = 5 * x + 1; }B → Bb { x = 3 * x + 1; }B → b { x = x + 1; }A → gBa { x = 2 * x + 1; }根据语义规则，对句子gbbabbccd进行语法制导翻译，最终结果是什么？要求写出分析过程，否则不得分。

安徽大学2011—2012学年第 2 学期《信号与系统 》考试试卷（A 卷）（闭卷 时间120分钟）考场登记表序号一、选择题（每小题2分，共10分） 1．已知()f t ，为求(25)f t -应按照下列哪种运算求得正确结果（ D ） A ．(5)f t -左移2 B.(5)f t 右移2 C.(5)f t 左移25 D.(5)f t -右移252．已知系统的激励e (t )与响应r (t )的关系为：()()de t r t dt=，则该系统为（ A ） A 、线性时不变系统 B 、线性时变系统 C 、非线性时不变系统 D 、非线性时变系统 3．若信号f(t)的最高频率是4kHz ，则2tf()的乃奎斯特抽样频率为（ B ） A ．4kHz B. 2kHz C. 8kHz D.3kHz4. 因果序列的Z 变换1121 1.50.5z X(z)z z---=-+，则该因果序列的终值()x ∞为（ A ） A ． 0 B. 1 C. 2 D. 3 5．若系统函数23()32s H s s s +=-+，则该系统(A ) A ．不稳定 B. 稳定 C. 临界稳定 D. 以上均不对院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------二、填空题（每小题2分，共10分）1．求()()f t u t *= 。

2．某连续时间系统由两个冲击响应分别为1h (t)和2h (t)子系统串联构成，则该系 统的冲击响应为 。

3．对连续时间最小相移系统，其在S 平面的________平面无零点。

4．若信号的113s F(s)=(s+)(s+)-，求该信号的=)j (F ω 。

2011~2012安徽大学《数据结构》期末试卷2011~2012安徽大学《数据结构》期末试卷一、单选题1、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A、O(1)B、O(n)C、O(1Ogzn)D、O(n2)2、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。

A、O(n)B、O(1)C、O(n2)D、O(10g2n)3、n个顶点的强连通图中至少含有( )。

A、n—l条有向边B、n条有向边C、n(n—1)／2条有向边D、n(n一1)条有向边4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A、HL＝ps p一>next＝HLB、p一>next＝HL；HL＝p3C、 p一>next＝Hl；p＝HL；D、 p一>next＝HL一>next;HL一>next＝p5、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A、整形B、引用型C、指针型D、常值引用型·二、填空题1、在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。

2、表示图的三种存储结构为、和。

3、数据的存储结构被分为、、和四种。

4、在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。

5、对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。

6、中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为。

7、假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为。

8、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和。

三、运算题。

1、已知一个带权图的顶点集V和边集G分别为：V＝{0，1，2，3，4，5}；E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}，则求出该图的最小生成树的权。

2011-2012（二）编译原理B卷院系：_____________ 专业：_______________ 班级：_________ 学号：___________ 姓名：_____________山西师范大学 2011——2012 学年第二学期期末考试试题（卷）密封线密封线以内不准作任何标记密封线9．如果一个文法是二义的，则必然存在某个句子对应（）。

A．恰好两棵相同的推导树B．恰好两棵不同的推导树C．两棵或两棵以上不同的推导树D．最左推导和最右推导的推导树相同10．下列不属于局部优化的方法有（）。

A．多余表达式的删除B．常量合并C．删除无用表达式D．强度削弱二、（10分）已知文法G[E]：E→T|E+TT→F|T*FF→(E)|i画出句型T+T*F+i的语法树，并找出该句型所有短语、直接短语、句柄、素短语和最左素短语。

三、(10分) 设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。

四、(10分)考虑文法S→(S)S |ε1. 求非终结符S的First集合和Follow集合；（5分）2. 构建该文法的LL(1)分析表，判断该文法是否是LL(1)文法？为什么？（5分）五、（20分）有如下文法S→EE→bEa | aEb | ba1. 求该文法的LR(0)项目集规范族及识别活前缀的DFA；（10分）2. 构建该文法的LR(0)分析表；(5)3. 该文法是否是SLR(1)文法？为什么？（5分）六、（20分）考虑下述的语法制导定义产生式语义规则S→AB B.i:=S.iA.i:=2*B.sS.s:=A.sA→a A.s:=A.i+3B→b B.s:=B.i+41. 画出字符串ab的分析树；(5分)2. 根据语义规则画出分析树的依赖图；(5分)3. 根据依赖图写出语义规则的计算顺序；(5分)4. 假设S.i的初值为3，计算S.s的初值；(5分)。

安徽大学20 11 —20 12 学年第二学期《编译原理》考试试卷（B卷）（闭卷时间120分钟）院/系年级专业姓名学号1. 下面关于编译程序的说法不正确的是。

A. 代码优化是其不可缺少的一部分B. 中间代码生成是其不可缺少的C. 含有优化部分的编译程序的效率高D. 编译程序得到的目标程序可执行2.在编译过程中，语法分析器的任务是。

A.分析单词是怎样构成的B.分析单词串是如何构成语句和说明的C.分析语句和说明是如何构成的D.分析程序的结构3. 已知文法L={a n b m| m≥n≥0}，则下列文法可以产生L的是。

A.G[S] ：S→a S b | S b|εB.G[S] ：S→a S b | B B→Bb|εC.G[S] ：S→AB A→a A b|εB→Bb|εD.G[S] ：S→AB A→a A b|εB→bB|ε4. 描述单词的工具有。

A.正规文法B.正规式C.有限状态自动机D.下推自动机5.下面关于LL（1）文法的说法正确的是。

A.LL（1）文法都是无二义的B. LL（1）文法是LR（1）文法C.LR（1）文法是LL（1）文法D. 无左递归的文法是LL（1）文法6.在算符优先分析方法中归约的是。

A.句柄B. 直接短语C. 最左素短语D.素短语7.在语义分析过程中要完成任务是。

A.静态语义检查B.执行真正的翻译C.检查语义结构D.完成语义计算8.赋值语句 A*(B-C*(C/D))的逆波兰式是。

A.ABC-CD/**B.ABCCD/*-*C.ABC-*CD/*D.ABC-*CB/*9.下列关于存储管理的叙述中，正确的是。

A.栈式存储管理允许过程的递归调用B.栈式存储管理允许使用动态数据C.堆式存储管理允许过程的递归调用D.堆式存储管理允许使用动态数据10.循环优化主要采用的三项优化措施是 。

A.合并已知量 B.代码外提 C.强度削弱 D.删除归纳变量 二、（20分）设NFA M=（Q ，Σ，δ，S,F ）如下图所示：，b1.求出与之等价的DFA M ´；(8分)2. 求最小的DFA M （8分）3.求出DFA M ´接受的正规式；(2分)4.写出该自动机接受的语言。

贵州大学计算机科学与信息学院 2011-2012 学年第二学期考试试卷 A《编译原理》注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

一、 填空题(每空1分, 共20分)1. 有穷自动机接受的语言是 语言。

2.∑={a, b}，则∑上所有以字符a 开头的字符串的正规式为： 。

3. 活前缀是指规范句型的一个前缀，其中不含 之后的任意符号。

4. 编译程序的整个过程从逻辑上依次分为词法分析、 、语义分析、中间代码生成、代码优化和 等几个阶段。

另外还有两个重要工作是 和出错处理。

5. 语法分析方法可以分为 和 两大类。

6. 数据空间的动态存储分配方式可分为 和 两种。

7. 表达式a+b*(c-d)的逆波兰式为：。

8. LR(0)文法中，不会出现 冲突和 冲突。

9.LL(1)文法应该消除和。

10.嵌套过程静态作用域的实现方式通常有两种，一种是为每个活动记录增加一个称为访问链的指针，还有一种则是通过使用一个称为的指针数组来实现非局部名字的访问。

11.已知如下程序段，采用传值的方式进行参数传递时，程序输出结果为，采用传地址的方式进行参数传递时，程序输出结果为，采用传值结果的方式进行参数传递时，程序输出结果为，采用传名的方式进行参数传递时，程序输出结果为。

主程序子程序A:=2; B:=3; P(X,Y,Z);P(A+B, A, A); {Y:=Y+1;print A Z:=Z+X; }二、单选题(每题2分, 共20分)1.Chomsky定义的四种形式语言文法中，上下文无关文法是()。

A. 0型文法B. 1型文法C. 2型文法D. 3型文法2.设有文法G(S):S→b|bB B→bS，则该文法所描述的语言是()。

A. L(G)={b2i+1|i≥0}B. L(G)={b2i+1|i≥1}C. L(G)={b2i|i≥0}D. L(G)={b2i|i≥1}3.经过编译所得到的目标程序是()。