编程语言B卷参考答案.doc

学院 专业 姓名 学号 座号( 密 封 线 内 不 答 题 )密封线线_ _ 深圳大学期末考试试卷开/闭卷闭卷A/B卷B课程编号15030600课程名称编程语言学分2.5命题人(签字) 审题人(签字) 年 月 日题号一二三四五六七八九十基本题总分附加题得分评卷人一选择题（共10题，每小题2分，共20分，答案请填写在第四大题前的表格中）1. 以下哪条不影响语言的可读性？( ) A简单性 B. 正交性 C. 语法设计 D. 类型检查2. 开发专家系统时，通过描述事实和规则由模式匹配得出结论，这种情况下适用的编程语言是（ ）。 A逻辑式语言 B函数式语言 C脚本语言 D命令式(或过程式)语言3. 考虑以下文法： a | b b | b以下语句中哪个属于该文法生成的语言？( )A.bbaabbB.bbababbC.babaabbD.bababb4.以下哪些文法有二义性? （ ）A. +| * a|b|cB. +*| a|b|cC. *| + a|b|cD.以上三项均二义性5. 以下哪几项属于变量的属性？（ ）名字 类型 生命周期 数值 绑定A. B. C. D. 6. 以下哪些不属于根据存储空间划分的数组分类？（ ）A. 固定栈动态数组 B. 栈动态数组 C.静态数组 D.显示堆动态数组7子程序的一般特性包括以下哪几项？（ ）每个子程序只有一个入口调用子程序与被调用子程序之间是平等的当执行被调用子程序时，调用子程序被暂停被调用子程序终止时，控制权交还给调用子程序A. B. C. D. 8. 以下哪几项属于指针类型的设计问题？（ ）指针变量的生存期堆动态变量的生存期指针的声明指针的初始化A. B. C. D. 9. 在采用从右到左计算的语言中，已知b=10,以下哪些语句一定能改变变量b的值？（ ）A. if(b+ != 12) & (b5) b = b/2;B. while（(b+ / 3) | (b 12)）break;C. if(b+ != 12) | (b5) b = b/2;D. 以上三项都不能10. 以下哪些问题属于迭代语句的设计问题（ ）控制迭代语句的设计迭代语言的类型控制语句的位置迭代表达式无法表达的值A. B. C. D. 二判断题 （共10题，每小题1分，共10分，答案请填写在第四大题前的表格中）11. 声明式语言包括了逻辑式语言，关系式语言，和基于约束的语言。 （ ）12.程序语言描述分为语法和语义。 （ ）13.BNF中，句子是指由开始符号经过推导得到的字符串。 （ ）14.相对于BNF，EBNF虽然增强了可读性和可写性，但并未增强表达能力 。 （ ） 15.引用类型变量和指针变量一样，可以改变所指向的内存地址的数值 。 （ ）16.任何一个计数循环都可以用逻辑控制循环来构建，反之也成立。 （ ）17.显式堆动态变量是可以没有名字的。 （ ）18.在编程语言中，一般采用公理语义来验证程序的正确性。 （ ） 19.类型的扩展转换通常是安全的。 （ ）20.关系运算符的优先级通常高于算术运算符。 （ ）三填空题（共5空，每空2分，共10分，答案请填写在第四大题前的表格中）21.按照运算符的优先级从高到低排序有+， -（一元），=,and,结合性为从右到左，写出下列表达式的运算顺序。(1)a+bc=0 and c+d=(-a）(2)c(-d)=a and -a+by) then b = a-3 else b=2*a-1; b52. （6分）考虑下列程序：int x;void setx(int n) x = n;void printx() print(x); /打印函数void foo(function S, function P, int n) int x = 5; if n % 2 = 1 then setx(n); else S(n); if n 3 then printx(); else P();setx(0);foo(setx, printx, 1); printx();setx(0);foo(setx, printx, 2); printx();setx(0);foo(setx, printx, 3); printx();setx(0);foo(setx, printx, 4); printx();假设语言采用动态作用域，那么(1) 当采用浅绑定时，这个程序将打印出什么？(2) 当采用深绑定时，这个程序将打印出什么？3. （4分）考虑下列程序int i = 0;int fun(int k) if(i % 2 = 0) return k*2; return k;void main() int x = 3; x = +i + fun(x);(1) 如果操作数是从左到右计算，x的值什么？简要写出计算过程。(2) 如果操作数是从右到左计算，x的值什么？简要写出计算过程。4. （9分）考虑下列程序void swap(int a, int b) a = a+b; b = a-b; a = a-b; void main() int value = 2, list5 = 1,2,3,4,5; swap(value, list0); swap(list0, value); swap(value, listvalue);对以下每种参数传递方法，在每个swap调用后，变量value和list的值分别是什么？（1） 按值传递（2） 按引用传递（3） 按值-结果传递五、解答题（共2题，25+10，35分）1.（25分）假设某语言的表达式遵循如下的结合性和优先级规则： 优先级最高*(乘方)%, 一元+,一元-最低*,/结合性左结合%,一元+,一元-右结合*,*,/(1) 假设操作数是整数和c,d,e,且允许括号，请根据以上优先级和结合性，写出BNF(2) 根据（1）中的BNF，写出表达式+4%3/3*3的推导树及其最右推导前五步和后五步(3) 请写出计算这些表达式的属性文法，并对（2）中表达式进行计算2.（10分）给定下列程序r = x;q = 0;while (y = r) r = r y; q = q + 1;请分别写出在状态x=7,y=3下的操作语义和指称语义（包括具体过程）附加题 （共2题，10+20，共30分）1.（10分）假设FOR语句的形式为FOR (; ; ),以计算最弱前置条件为例，设计FOR语句的公理语义。2. （20分）利用附加题1中的规则，计算下列程序P和后置条件的最弱前置条件（包括具体过程）f = 1;for(c = n; c 1; c = c1) x = f;for(y = c; y 1; y = y-1) f = f + x; f = n!201702编程语言试卷 B 参考答案与评分标准一、 选择题（10小题，每小题2分，共20分）DADBC DDACA二、 判断题（10小题，每小题1分，共10分）TTFTF FTTTF三、填空题（5个空，每空2分，共10分）21（1）(a+b)1c)2=0)3 and (c+d)4=(-a)5)6)7(2) (c (-d)1)2=a)3 and (-(a+b)4)5=(-b)6d)7)8)922（1）(a+b)1c)2=0)3 and c)4+d)5=(-a)6)7(2) (c (-d)1)2=a)3 and (-a)4)5+b)65，即a8；条件不成立时，2a-15，即a3（1分）。因此if语句的前置条件是a8（1分）。最后的前置条件为2ba8（1分）。2. （6分）（1）1，0；2，0；3，0；4，0（第一组和第三组各1分，第二组和第四组各0.5分）（2）1，0，5，2；0，0；4，4（第一组和第三组各1分，第二组和第四组各0.5分）3. （4分）（1）从左到右：先算+i, 得1（此时i1），再算fun(x)，得3，结果为4（2分）（2）从左到右：先算fun(x)，得6，再算+i, 得1（此时i1），结果为7（2分）注：只写结果无过程得1分4. （9分）（1）按值传递：value=2, list5 = 1,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)（2）按引用传递：value=1, list5 = 2,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)value=3, list5 = 1,2,2,4,5 (1分)（3）按值结果传递：value=1, list5 = 2,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)value=3, list5 = 1,2,2,4,5 (1分)五、解答题（25+10=35分）1. (1) （5分） - * | / | - % | - + | - | - * | - INT | c | d | e | ( )注：只要文法正确即可得5分，否则根据产生式酌情给分，例如3个产生式1分（2）推导树（略）（5分），最右推导（略）（5分，每步0.5分）（3）属性文法，其中属性为val (1分) - * 语义函数：.val = mul(.val, .val) - / 语义函数：.val = div(.val, .val) - 语义函数：.val = .val - % 语义函数：.val = mod(.val, .val) - 语义函数：.val = .val - + 语义函数：.val = .val - - 语义函数：.val = -.val - 语义函数：.val = .val - * 语义函数：.val = power(.val, .val) - 语义函数：.val = .val - INT | a | b | c 语义函数：.val = lookup(table)l -( )语义函数：.val = .val注：只要语义函数符合（1）文法即可得6分，否则根据语义函数酌情给分，例如5个语义函数2分求值过程（略，可在（2）中推导树中标明），3分，只给正确结果得1分。2.（10分）记整个程序为P，循环语句为W。操作语义（5分）r=x, x=7,y=3 - x=7,y=3,r=7q=0, x=7,y=3,r=7 - x=7,y=3,r=7,q=0 (1分)（可合并为r=x; q=0, x=7,y=3 -x=7,y=3,r=7,q=0）在x=7,y=3,r=7,q=0下，y x=7,y=3,r=4,q=0q=q+1, x=7,y=3,r=4,q=0 - x=7,y=3,r=4,q=1（1分）(可合并r=r-y; q=q+1, x=7,y=3,r=7,q=0 - x=7,y=3,r=4,q=1)在x=7,y=3,r=4,q=1下，y x=7,y=3,r=1,q=2（1分）在x=7,y=3,r=4,q=1下，y x=7,y=3,r=1,q=2（1分）指称语义（5分）M(P)(x=7,y=3) = M(r=x; q=0; W)(x=7,y=3)= (M(W) M(r=x; q=0;) (x=7,y=3)= M(W)( M(r=x; q=0;)(x=7,y=3) )= M(W)( x=7,y=3,r=7,q=0 ) (1分)= M(r=r-y; q=q+1; W)( x=7,y=3,r=7,q=0 )= (M(W) M(r=r-y; q=q+1;) (x=7,y=3,r=7,q=0)(0.5分)= M(W)( M(r=r-y; q=q+1;)(x=7,y=3,r=7,q=0) )= M(W)( x=7,y=3,r=4,q=1 ) (1分)= M(r=r-y; q=q+1; W)( x=7,y=3,r=4,q=1 )= (M(W) M(r=r-y; q=q+1;) (x=7,y=3,r=4,q=1)(0.5分)= M(W)( M(r=r-y; q=q+1;)(x=7,y=3,r=4,q=1) )= M(W)( x=7,y=3,r=1,q=2 ) (1分)=x=7,y=3,r=1,q=2(1分)附加题（10+20=30分）1 （10分）若P stmt1 I，且I and cond stmt3;stmt2 I，那么则有P FOR (stmt1; cond; stmt2) stmt3 I and not cond注：转化WHILE语句也可以。2 （20分）外层For语句的不变式I1为 fn!/c! and c=0里层For语句的不变式I2为 f(n!/c!)*(c-y+1) and y0 and c=y and x =(n!/c!)(1)证明外层循环终止时能推出给定的后置条件(2) 求解外层for的最弱前置条件(2.1) 求解内层for的最弱前置条件(2.2) 求解x=f的最弱前置条件(3)求解f1的最弱前置条件 (n=0)(1)证明外层循环终止时能推出给定的后置条件I1 and not c 1 = fn!/c! and c=0 and c fn!/c! and c!=1 = fn!(2) 求解外层for的最弱前置条件(2.1) 证明I1 and c1 x=f;内