程序设计理论各年试题参考答案

1、百度文库程序设计理论各年试题参考答案Madeby林祺颖试题预测(这些为本人意见，仅供参考)：/题目前有#为考试必考内容，即类似的题目一定会出，一定要灵活掌握。题目前有*符号的为基本不考内容，浏览一下即可。答案参考(如有任何补充或者感觉不对的地方，一定要向我提出来噢)：黑色的为个人感觉没有问题的部分，如果发现有错误，那一定要跟我说。红色的为个人感觉可以修改或者不确定，甚至不太会做的部分，大家一起讨论。绿色的为提示或者需要注意的部分。联系方式：在群上找林祺颖，或者，我基本都在。下面有些符号为了录入方便，都作了一些替代，标准符号可要看书。如3用W代替。程序设计理论试题2004年01月06日该卷答案基

2、本是一个师兄做的，红色为我补充的部分1. Showthat(P(Nat),)isnotaWell-foundedSet,but(S|SisafinitesubsetofNat,)isawell-foundedset解释：P(Nat)为自然数集合的集合。即Nat的PowerSet。取第1个集合为Nat,第2个集合为Nat-1,。，第n个集合为Nat-1,2,.n-1,则可以产生一个infinitedescendingsequence(无穷递降序列)，所以(P(Nat),)不是Well-foundedSet.设T=S|SisafinitesubsetofNat,若(T,)不是Well-founde

3、dSet,则必然存在一个infinitedescendingsequence,设为a1,a2,，an则a1a2an，从而|a1|>|a2|>>|an|因为ai属于T(i>=1),即ai是一个有限集，所以|ai|是一个有限的自然数，|ai|不能形成一个无限下降的序列，矛盾，所以(T,)是Well-foundedSet.2. Showthatforallformulasw1andW2,theformulaw1W2andW1VW2andlogicallyequivalent.证明w1%w2与w1Vw2逻辑等价，即是要证明|=w1w2w1Vw2.对于任意的小Interpreta

4、tionI,I(w1w2w1Vw2)(簿价于I(w1)(0-)I(w2)(0-)I(w1)(V)I(w2)(,),因为w1,w2:$Bool,所以I(w1)(b尸true或者I(w1)(尸false,I(w2)(r)=true或者I(w2)(0-)=false若I(w1)(b尸true,I(w2)(0-)=true,则I(w1w2w1Vw2)(0-)=(truetruetrueVtrue尸true;其余三种情况类似地也有I(w1w2w1Vw2)(true.所以|=w1w2w1Vw2,从而w1w2与w1Vw2逻辑等价。# 3.Considerevaluationofthelogicexpress

5、ionswithonlyoperators&&,|and|inCprogramminglanguage.ConstructanabstractmachineforevaluationoftheexpressionsandtrytodefinethemeaningfunctionM(e):Boolforanygivenexpressione.这题不会写。师兄也没给出答案。A_A题目意思是，对于一个只有&&,|,|操作的C语言逻辑表达式，建立起抽象机，并且给出对于给定的表达式e,给出对应的meaningfunctionM(e):Bool的定义# 4.Presentt

6、hepartialorder(BoolmBool,)graphically.Howmanyelementsdoesithave?Howmanyelementsaremaximal?这是一个定义在由Bool口映射到Bool口的函数的偏序集。并且是具有<=关系，所以某些映射是不能成立的，如(wture),(true,).电BoolcomBool3共有11个元素，用ai(1<=i<=11)表示如下:a1:(3,3),(true,w),(false,a2站()w,w),(true,w),(false,true)a3:(w,w),(true,w),(false,false)a4:(w,

7、w),(true,true),(false,w)a5:(w,w),(true,true),(false,true)a6:(w,w),(true,true),(false,false)a7:(w,w),(true,false),(false,a8:(w)w),(true,false),(false,true)a9:(w,w),(true,false),(false,false)a10:(w,true),(true,true),(false,true)a11:(w,false),(true,false),(false,false)14共有4个极大元。# 5.Designalogicprogramw

8、ithanequivalentmeaningasthefollowingfunctionalprogram:F(x)if(x=0)then1elsex*F(x-1)fi.WriteoutthecomputationsequenceofthefunctionalprogramforcomputingF(2).Constructaderivation(refutation)forthesamecomputationforthelogicprogram.(a)函数程序计算序列：F(2)=>(if 2=0 then 1 else 2*F(2-1)fi) =>(if false then 1

9、 else 2*F(1) fi) =>2*F(1)=>2*(if 1=0 then 1 else 1*F(1-1) fi) =>2*(if false then 1 else 1*F(0) fi) =>2*(1*F(0)=>2*(1*1)=>2(b)对应逻辑程序如下：F(0，1).F(x,n) F(x-1,m),n=x*m目标是 F(2,x)这里要注意，最后会出现不为空的情况(2=0,false),(2-1,1)(if false then 1 else 2*F(1) fi, 2*F(1)(1=0,false),(1-1,0)(if false then 1

10、 else 1*F(0) fi, 1*F(0)(F(0),1)(2*(1*1),2)（即不是Refutation ）,有一种理解是具有默认的式子true:-.另一种是需要加式子m:-(c)逻辑程序的derivation:F(2,x)=> F(1,m1),x=2*m1=> F(0,m2),m1=1*m2,x=2*m1=> m1=1*m2,x=2*m1=> m1=2, x=4F(x1,n1)F(x1-1,m1),n1=x1*m1F(x2,n2) F(x2-1,m2),n2=x2*m2F(0，1)x1/2,n1/x x2/1,n2/m1 m2/1=>再根据true:-和

11、替换(m1/2,x/4),可以归到口。6.Giveanexampleofafunctionalprogramforwhichthesemanticfunctionalistheidentityfunction.Explainwhy?假设在UsualInterpretationI=(Nat,I0)下，定义函数程序为：F(x)<=F(x)则指称语义函数：NatsNat<0Nat.NatJ定义为(F)=入F.入(x)下面证明是恒等函数，即对于任意的f,都有二f.在InterpretationI下，对于任意的fNatNats,和任意的nCNat%都有(n尸I(入F.入(x)(利F/fx/n

12、),(f)(n)=3n=3;=f(n)nw3；所以对于任意的nCNat如果n=co,则(n)=3=f(n),如果nw也同样有(n)=f(n),所以(f)=f,即是恒等函数#7.Givetheformaldefinitionofprogrampartialcorrectnessintermsofformulawlp(a,p),whereaisapathinthegivenprogram.这题首先必须要加入这个：Partialcorrectness就是指对于输入q,ifM(S)isdefinedandI(p)(M(S)(c)=truethenI(wlp(%p)(r)=true然后下面的内容是wlp

13、和vc的定义，不是该题的重点，是否写上看情况吧。令B是谓词逻辑的basis,p,q是WFFb的两个公式，SCLB是一个flowchart程序,a=(lo,li,k)是程序S中的一条路径，/(i)根据k的取值递归地定义wlp(a,p)如下：/如果k=0,则定义wlp(a,p)=p;/当k>0时，设3=(1,l2，k),r=wlp(p),根据l。处的语句类型，分成两种情况来定义wlp(a,p)./如果是平行的赋值语句，设形式如下所示：/l0:(x1,x2,xn):=(t1,t2,th)；gotol/则定义wlp(a,p)=r：.；;/,.,如果是条件转移语句，设形式如下所示：l0:ifeth

14、engotolelsegotol'fi;则定义wlp(a,q)如下:er如果li=l且liwl'er如果11w且l1=l'(ii)定义partialcorrectness的验证条件vc(p,a,q)为pw1p(a,q).令B为谓词逻辑的basis,p,q为WFFb的两个公式，SCLB是一个flowchart程序，对于任意的InterpretationI,程序S在InterpretationI中，对于p和q是partialcorrect的，当且仅当如果对于S中的任意一条路径a,都有验证条件vc(p,a,q)在I中为valid。#thatthefollowingisacor

15、rectinferenceruleinHoarelogicusingconstructionsequenceinInductiveDefinitionofSets”.WhatareBandKinthiscontext?Andwhatistheinductivelydefinedsetinthecontext?pr,reSr,(re)qpwhileedoSodqforallp,q,r£WFFb,eCQFFb,andSCL2B.设WFFb为well-formedformula的集合b=pXx:=tp|pewffb,xev,teTbK=(pr,rAeSr,(rAe)q),pwhileedo

16、Sodq)|p,q,rCWFFB,e6QFFb,SCl2推导出来的集合是Hoarecalculus里面logicallyvalid的公式集的一个子集。推导过程：P->rrAeS1rrAe->qrwhileedoSiodMepwhilerdoSiodq（即老师的样题）w n w或者n i, n Nat n! n Nat,0 n i -1程序设计理论试题1.Sfi|iNat,fi：NatwNatw,fi(n)试指出链S在Natw->Natw上的最小上界。有些人说论域就是CPO。对于该题，由于<二为平坦半序，所以每条链都有lub,最小元是w。所以可以构成CPO。S的最小上界为

17、：uSf|f(n)n!,nNat#2.利用归一算法。首先找到Di=f(a),x,取0i=x/f(a),得S9i=p(f(a),g(f(a),p(f(a),y)然后找到D2=g(f(a),y,取(2=y/g(f(a),得Sa2=p(f(a),g(f(a)即S可以归一。且(x/f(a),y/(g(f(a)在某份答案中说这是不能归一，这显然是错误的。这里的答案是正确的。在老师讲义上说不能归一，课堂上他明确表示第二条式x是a的时候才是不能归一。现在是可以归一的。3.二进制数句法：对于二进制数集合B,有和1属于Bb.如果a属于B并且a不等于0,则a0,a1属于B。很多份答案(可能包括老师答案)都没有表示

18、a不等于0,个人感觉是错误的，因为如01,001,这类数不是二进制数。这些要排除。对于B,我们给定一个解释I,其中+,*,为自然数中的加法和乘法：a.M0)=0na1,.0)=1natb.如果a属于B并且a不等于0,则(f)(a0)=(f)(a)*2nat,(f)(a1)=(f)(a)*2+1。c.M*)(a,b)=a*b,(j)(+)(a,b)=a+b/指称函数：?Xn-,X1X0.xn*2An+xn-1*2A(n-1)+,+x1*2+x0某些答案只写了一个递归的“指称函数”，感觉不对。/#的语义范函为：(S):D*D*,具体为：/i(S)=I(F.x.ifx=0then1elsex*F(x

19、-1)fi)()对任意的赋值ii(S)(f)(n)=I(ifx=0then1elsex*F(x-1)fi)(F/fx/n)若nor(n0f(n1)1ifn0n*f(n1)otherwise程序的Meaningfunction对任意的赋值ii(S)( )|i Nati , Mi (S尸(S)= I ( F. x. if x=0 then 1 else x*F(x-1) fi)()=其中 i(S)( )(n)若nornin!ifnNat,0ii1undefined若nMI=(3(S)()1i皿=n!otherwise5.设B为谓词逻辑的基，I为基的一个解释，为相应的状态集，S为Lib或L2B的程序

20、，Mi(S)为程序的语义函数，谓词：Bool和：Bool分别为前置条件和后置条件。则：1)程序S和谓词的最弱前置条件是指：谓词：Bool,满足(尸true当且仅当Mi(S)()有定义且(Mi(S)()=trueo2)程序S和谓词的最强后置条件是指：谓词：Bool,满足(尸true当且仅当存在一个状态使彳导()=true且Mi(S)()=。#6.对于基B(F,P),解释I为通常的解释。则(0)(7=0,(1)(d)=1,，+为Nat2->Nat,且(+)(a,b)(y=a+b,*为Nat2->Nat,且(*)(a,b)(ga*b,<=为Nat2->Bool,且(<=

21、)(a,b)(r=a<=b该公式的语义为(Vx.(0<=x)=trueiff所有的x属于Nat,(<=)(0,x)(r=true,即0小于等于x(不建议写成x大于等于0)。7.(P(3,1)=(y:=1;ify=1thenx:=1elsex:=2fi)(3,1)=(ify=1thenx:=1elsex:=2fi)(3,1)=(iftruethenx:=1elsex:=2fi)(3,1)=(x:=1)(3,1)=(1,1)#8.对于格局(S1,并对格局(S1,。转移到(S2,b),有：/当S1为whileedoSod;S'时，S'<>e,有声；且/S

22、2为a.S;S1、当(e)(6=true/b.S'当(e)(6=false/当S1为WhileedoSod时，有声；且S2为a.S当(e)(o)=true/b.e当(e)(o)=false/# 9.当使用通常解释I时，有F(2)=if2=0then1else2*F(2-1)fi/=iffalsethen1else2*F(1)fi=2*(if1=0then1else1*F(1-1)fi)=2*(iffalsethen1else1*(F(0)fi)=2*1*(F(0)=2*(if0=0then1else0*F(0-1)fi)=2*1=2/F(-2)由于不可终止，所以F(-2)未定义# 10

23、.Vc(q,(test,loop,upd,test),q)q->wlp(test,loop,upd,test),q)wlp(test,q)=q/wlp(upd,test),q)=q(y3+y2/y3)wlp(loop,upd,test),q)=q(y3+y2/y3)(y1+1,y2+2/y1,y2)wlp(test,loop,upd,test),q)=(y3<=x->(x=aA(y1+1)A2<=cAy3+y2+2=(y1+1+1)A2y2+2=2*(y1+1)+1)vc(,)=(x=aay1A2<=xay3=(y1+1)A2ay2=2*y1+1ay3<=x

24、1)->(x=aa(y1+142<=xy3+y2+2=(y1+1+1)A2ay2+2=2*(y1+1)+1)(可看书本P135)# 11.p->rrAeS1rrA-e->qrwhileedoS1odM-epwhileedoS1odq(可看书P153)程序设计理论期末练习题1 .可参考老师小¥题的第6题。/# 2.这题很难写。先给个思路：第一要建立一个well-foundedset(自然数集)，并且需要最小值为0。然后证明对于x<0,程序无定义。最后证明对于x>0,每次的计算都是递减。然后下结论。# 3.参考书本P50。/# 4.F(x)<-i

25、fx=0then1elsex*F(x)fiM(S)(3)：F(3)=-=6.可参考老师样题第9题。# 是程序，G是目标。当我们称是PUG的AS,是指对G的变量的一个替换。而CAS,是指一个AS,并且是对P的所有的变量的替换。AS是程序的中间过程，而CAS是程序运行的结果。、6 .对于(Ea,)而言，3为最小元，(Ea,)上有两条链均有限(见图)，故(Ea,)构成一个论域。X)而言，由定理，若(Eco,)构成一个论域，D3是一个集合，则(D3-E3)亦构成一个论域，其最小元：Dco-E3,(0)=,(1)=,()=。7 .有问题的题目。不过估计是x*F(x),老师样题4。# 8.又是一个很长的证

26、明过程。给思路：首先需要指出有3种关键路径，(begin,test),(test,loop,upd,test),(test,end),然后对每种路径都要证明该式成立。最后即可得出结论。# 9.这里不写证明了。可参考老师样题中的10。# 10.书本P152。/# 11.有问题的题目。把它改成。入(3冈)(出例=4/定义入(3,x加一个(Nat2->Nat)->Nat的函数，并设为G+/则Gqop)=F(3,x)(MF/op)=op(3,4)/则(入(3,x)*()(沪3*4=12。/可看书P95。程序设计理论期末考试（99）这年考试题目侧重于概念，与之后几年的题目有很大的区别* 1.

27、问得真直接。不好做。指称语义：定义了基类，然后由基类影射到相应的函数，然后由函数来定义其语义。操作语义：定义了抽象机，然后及其相关操作。由抽象机的运行和状态来反映其语义。异：指称语义表示的语言要比操作语义要多。指称语义重点在指称上，即所对应的函数上。而操作语义的重点在于抽象机的运行及其状态。* 2.使用CPO的目的是最终能够归到基类，并且能够归到F和V这两个最基本的类型。最小元表示函数影射的开始，也就是寻找对应的语义中的最小语义单位。Chain就是其影射过程，也即对应的语义解释过程。* 3.ImperativeLanguage:即命令方式语言。Algol-Like语言。该类语言通过各种相对独立

28、的语句，语句自身是不会直接或间接调用自己，可以通过独立地对每条语句的解释来进行语义分析。'DeclarativeLanguage即声明方式语言。Lisp-Like语言。该类语言使用声明性语句，语句自身会直接或者间接调用自己，通过对多个变量的映射关系，来最终确认其对应的语义。* 4.个人感觉是正确的。因为如果程序的语义脱离了形式系统，那么程序的语义就不能解释或者不可理解了。而程序的正确性也不可验证了。5 .参考老师样题。6 .参考老师样题。7 .参考课本P50。数据不同，最后结果为（式5,2,5,9）*8.书本P25。简单来说就是一个解释也4（w）（T）=trUe,（f）为W的Model

29、。9. Completeo因为定义了一个即每个chain都存在lub。这里要提出一个，R+U8也是CPQ有人提出链：，没有Lub。其实是有的，1 0lub1,即1.1910. M（S）=xmod2.11 .部分正确性是基于程序对输入有定义下的正确性，即程序对合法的输入是正确的。而完全正确性是需要证明其程序对输入有定义的，即程序对于输入是正确的，并且可以终止的。基于谓词的正确性是证明给定的谓词是正确的。基于公式的正确性是证明公式的守恒。12 .PartialCorrect:i:说明程序是无论有没定义都部分正确。Ii:说明程序是处处都没有定义。/Terminate:程序处处有定义。13 .程序输入

30、是x=y,输出是x=y!,所以最后的结果一定是让x为y!,y在程序中可变（改变以后可以归回原来的值），但最后的结果必定要让x=y!。并且y要等于原值才是计算阶乘的程序。14 .为了保证每条路径都遍历，即程序的运行情况都可保证。/15 .（f）pSq）（r）=trueiff/If（j）（p）（y=trueandifM（j）（S）（o-）isdefined,/Then（f）（q）（M（f）（S）（r）=true./看书P150/程序设计理论期末考试(2000)1 .想不到其他方法。用定义证明。2 .麻烦。直接证。不写了。3 .i:说明程序是处处都没有定义。iii.同iiv.程序处处有定义。/ii:

31、说明程序是无论有没定义都部分正确。iv.同iivi.说明程序是无论有没定义都可终止。4.程序的执行就是对机器的操作，即由一种状态转换到另外一种状态。程序状态：是程序真实的状态，与机器无关。机器状态：机器状态反映了程序状态。5.输入即x=2,y=2,z=2输出要符合x=2*yAy=4*z,可能的输出为x=16y=8z=2由于这题没说中间的结果，z的值可以改变，所以答案也可以是反正满足最后的条件就可以了。8,4,1。甚至24,12,3都可以。6.状态是由(11,d)转换到(12,(2)(2=dx/0(2)(2=/x/x+1(3) o2=dx,y/y,x(4)定义11下一指令为11',再下一

32、指令为11'.'o2=(r1且12=11'ifx!=012=11''ifx=07.老师样题。8.a1=(begin,3,6,end)a2=(begin,2,6,end)a3=(begin,3,5,end)awlp:m2<m1am3<m1wlp:m1<m2am2Vm3wlp:m2<m1am1<m3wlp:m1<m2am3Vm29.(a)两个方面。Continuous->相等由continuous定义可知，相等。相等->Continuous由Continuous定义可知。书P77。(b)不会做。10.类似于作业。可推出Refutation。下面是作业的解答。:-f(2,2,x):-f(2,1,y1),f(1,y1,x):-f(2,0,y2),f(1,y2,y1),f(1,y1,x):-f(1,1,y2),f(1,y2,y1),f(1,y1,x)(3)0=(m/2,n/2,y/y1)(3