编程语言B卷+参考答案.docx
《编程语言B卷+参考答案.docx》由会员分享，可在线阅读，更多相关《编程语言B卷+参考答案.docx（14页珍藏版）》请在冰点文库上搜索。
编程语言B卷+参考答案
编程语言B卷+参考答案
学院专业姓名学号座号
（密封线内不答题）
……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………
_____________________
…
深圳大学期末考试试卷
开/闭卷
闭卷
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.bbaabb
B.bbababb
C.babaabb
D.bababb
4.以下哪些文法有二义性?
（）
A.→
→+|
→*
→a|b|c
B.→
→+*|
→a|b|c
C.→
→*|
→+
21.按照运算符的优先级从高到低排序有+，-（一元），\，<=,and,结合性为从右到左，写出下列表达式的运算顺序。
（1）a+b\c<=0andc+d<=（-a）
（2）c\（-d）<=aand-a+b<=-b\d
22.假设所有运算符没有优先级，结合性为从左到右，指出21题中表达式的运算顺序。
23.子程序有哪些类别?
第一至三题的答案请填写在下面对应空格的位置上。
选择题题号
1
2
3
4
5
6
7
8
9
10
选择题答案
判断题题号
11
12
13
14
15
16
17
18
19
20
判断题答案
填空题题号
填空题答案
21
（1）
21
（2）
22
（1）
22
（2）
23
四、计算题（共4题，6+6+4+9，共25分）
1.（6分）计算下列语句和后值条件的最弱前置条件（请写出具体过程）
（1）t=x;x=y;y=t{x=nandy=m}（n,m是整数）
（2）a＝2*b+a;if（x>y）thenb=a-3elseb=2*a-1;{b>5}
2.（6分）考虑下列程序：
intx;
voidsetx（intn）{
x=n;
}
voidprintx（）{
print（x）;//打印函数
}
voidfoo（functionS,functionP,intn）{
intx=5;
ifn%2==1thensetx（n）;
elseS（n）;
ifn<3thenprintx（）;
elseP（）;
}
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分）考虑下列程序
inti=0;
intfun（intk）{
if（i%2==0）returnk*2;
returnk;
}
voidmain（）{
intx=3;
x=++i+fun（x）;
}
（1）如果操作数是从左到右计算，x的值什么？
简要写出计算过程。
（2）如果操作数是从右到左计算，x的值什么？
简要写出计算过程。
4.（9分）考虑下列程序
voidswap（inta,intb）{
a=a+b;b=a-b;a=a-b;
}
voidmain（）{
intvalue=2,list[5]={1,2,3,4,5};
swap（value,list[0]）;
swap（list[0],value）;
swap（value,list[value]）;
}
对以下每种参数传递方法，在每个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=c–1）{
x=f;
for（y=c;y>1;y=y-1）{
f=f+x;
}
}
{f=n!
}
201702《编程语言》试卷B参考答案与评分标准
一、选择题（10小题，每小题2分，共20分）
DADBCDDACA
二、判断题（10小题，每小题1分，共10分）
TTFTFFTTTF
三、填空题（5个空，每空2分，共10分）
21
（1）（（（（a+b）1\c）2<=0）3and（（c+d）4<=（-a）5）6）7
（2）（（（c\（-d）1）2<=a）3and（（-（a+b）4）5<=（（-b）6\d）7）8）9
22
（1）（（（（（（a+b）1\c）2<=0）3andc）4+d）5<=（-a）6）7
（2）（（（（（（c\（-d）1）2<=a）3and（-a）4）5+b）6<=（-b）7）8\d）9
注：
21和22小题中，主要不影响结果的顺序都可算正确。
23函数、过程
四、计算题（6+6+4+9=25分）
1.（6分）
（1）由后往前，最弱前置条件依次为：
{x=nandt=m},{y=nandt=m},{y=nandx=m}。
每个各1分。
（2）条件成立时，a-3>5，即a>8；条件不成立时，2a-1>5，即a>3（1分）。
因此if语句的前置条件是a>8（1分）。
最后的前置条件为2b＋a>8（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（此时i＝1），再算fun（x），得3，结果为4（2分）
（2）从左到右：
先算fun（x），得6，再算++i,得1（此时i＝1），结果为7（2分）
注：
只写结果无过程得1分
4.（9分）
（1）按值传递：
value=2,list[5]={1,2,3,4,5}（1分）
value=2,list[5]={1,2,3,4,5}（1分）
value=2,list[5]={1,2,3,4,5}（1分）
（2）按引用传递：
value=1,list[5]={2,2,3,4,5}（1分）
value=2,list[5]={1,2,3,4,5}（1分）
value=3,list[5]={1,2,2,4,5}（1分）
（3）按值－结果传递：
value=1,list[5]={2,2,3,4,5}（1分）
value=2,list[5]={1,2,3,4,5}（1分）
value=3,list[5]={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=7}
q=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<=r成立,执行循环体
r=r-y,{x=7,y=3,r=7,q=0}->{x=7,y=3,r=4,q=0}
q=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<=r成立,执行循环体
r=r-y;q=q+1,{x=7,y=3,r=4,q=1}->{x=7,y=3,r=1,q=2}（1分）
在{x=7,y=3,r=4,q=1}下，y<=r不成立,不执行循环体（1分）
因此，P,{x=7,y=3}->{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}，且{Iandcond}stmt3;stmt2{I}，那么则有
{P}FOR（stmt1;cond;stmt2）{stmt3}{Iandnotcond}
注：
转化WHILE语句也可以。
2（20分）
外层For语句的不变式I1为f＝n!
/c!
andc>=0
里层For语句的不变式I2为f＝（n!
/c!
）*（c-y+1）andy>0andc>=yandx=（n!
/c!
）
（1）证明外层循环终止时能推出给定的后置条件
（2）求解外层for的最弱前置条件
（2.1）求解内层for的最弱前置条件
（2.2）求解x=f的最弱前置条件
（3）求解f＝1的最弱前置条件（n>=0）
（1）证明外层循环终止时能推出给定的后置条件
I1andnotc>1=>f＝n!
/c!
andc>=0andc<=1=>f＝n!
/c!
andc!
=1=>f＝n!
（2）求解外层for的最弱前置条件
（2.1）证明{I1andc>1}x=f;内层for;c=c-1{I1}
{f＝n!
/（c-1）!
andc-1>=0}c=c-1{f＝n!
/c!
andc>=0}
（2.1.1）此次需计算内层for在f＝n!
/（c-1）!
andc>=1的最弱前置条件
（2.1.1.1）先证明内层for终止时能推出给定的后置条件
I2andnoty>1=>f=（n!
/c!
）*（c-y+1）andy>0andc>=yandy<=1
=>f＝（n!
/c!
）*candc>=1=>f＝n!
/（c-1）!
andc>=1
（2.1.1.2）证明{I2andy>1}f=f+x;y=y-1{I2}
在I2下求f=f+x;y=y-1的最弱前置条件为
f+x＝（n!
/c!
）*（c-y+2）andy>1andc>=y-1andx=（n!
/c!
）
即f=（n!
/c!
）（c-y+1）andy>1andc>yandx=（n!
/c!
）
因此I2andy>1成立
即内层for的前置条件为I2[y->c]=f=（n!
/c!
）（c-c+1）andc>0andc>=candx=（n!
/c!
）
即f=（n!
/c!
）andc>0andx=（n!
/c!
）
（2.1.2）求x＝f的最弱前置条件
{f=（n!
/c!
）andc>0}x=f{f=（n!
/c!
）andc>0andx=（n!
/c!
）}
即I1andI
升级会员 