程序設計理論各年試題參考答案

1、百度文庫程序設計理論各年試題參考答案Madeby林祺穎試題預測(這些為本人意見，僅供參考)：/題目前有#為考試必考內容，即類似的題目一定會出，一定要靈活掌握。題目前有*符號的為基本不考內容，瀏覽一下即可。答案參考(如有任何補充或者感覺不對的地方，一定要向我提出來噢)：黑色的為個人感覺沒有問題的部分，如果發(fā)現(xiàn)有錯誤，那一定要跟我說。紅色的為個人感覺可以修改或者不確定，甚至不太會做的部分，大家一起討論。綠色的為提示或者需要注意的部分。聯(lián)系方式：在群上找林祺穎，或者，我基本都在。下面有些符號為了錄入方便，都作了一些替代，標準符號可要看書。如3用W代替。程序設計理論試題2004年01月06日該卷答案基

2、本是一個師兄做的，紅色為我補充的部分1. Showthat(P(Nat),)isnotaWell-foundedSet,but(S|SisafinitesubsetofNat,)isawell-foundedset解釋：P(Nat)為自然數(shù)集合的集合。即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|是一個有限的自然數(shù)，|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口的函數(shù)的偏序集。并且是具有<=關系，所以某些映射是不能成立的，如(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)函數(shù)程序計算序列：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)這里要注意，最后會出現(xiàn)不為空的情況(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)下，定義函數(shù)程序為：F(x)<=F(x)則指稱語義函數(shù)：NatsNat<0Nat.NatJ定義為(F)=入F.入(x)下面證明是恒等函數(shù)，即對于任意的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,即是恒等函數(shù)#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。對于該題，由于<二為平坦半序，所以每條鏈都有l(wèi)ub,最小元是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的時候才是不能歸一?，F(xiàn)在是可以歸一的。3.二進制數(shù)句法：對于二進制數(shù)集合B,有和1屬于Bb.如果a屬于B并且a不等于0,則a0,a1屬于B。很多份答案(可能包括老師答案)都沒有表示

18、a不等于0,個人感覺是錯誤的，因為如01,001,這類數(shù)不是二進制數(shù)。這些要排除。對于B,我們給定一個解釋I,其中+,*,為自然數(shù)中的加法和乘法：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/指稱函數(shù)：?Xn-,X1X0.xn*2An+xn-1*2A(n-1)+,+x1*2+x0某些答案只寫了一個遞歸的“指稱函數(shù)”，感覺不對。/#的語義范函為：(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為基的一個解釋，為相應的狀態(tài)集，S為Lib或L2B的程序

20、，Mi(S)為程序的語義函數(shù)，謂詞：Bool和：Bool分別為前置條件和后置條件。則：1)程序S和謂詞的最弱前置條件是指：謂詞：Bool,滿足(尸true當且僅當Mi(S)()有定義且(Mi(S)()=trueo2)程序S和謂詞的最強后置條件是指：謂詞：Bool,滿足(尸true當且僅當存在一個狀態(tài)使彳導()=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(自然數(shù)集)，并且需要最小值為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的函數(shù)，并設為G+/則Gqop)=F(3,x)(MF/op)=op(3,4)/則(入(3,x)*()(滬3*4=12。/可看書P95。程序設計理論期末考試（99）這年考試題目側重于概念，與之后幾年的題目有很大的區(qū)別* 1.

27、問得真直接。不好做。指稱語義：定義了基類，然后由基類影射到相應的函數(shù)，然后由函數(shù)來定義其語義。操作語義：定義了抽象機，然后及其相關操作。由抽象機的運行和狀態(tài)來反映其語義。異：指稱語義表示的語言要比操作語義要多。指稱語義重點在指稱上，即所對應的函數(shù)上。而操作語義的重點在于抽象機的運行及其狀態(tài)。* 2.使用CPO的目的是最終能夠歸到基類，并且能夠歸到F和V這兩個最基本的類型。最小元表示函數(shù)影射的開始，也就是尋找對應的語義中的最小語義單位。Chain就是其影射過程，也即對應的語義解釋過程。* 3.ImperativeLanguage:即命令方式語言。Algol-Like語言。該類語言通過各種相對獨立

28、的語句，語句自身是不會直接或間接調用自己，可以通過獨立地對每條語句的解釋來進行語義分析。'DeclarativeLanguage即聲明方式語言。Lisp-Like語言。該類語言使用聲明性語句，語句自身會直接或者間接調用自己，通過對多個變量的映射關系，來最終確認其對應的語義。* 4.個人感覺是正確的。因為如果程序的語義脫離了形式系統(tǒng)，那么程序的語義就不能解釋或者不可理解了。而程序的正確性也不可驗證了。5 .參考老師樣題。6 .參考老師樣題。7 .參考課本P50。數(shù)據不同，最后結果為（式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.程序的執(zhí)行就是對機器的操作，即由一種狀態(tài)轉換到另外一種狀態(tài)。程序狀態(tài)：是程序真實的狀態(tài)，與機器無關。機器狀態(tài)：機器狀態(tài)反映了程序狀態(tài)。5.輸入即x=2,y=2,z=2輸出要符合x=2*yAy=4*z,可能的輸出為x=16y=8z=2由于這題沒說中間的結果，z的值可以改變，所以答案也可以是反正滿足最后的條件就可以了。8,4,1。甚至24,12,3都可以。6.狀態(tài)是由(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.類似于作業(yè)?？赏瞥鯮efutation。下面是作業(yè)的解答。:-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