程序与递归组合抽象与构造练习题答案解析

第3章程序和递归：组合、抽象和结构1、相关计算系统和程序，下列说法正确是_____。(A)只有用计算机语言编写出来代码才是程序，其它全部不能称其为程序；(B)结构计算系统是不需要程序，程序对结构计算系统没有什么帮助；(C)任何系统全部需要程序，只是这个程序是由人来实施还是由机器自动实施，能够由机器自动实施程序系统被称为计算系统； (D)程序是用户表示随使用者目标不一样而千变万化复杂动作，不是使用者实现而是需要计算系统事先完成。答案：C解释：本题考查程序，计算系统等概念；（A）程序=基础动作指令一个组合或实施序列,用以实现复杂动作，只用计算机语言编写出来代码称为程序，这个概念太狭隘了，A错误；（B）计算系统一部分是由程序组成，所以B错误；（C）计算系统=基础动作+指令+程序实施机构，任何系统全部需要系统，C完全正确；（D）程序=基础动作指令一个组合或实施序列,用以实现复杂动作，并不是由用户表示，随使用者不一样而千变万化复杂动作。所以D是错；具体内容参考第三章视频之“程序作用和本质”及第三章课件。2、相关程序，下列说法不正确是_____。(A)“程序”是由人编写、以通知计算系统实现人所期望复杂动作；(B)“程序”能够由系统自动解释实施，也能够由人解释由系统实施；(C)一般人是极难了解“程序”，其也和“程序”无关； (D)“程序”几乎和每个人全部相关系，如自动售票系统、自动取款机等。答案：C解释：本题考查程序概念；程序=基础动作指令一个组合或实施序列,用以实现复杂动作，所以A,B，D全部是正确；C说一般人极难了解程序，这显然是错误。所以选C； 具体内容参考第三章视频之“程序作用和本质”及第三章课件。3、相关程序，下列说法不正确是_____。(A)程序基础特征是复合、抽象和结构；(B)复合就是对简单元素多种组合，立即一个(些)元素代入到另一个(些)元素中；(C)抽象是对多种元素组合进行命名，并将该名字用于更复杂组合结构中； (D)程序就是经过组合、抽象、再组合等结构出来； (E)上述说法有不正确。答案：E解释：本题考查程序概念；（A）程序特征即是：组合-抽象-结构，所以A正确；（B）复合即是将简单基础动作指令组合起来，实现复杂动作。B正确；（C）抽象：将常常使用、可由低层次系统实现部分复杂动作，进行命名，以作为高层次系统指令被使用，C正确；（D）经过前面三个选项可知，程序就是经过组合，抽象，再组合这么结构出来。综上可知E不正确。具体内容参考第三章视频之“程序作用和本质”及第三章课件。4、通常而言，设计和实现一个计算系统，需要设计和实现_____。(A)基础动作和程序；(B)基础动作和控制基础动作指令；(C)基础动作、控制基础动作指令和一个程序实施机构； (D)基础动作、控制基础动作指令和程序。答案：C解释：本题考查计算系统概念；计算系统=基础动作+指令+程序实施机构，所以ABC全部描述不完整，只有C正确；具体内容参考第三章视频之“程序作用和本质”及第三章课件。5、通常而言，一个较高抽象层次计算系统是能够这么实现，即_____。(A)将较低抽象层次反复性组合，命名为较高抽象层次指令；(B)利用较高抽象层次指令进行复合、抽象和结构，即形成高抽象层次程序；(C)高抽象层次程序经过其程序实施机构解释为高抽象层次指令及其操作次序； (D)高抽象层次指令被替换为低抽象层次程序，再由低抽象层次程序实施机构解释并实施。 (E)上述A-D全部。答案：E解释：本题考查计算系统概念；（A）抽象：将常常使用、可由低层次系统实现部分复杂动作，进行命名，以作为高层次系统指令被使用，所以，A正确；（B）程序本身即是复合，抽象，结构过程，B正确；（C）（D）描述全部完全正确；所以总而言之，应该选E；具体内容参考第三章视频之“程序作用和本质”及第三章课件。6、熟悉下列运算组合式(前缀表示式)，其中结果为56是_____。(A)(*7(+52))；(B) (*(+53)(+52))；(C)(+20(+66))； (D)(-(*98)(-202))。答案：B解释：本题考查基础运算组合式结构和计算，尤其是嵌套运算组合式计算对于一个前缀表示式求值而言，首先要从右至左扫描表示式，从右边第一个字符开始判定，假如目前字符是数字则一直到数字串末尾再统计下来，假如是运算符，则将右边离得最近两个“数字串”作对应运算，以此作为一个新“数字串”并统计下来。一直扫描到表示式最左端时，最终运算值也就是表示式值。所以，（A）中缀表示式7*（2+5）=49；（B）（3+5）*（2+5）=56；所以选B；（C）20+（6+6）=32；（D）（9*8）-（20-2）=54；所以答案选B；具体内容参考第三章视频之“程序结构示例(I)”及第三章课件。7、对于计算式，其正确运算组合式(前缀表示法)为_____。(A)(/(+10/20+84)(+*36*82))；(B) ((10+(20/(8+4)))/((3*6)+(8*2)))；(C)(/(+10(/20(+84)))(+(*36)(*82)))； (D)(/(/20(+10(+84)))(*(+36)(+82)))。答案：C解释：本题考查运算组合式书写和结构对于一个前缀表示式求值而言，首先要从右至左扫描表示式，从右边第一个字符开始判定，假如目前字符是数字则一直到数字串末尾再统计下来，假如是运算符，则将右边离得最近两个“数字串”作对应运算，以此作为一个新“数字串”并统计下来。一直扫描到表示式最左端时，最终运算值也就是表示式值。我们能够将答案中四个选项全部转化成中缀表示式，发觉C完全符合题意；具体内容参考第三章视频之“程序结构示例(I)”及第三章课件。8、请用define运算，定义一个过程实现计算a3，其正确定义过程为_____。(A)(definecubea(*aaa))；(B) (define(cubex)(*xxx))；(C)(define(cubea(*aaa)))； (D)(define(cubea)(*xxx)))。答案：B解释：本题考查新运算符(即过程)定义（cubex）中，cube是新运算符，x是形式参数，使用时将被实际参数替换。（*xxx）是过程体，用于表示新运算符具体计算规则，其为相关形式参数x一个计算组合。所以总而言之应选择B，满足条件；具体内容参考第三章视频之“程序结构示例(II)”及第三章课件。9、已知一个新运算被定义为(define(newCalcxy)(*(+x1)(*y2)))，问newCalc能够完成计算功效为_____。-(A)(x+1)+2y；(B) (x+1)*2y；(C)(x+1)+(y+2)； (D)(x+1)*(y+2)。答案：B解释：本题考查新运算符(即过程)定义此题是定义了个一个相关x和y心运算newCale，后面(*(+x1)(*y2))转化成中缀表示式：即为(x+1)*2y，所以选B；具体内容参考第三章视频之“程序结构示例(II)”及第三章课件。10、已知一个新运算被定义为(define(newCalcxy)(*(+x1)(*y2)))，问正确使用了newCalc并得到正确结果为_____。(A)((newCalc)(45))，其结果为50；(B) (newCalc4)，其结果为40；(C)(newCalc45)，其结果为50； (D)(newCalc23)，其结果为21。答案：C解释：本题考评新运算符(即过程)定义和使用。本题定义新运算是(x+1)*(y*2)。(A)和(B)使用方法不正确；(C)将x=4，y=5代入新运算得50，所以是正确；(D)将x=2，y=3代入新运算得18，是错误。具体内容请参考第三章课件之“程序结构示例”及第三章课件。11、已知一个新运算被定义为(define(newCalcxy)(*(+x1)(+y1)))，问(newCalc(newCalc(newCalc11)2)3)计算结果为_____。(A)6；(B)13；(C)64；(D)24。答案：C解释：本题考评新运算符(即过程)定义和嵌套使用。本题定义新运算是(x+1)*(y+1)。先计算最里层(newCalc11)=(1+1)*(1+1)=4；再计算(newCalc(newCalc11)2)=(newCalc42)=(4+1)*(2+1)=15；最终计算(newCalc(newCalc(newCalc11)2)3)=(newCalc153)=(15+1)*(3+1)=64，即最终止果是64，所以(C)是正确。具体内容请参考第三章课件之“程序结构示例”及第三章课件。12、已知一个新运算被定义为(define(newCalcxy)(*(+x1)(+y1)))，问(newCalc(newCalc(newCalc11)(newCalc11))(newCalc11))计算结果为_____。(A)1；(B)64；(C)130；(D)8。答案：C解释：本题考评新运算符(即过程)定义和嵌套使用。本题定义新运算是(x+1)*(y+1)。先计算(newCalc11)=(1+1)*(1+1)=4；再计算(newCalc(newCalc11)(newCalc11))=(newCalc44)=(4+1)*(4+1)=25；最终计算(newCalc(newCalc(newCalc11)(newCalc11))(newCalc11))=(newCalc254)=(25+1)*(4+1)=130，即最终止果是130，所以(C)是正确。具体内容请参考第三章课件之“程序结构示例”及第三章课件。13、已知一个运算被定义为(define(firstCalcx)(*xx))，在其基础上深入定义新运算secondCalc为x2+y2+z2，下列运算组合式书写正确是_____。(A)(definesecondCalc(+(firstCalcx)(firstCalcy)(firstCalcz)))；(B) (define(secondCalcxyz)(+firstCalcxyz))；(C)(define(secondCalcxyz)(+(firstCalcx)(firstCalcy)(firstCalcz)))； (D)(definesecondCalcxyz(+(firstCalcx)(firstCalcy)(firstCalcz)))。 (E)(define(secondCalcxyz)(+(firstCalcx)(firstCalcx)(firstCalcx)))。答案：C解释：本题考评新运算符(即过程)定义，和形式参数使用。本题首先定义新运算是(firstCalcx)=x2，最终要定义新运算是x2+y2+z2，只需要将(firstCalcx)、(firstCalcy)和(firstCalcz)这三项加起来即可。其中(A)选项定义新运算符secondCalc后没有跟参数，错误；(B)选项调用运算(firstCalcx)时错误；(C)选项正确；(D)选项secondCalcxyz没有加括号；(E)选项后面运算是x2+x2+x2，错误。具体内容请参考第三章课件之“程序结构示例”及第三章课件。14、已知一个运算被定义为(define(firstCalcx)(*xx))，在其基础上深入定义新运算为(define(secondCalcx)(firstCalc(firstCalc(firstCalcx))))，问secondCalc表示运算功效为_____。(A)x*x*x；(B) x2+x2+x2；(C)((x2)2)2； (D)x4。答案：C解释：本题考评新运算符(即过程)定义和嵌套使用。本题首先定义新运算是(firstCalcx)=x2，下面计算深入定义新运算secondCalc，从最里层开始计算(firstCalcx)=x2，然后计算(firstCalc(firstCalcx))=(firstCalcx2)=(x2)2，最终计算(firstCalc(firstCalc(firstCalcx)))=(firstCalc(x2)2)=((x2)2)2，所以(C)选项是正确。具体内容请参考第三章课件之“程序结构示例”及第三章课件。15、用条件运算符定义一个过程。正确定义为_____。(A)(define(fxy)(cond((x>y)(*xxx)) ((x=y)0) ((x<y)(*yyy))))；(B)(define(fxy)(cond((>xy)(*xxx)) ((=xy) 0) ((<xy) (*yyy))))；(C)(define(fxy)(cond((x>y)(x*x*x)) ((x=y)0) ((x<y)(y*y*y))))；(D)(define(fxy)(cond((<xy)(*xxx)) ((=xy) 0) ((>xy) (*yyy))))。答案：B解释：本题考评条件运算符使用及分支处理。(A)选项，条件书写错误，应该用前缀表示法，即运算符在前面；(B)选项正确；(C)选项，条件和表示式全部书写错误，应该用前缀表示法，而选项中用是中缀表示法；(D)选项，条件书写错误，把x>y和x<y写颠倒了。具体内容请参考第三章课件之“程序结构示例”及第三章课件。16、用条件运算符定义一个过程。正确定义为_____。(A)(define(fn)(cond((n<2)1) ((n>1)(n*f(n-1)))(B)(define(fn)(cond((<n2)1) ((>n1) (*n(f(-n1))))))；(C)(define(fn)(cond((n<2)1) ((n>1)(n*f(n-1)))))；(D)(define(fn)(cond((<n2)1) ((>n1) (*n(fn-1)))))。答案：B解释：本题考评递归过程定义。(A)选项，首先条件书写错误，其次n>1时，表示式书写错误，最终右括号数目不够；(B)选项正确；(C)选项，首先条件书写错误，其次n>1时，表示式书写错误；(D)选项，调用f(n-1)时书写错误。具体内容请参考第三章视频之“利用递归和迭代”及第三章课件。17、若要表示从1计算到n运算组合式，(*…(*(*(*(*11)2)3)4)…n)定义一个过程。正确定义为_____。(A)(define(fproductcountermax-count)(f(*counterproduct)(+counter1)max-count))；(B)(define(fproductcountermax-count)(cond((>countermax-count)product)((<=countermax-count)(f(counter*product)(counter+1)max-count))))；(C)(define(fproductcountermax-count)(cond((>countermax-count)product)((<=countermax-count)(f(*counterproduct)(+counter1)max-count))))；(D)(define(fproductcountermax-count)(cond((>countermax-count)product)((<=countermax-count)(fproductcountermax-count))))；答案：C解释：本题考评迭代过程定义。本题需要计算1*2*3*---*n，选项中product表示每次迭代结果，counter表示此次迭代要相乘数，max-count即n，在每次迭代中，要把product*counter赋给product，把counter+1赋给counter。(A)选项，没有结束条件，会一直迭代下去；(B)选项，(f(counter*product)(counter+1)max-count)没有用前缀表示法；(C)选项正确，计算1*2*3*---*n即(define(f11n))；(D)选项，当counter<=max-count时，表示式错误。具体内容请参考第三章视频之“利用递归和迭代”及第三章课件。18、相关原始递归函数了解，下列说法不正确是_____。(A)“复合”即是将一组函数g1,g2,…,gn作为参数代入到另一函数f(x1,x2,…,xn)中，即n个函数g1,g2,…,gn被组合到了一起，是按函数f形式进行组合。(B)“原始递归”即是要定义h(0),h(1),…,h(n),h(n+1)，其中h(0)需要直接给出，而h(n+1)需要用h(n)进行定义，即h(n+1)是将h(n)和n复合在一起。(C)复合是结构新函数一个手段，原始递归也是结构新函数一个手段； (D)递归函数是描述程序组合和结构问题一个数学形式。 (E)上述说法有不正确。答案：E解释：本题考评对原始递归函数了解。(A)、(B)、(C)和(D)说法全部是正确，所以(E)选项错误。具体内容请参考第三章视频之“原始递归”及第三章课件。19、按原始递归定义，h是由f和g递归地结构出来。假设已知h(n)=n!，请给出结构hf和g函数。正确是_____。(A)f()是常数为1函数；g(x1,x2)=x1*x2。(B)f()是常数为1函数；g(x1,x2)=x1*(x2+1)。(C)f()是常数为1函数；g(x1,x2)=(x1+1)*(x2+1)。(D)f()是常数为1函数；g(x1)=n*(x1)。答案：B解释：本题考评原始递归定义,当f()是常数为1函数，若g(x1,x2)=x1*x2。则h(n)=1；若g(x1,x2)=x1*(x2+1)。则h(n)=n!；若g(x1,x2)=(x1+1)*(x2+1)。递归从2开始；若g(x1)=n*(x1)。h(n)为NN次方；所以B选项正确。具体内容请参考“递归概念’及第三章课件。20、已知f(x)=x，g(x1,x2,x3)=x1+x2+x3,其中x,x1,x2,x3均为自然数，新函数h可递归结构以下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，请按递归式进行计算下列式子，正确是_____。(A)h(1，x)=x；(B)h(2，x)=2x；(C)h(3，x)=3x+1；(D)h(4，x)=5x+6；(E)上述全部不正确。答案：D解释：本题考评递归。h(0,x)=f(x)=xh(1,x)=h(S(0),x)=g(h(0,x),0,x)=g(f(x),0,x)=f(x)+0+x=2xh(2,x)=h(S(1),x)=g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2x,1,x)=3x+1h(3,x)=h(S(2),x)=g(h(2,x),2,x)=g(g(h(1,x),1,x),2,x)=g(g(g(h(0,x),0,x),1,x),2,x) =…=4x+3h(4，x)=h(S(3),X)=g(h(3,X),3,x)=......=5x+6;所以选D；具体内容请参考“原始递归函数结构’及第三章课件。21、已知f(x)=5，g(x1,x2,x3)=x1,其中x,x1,x2,x3均为自然数，新函数h可递归结构以下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，请按递归式进行计算下列式子，正确是_____。(A)h(1，x)=5；(B)h(2，x)=5+x；(C)h(3，x)=5+2x；(D)h(4，x)=5+3x；(E)上述全部不正确。答案：A解释：本题考评递归。h(1,x)=h(S(0),x)=g(h(0,x),0,x)=g(f(x),0,x)=f(x)=5；h(2,x)=h(S(1),x)=g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(5,1,x)=5；h(3,x)=h(S(2),x)=g(h(2,x),2,x)=g(g(h(1,x),1,x),2,x)=g(g(g(h(0,x),0,x),1,x),2,x) =…=5；h(4，x)=h(3,x)=...=5;所以选A；具体内容请参考“原始递归函数结构’及第三章课件。22、已知f(x)=x，g(x1,x2,x3)=x1*(x2+1),其中x,x1,x2,x3均为自然数，新函数h可递归结构以下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，请按递归式进行计算下列式子，不正确是_____。(A)h(1，x)=x；(B)h(2，x)=2x；(C)h(3，x)=6x；(D)h(4，x)=12x；答案：D解释：本题考评递归。h(0,x)=f(x)；h(1，x)=h(S(0),x)=g(h(0,x),0,x)=f(x)=x；h(2，x)=h(S(1),x)=g(h(1,x),1,x)=h(1,x)*2=2x； h(3，x)=h(S(2),x)=g(h(2,x),2,x)=h(2,x)*3=6x； h(4，x)=h(S(3),x)=g(h(3,x),3,x)=h(3,x)*4=24x；所以选D；具体内容请参考“原始递归函数结构’及第三章课件。23、相关“递归”，下列说法不正确是_____。(A)“递归”源自于数学上递推式和数学归纳法。(B)“递归”和递推式一样，全部是自递推基础计算起，由前项(第n-1项)计算后项(第n项)，直至最终止果取得。(C)“递归”是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再以前项计算后项获取结果，直至最终止果取得； (D)“递归”是由前n-1项计算第n项一个方法。答案：B解释：本题考评递归相关内容。递归”源自于数学上递推式和数学归，是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再以前项计算后项获取结果，直至最终止果取得，是由前n-1项计算第n项一个方法。所以选B；具体内容请参考“递归概念”及第三章课件。24、相关“递归”，下列说法不正确是_____。(A)能够利用“递归”进行含有自相同性无限反复事物定义。(B)能够利用“递归”进行含有自反复性无限反复动作实施，即“递归计算”或“递归实施”。(C)能够利用“递归”进行含有自相同性无限反复规则算法结构； (D)上述说法不全正确。答案：D解释：本题考评递归概念内容。递归”能够进行含有自相同性无限反复事物定义，进行含有自反复性无限反复动作实施，即“递归计算”或“递归实施”，进行含有自相同性无限反复规则算法结构。具体内容请参考“递归概念”及第三章课件。25、相关递归定义函数，下列说法正确是_____。(A)递归定义函数一定是“递归计算”；(B)递归定义函数一定是“迭代计算”；(C)有些递归定义函数能够“迭代计算”，有些递归定义函数则必需“递归计算”； (D)通常能够“迭代计算”函数，一定能够“递归计算”，通常能够“递归计算”函数，也一定能够“迭代计算”。答案：C解释：本题考评递归和迭代，有些递归定义函数能够“迭代计算”，有些递归定义函数则必需“递归计算”所以选C。具体内容请参考“递归和迭代概念”及第三章课件。26、用递归是能够定义语言。如表述命题逻辑一个语言能够以下定义：(1)一个命题是其值为真或假一个判定语句；(2)假如X是一个命题，Y也是一个命题，则XandY，XorY,notX也是一个命题；(3)假如X是一个命题，则(X)也是一个命题，括号内命题运算优先；(4)命题由以上方法结构。若X，Y，Z，M等均是一个命题，问不符合上述递归定义语句是_____。(A)X；(B)(XandYnotZ)；(C)(X)； (D)((XandY)or(notZ))and(notM)。答案：B解释：本题考评递归定义。由前n项或第n项定义第n+1项；由低阶f(k)且k<n，来结构高阶f(n+1)----实施：由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终止果；所以选B。具体内容请参考“递归概念”及第三章课件。27、递归计算是关键实施手段。比如一个形式阿克曼函数以下所表示：任何一个A(m,n)全部能够递归地进行计算，比如A(1,2)递归计算过程以下所表示：A(1,2)=A(0,A(1,1))=A(0,A(0,A(1,0)))=A(0,A(0,A(0,1)))=A(0,A(0,2))=A(0,3)=4。请你按上述方法递归计算下列项，并判定，计算结果正确是_____。(A)A(1,8)=9；(B)A(2,0)=2；(C)A(2,1)=4； (D)A(1,n)=n+2。答案：D解释：本题考查对程序和递归综合了解，以正面叙述为主，便于学生复习A(1,n)=A(0,A(1,n-1))=A(0.<…代入前式计算过程>)=A(0,n+1)=n+2。所以A(1,8)=10；A(2，0)=A(1，1)=3；A(2,1)=A(1，A(2，0))=A(1，A(1，1))=A(1，A(0，A(1，0))) =A(1，A(0，A(0，1)))=A(1