ImageVerifierCode 换一换
格式:DOC , 页数:11 ,大小:199KB ,
资源ID:678645      下载积分:20 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-678645.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(程序设计理论各年试题参考答案.DOC)为本站会员(国***)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

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

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

2、书。如 用 w 代替。程序设计理论试题 2004 年 01 月 06 日该卷答案基本是一个师兄做的,红色为我补充的部分1. Show that (P(Nat), ) is not a Well-founded Set, but(S|S is a finite subset of Nat, ) is a well-founded set解释:P(Nat)为自然数集合的集合。即 Nat 的 Power Set。取第 1 个集合为 Nat, 第 2 个集合为 Nat-1, 。 。 。,第 n 个集合为 Nat-1,2,.n-1,则可以产生一个 infinite descending sequence

3、(无穷递降序列), 所以(P(Nat), )不是 Well-founded Set. 设 T=S|S is a finite subset of Nat, 若(T, )不是 Well-founded Set,则必然存在一个infinite descending sequence, 设为 a1,a2,an, 则 a1 a2 an , 从而|a1|a2|an|.,因为 ai 属于 T(i=1),即 ai 是一个有限集,所以|ai|是一个有限的自然数, |ai|不能形成一个无限下降的序列,矛盾,所以(T, )是 Well-founded Set.2. Show that for all formul

4、as w1 and w2, the formula w1 w2 and w1 w 2 and logicallyequivalent.证明 w1w2 与 w1w2 逻辑等价,即是要证明|= w1w2 w1w2. 对于任意的Interpretation I, I(w1w2 w1w2)() 等价于 I(w1)()I(w2)() I(w1)()I(w2)(), 因为 w1,w2:Bool, 所以 I(w1)()=true 或者 I(w1)()=false, I(w2)()=true 或者 I(w2)()=false。若 I(w1)()=true, I(w2)()=true, 则 I(w1w2 w1w

5、2)() = (truetrue truetrue)=true;其余三种情况类似地也有 I(w1w2 w1w2)()true.所以|= w1 w2 w1w2, 从而 w1w2 与 w1w2 逻辑等价。*3. Consider evaluation of the logic expressions with only operators goto l1;则定义 wlp(a,p)= ;tnxr,.1如果是条件转移语句,设形式如下所示:l0: if e then goto l else goto l fi;则定义 wlp(a,q)如下: e r 如果 l1=l 且 l1le r 如果 l1l 且 l

6、1=l(ii) 定义 partial correctness 的验证条件 vc(p,a,q)为 p wlp(a,q).令 B 为谓词逻辑的 basis, p,q 为 WFFB 的两个公式,S 是一个 flowchart 程序,对于BL1任意的 Interpretation I, 程序 S 在 Interpretation I 中,对于 p 和 q 是 partial correct 的,当且仅当如果对于 S 中的任意一条路径 a, 都有验证条件 vc(p,a,q) 在 I 中为 valid。#8.Show that the following is a correct inference ru

7、le in Hoare logic using construction sequence in “Inductive Definition of Sets”. What are B and K in this context? And what is the inductively defined set in the context?,() while doS qprrefor all p,q,rWFF B, eQFF B, and SL 2B.设 WFFB 为 well-formed formula 的集合B= x:=tp | pWFFB,xV, tTBtxK= ( (pr, reSr,

8、 (r e)q ) , pwhile e do S od q)|p,q,rWFF B,eQFF B,S L2推导出来的集合是 Hoare calculus 里面 logically valid 的公式集的一个子集。推导过程:P-rreS1rr e-qrwhile e do S1 od r epwhile r do S1 od q程序设计理论试题 2000.1.22(即老师的样题)1. 1-in0,Natat!)(,:,| ,或 者wnfNattfatifSiwi试指出链 S 在 Natw-Natw 上的最小上界。有些人说论域就是 CPO。对于该题,由于Nat,且 (+)(a,b) ()=a+b

9、, *为 Nat2-Nat,且 (*)(a,b) ()=a*b,Bool,且 (,有 =, 且S2 为 a. S;S1 当 (e)()=trueb. S 当 (e)()=false当 S1 为 While e do S od 时,有 =,且S2 为 a. S 当 (e)()=trueb. 当 (e)()=false#9当使用通常解释 I 时,有F(2)= if 2=0 then 1 else 2*F(2-1) fi= if false then 1 else 2*F(1) fi= 2*(if 1=0 then 1 else 1*F(1-1) fi)=2*(if false then 1 els

10、e 1*(F(0) fi)=2*1*(F(0)=2*(if 0=0 then 1 else 0*F(0-1) fi)=2*1=2F(-2)由于不可终止,所以 F(-2)未定义#10Vc(q,(test,loop,upd,test),q)q-wlp(test,loop,upd,test),q)wlp(test,q)=qwlp(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=a (y1+1)2(x=a (y1+1)2rreS1rr-

11、e-qr while e do S1 od r-ep while e do S1 od q(可看书 P153)程序设计理论期末练习题1. 可参考老师样题的第 6 题。*2. 这题很难写。先给个思路:第一要建立一个 well-founded set(自然数集) ,并且需要最小值为 0。然后证明对于 x0,每次的计算都是递减。然后下结论。#3. 参考书本 P50。#4. F(x) Nat)-Nat 的函数,并设为 G。则 G(op) =F(3,x)( F/op)=op(3,4)则 (F.F(3,x)(*)()=3*4=12。可看书 P95。程序设计理论期末考试(99)这年考试题目侧重于概念,与之后

12、几年的题目有很大的区别*1. 问得真直接。不好做。指称语义:定义了基类,然后由基类影射到相应的函数,然后由函数来定义其语义。操作语义:定义了抽象机,然后及其相关操作。由抽象机的运行和状态来反映其语义。异:指称语义表示的语言要比操作语义要多。指称语义重点在指称上,即所对应的函数上。而操作语义的重点在于抽象机的运行及其状态。*2. 使用 CPO 的目的是最终能够归到基类,并且能够归到 F 和 V 这两个最基本的类型。最小元表示函数影射的开始,也就是寻找对应的语义中的最小语义单位。Chain 就是其影射过程,也即对应的语义解释过程。*3. Imperative Language:即命令方式语言。Al

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

14、释 ,(w)()=true,则 为 W 的 Model。9Complete。因为定义了一个,即每个 chain 都存在 lub。这里要提出一个,R +也是 CPO。有人提出链:1.1,1.11,1.111,没有 Lub。其实是有的,。即 1.,9lub10. M(S)=x mod 2.11部分正确性是基于程序对输入有定义下的正确性,即程序对合法的输入是正确的。而完全正确性是需要证明其程序对输入有定义的,即程序对于输入是正确的,并且可以终止的。基于谓词的正确性是证明给定的谓词是正确的。基于公式的正确性是证明公式的守恒。12Partial Correct: i:说明程序是无论有没定义都部分正确。

15、Ii:说明程序是处处都没有定义。Terminate: 程序处处有定义。13. 程序输入是 x=y,输出是 x=y!,所以最后的结果一定是让 x 为 y!,y 在程序中可变(改变以后可以归回原来的值) ,但最后的结果必定要让 x=y!。并且 y 要等于原值才是计算阶乘的程序。14.为了保证每条路径都遍历,即程序的运行情况都可保证。15. (pSq)()=true iffIf (p)()=true and if M(S)() is defined,Then (q)(M(S)()=true.看书 P150。程序设计理论期末考试(2000)1. 想不到其他方法。用定义证明。2. 麻烦。直接证。不写了。

16、3. i:说明程序是处处都没有定义。 ii:说明程序是无论有没定义都部分正确。iii. 同 ii iv.同 iiv. 程序处处有定义。 vi. 说明程序是无论有没定义都可终止。4程序的执行就是对机器的操作,即由一种状态转换到另外一种状态。程序状态:是程序真实的状态,与机器无关。机器状态:机器状态反映了程序状态。5.输入即 x=2,y=2,z=2输出要符合 x=2*y y=4*z,可能的输出为 x=16 y=8 z=2由于这题没说中间的结果,z 的值可以改变,所以答案也可以是 8,4,1。甚至 24,12,3 都可以。反正满足最后的条件就可以了。6状态是由(l1, 1)转换到(l2, 2)(1)

17、2=1x/0(2)2=1x/x+1(3)2=1x,y/y,x(4)定义 l1 下一指令为 l1,再下一指令为 l1.2=1 且l2=l1 if x!=0l2=l1 if x=07.老师样题。8. 1=(begin,3,6,end) wlp:m1 相等 由 continuous 定义可知,相等。相等-Continuous 由 Continuous 定义可知。书 P77。(b)不会做。10.类似于作业。可推出 Refutation。下面是作业的解答。:-f(2,2,x) (3) =(m/2,n/2,y/y1):-f(2,1,y1),f(1,y1,x) (3) =(m/2,n/1,x/y1,y/y2):-f(2,0,y2),f(1,y2,y1),f(1,y1,x) (2) =(m/2,x/y2):-f(1,1,y2),f(1,y2,y1),f(1,y1,x) (3) =(m/1,n/1,x/y2,y/y3)

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。