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

1、第3章程序与递归：组合、抽象与构造1、关于计算系统与程序，下列说确的是 。(A)只有用计算机语言编写出来的代码才是程序，其他都不能称其为程序；(B)构造计算系统是不需要程序的，程序对构造计算系统没有什么帮助；(C)任何系统都需要程序，只是这个程序是由人来执行还是由机器自动执行，可以由机器自动执行程序的系统被称为计算系统；(D)程序是用户表达的随使用者目的不同而千变万化的复杂动作，不是使用者实现的而是需要计算系统事先完成的。答案：C 解释:本题考查程序，计算系统等的概念；(A)程序=基本动作指令的一个组合或执行序列，用以实现复杂的动作，只用计算机语言 编写出来的代码称为程序，这个概念太狭隘了，A

2、错误；(B)计算系统的一部分是由程序组成的， 所以B错误；(C)计算系统=基本动作+指令+程序执行机构，任何系统都需要系统， C完 全正确；(D)程序=基本动作指令的一个组合或执行序列，用以实现复杂的动作，并不是由用 户表达的，随使用者的不同而千变万化的复杂动作。所以D是错的；具体容参考第三章视频之“程序的作用和本质”及第三章课件。2、关于程序，下列说法不正确的是 。(A) “程序”是由人编写的、以告知计算系统实现人所期望的复杂动作；(B) “程序”可以由系统自动解释执行，也可以由人解释由系统执行；(C)普通人是很难理解“程序”的，其也和“程序”无关；(D) “程序”几乎和每个人都有关系，如自

3、动售票系统、自动取款机等。答案：C 解释:本题考查程序的概念；程序=基本动作指令的一个组合或执行序列，用以实现复杂的动作，所以A,B, D都是正确 的；C说普通人很难理解程序，这显然是错误的。所以选 C;具体容参考第三章视频之“程序的作用和本质”及第三章课件。3、关于程序，下列说法不正确的是 。(A)程序的基本特征是复合、抽象与构造；(B)复合就是对简单元素的各种组合，即将一个(些)元素代入到另一个(些)元素中;(C)抽象是对各种元素的组合进行命名，并将该名字用于更复杂的组合构造中；(D)程序就是通过组合、抽象、再组合等构造出来的；(E)上述说法有不正确的。答案：E解释：本题考查程序的概念；(

4、A)程序的特征即是：组合-抽象-构造，所以A正确；(B)复合即是将简单的基本动作指 令组合起来，实现复杂动作。B正确；(C)抽象：将经常使用的、可由低层次系统实现的一些复 杂动作，进行命名，以作为高层次系统的指令被使用，C正确；(D)通过前面三个选项可知，程序就是通过组合，抽象，再组合这样构造出来的。综上可知E不正确。具体容参考第三章视频之“程序的作用和本质”及第三章课件。4、一般而言，设计和实现一个计算系统，需要设计和实现 。(A)基本动作和程序；(B)基本动作和控制基本动作的指令；(C)基本动作、控制基本动作的指令和一个程序执行机构；(D)基本动作、控制基本动作的指令和程序。答案：C解释：

5、本题考查计算系统的概念；计算系统=基本动作+指令+程序执行机构，所以ABC都描述不完整，只有C正确;具体容参考第三章视频之“程序的作用和本质”及第三章课件。5、一般而言，一个较高抽象层次的计算系统是可以这样实现的，即 。(A)将较低抽象层次的重复性组合，命名为较高抽象层次的指令；(B)利用较高抽象层次的指令进行复合、抽象与构造，即形成高抽象层次的程序；(C)高抽象层次的程序通过其程序执行机构解释为高抽象层次的指令及其操作次序；(D)高抽象层次的指令被替换为低抽象层次的程序，再由低抽象层次的程序执行机构解释并执 行。(E)上述A-D全部。答案：E解释：本题考查计算系统的概念；(A)抽象：将经常使

6、用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层 次系统的指令被使用，所以，A正确；(B)程序本身即是复合，抽象，构造的过程，B正确；(C) (D)的描述都完全正确；所以综上所述，应该选 E;具体容参考第三章视频之“程序的作用和本质”及第三章课件。6、熟悉下列运算组合式(前缀表达式)，其中结果为56的是。(A) (*7(+5 2);(B) (*(+5 3)(+ 52);(C) (+20(+ 66);(D) (-(*9 8)(- 202)。答案：B解释：本题考查基本运算组合式的构造与计算，尤其是嵌套的运算组合式的计算对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个

7、字符开始判断， 如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两 个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最 左端时，最后运算的值也就是表达式的值。所以， (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)”及第三章课件。107、对于计算式208二，其正确的运算组合式(前缀表示法)为3*6 8*2(A) (B) (C)

8、(D)(/ (+ (10 + (/ (+ (/ (/10 / (20 / 10 (/20 (+20(82010(+(+8 4) (+*36*4) / (3 * 6) + (8 * 2);8 4)(+(*36)8 4)(*(+36)8 2 )；(* 8 2);(+ 8 2)o答案：C解释：本题考查运算组合式的书写与构造对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断, 如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两 个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最 左端时，最后运算的值也就是

9、表达式的值。我们可以将答案中的四个选项都转化成中缀表达式， 发现C完全符合题意；具体容参考第三章视频之“程序构造示例（I）”及第三章课件。8、请用define运算，定义一个过程实现计算 a3,其正确定义的过程为 。(A)(define cube a (*a a a);(B)(define (cube x) (*x xx) ；(C)(define (cube a (*a aa)；(D)(define (cube a) (*x x x)。答案：B解释：本题考查新运算符（即过程）的定义（cube x）中，cube是新运算符，x是形式参数，使用时将被实际参数替代。（*x x x）是过 程体，用于表示新

10、运算符的具体计算规则，其为关于形式参数 x的一种计算组合。所以综上所述应选择B,满足条件；具体容参考第三章视频之“程序构造示例（II）”及第三章课件。9、已知一个新运算被定义为（define （newCalc x y） （* （+ x 1） （* y 2）,问 newCalc 可以完成的计算功能为 O -(A) (x+1)+2y;(B) (x+1)*2y;(C) (x+1) +(y+2);(D) (x+1)*(y+2)。答案：B解释：本题考查新运算符（即过程）的定义此题是定义了个一个有关x和y的心运算newCale,后面（* （+ x 1） （* y 2）转化成中 缀表达式：即为（x+1）*2

11、y,所以选B;具体容参考第三章视频之“程序构造示例（II）”及第三章课件。10、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (* y 2),问正确使用 了 newCalc并得到正确结果的为。(A) (newCalc) (4 5),其结果为 50;(B) (newCalc 4),其结果为 40;(C) (newCalc 4 5),其结果为 50;(D) (newCalc 2 3),其结果为 21。答案：C解释：本题考核新运算符(即过程)的定义和使用。本题定义的新运算是(x+1)*(y*2)。(A)和(B)使用方法不正确；(C)将x=4, y=5代入新运

12、算得 50,所以是正确的；(D)将x=2, y=3代入新运算得18,是错误的。具体容请参考第三章课件之“程序构造示例”及第三章课件。11、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1),问(newCalc (newCalc (newCalc 1 1) 2) 3)的计算结果为。(A) 6 ; (B) 13; (C) 64; (D) 24。答案：C解释：本题考核新运算符(即过程)的定义和嵌套使用。本题定义的新运算是(x+1)*(y+1)。先计算最里层的(newCalc 1 1)= (1+1)*(1+1)=4;再计算 (newCalc (new

13、Calc 1 1) 2)= (newCalc 4 2) = (4+1)*(2+1)=15;最后计算(newCalc (newCalc (newCalc 1 1) 2) 3)= (newCalc 15 3) = (15+1)*(3+1)=64,即最终结果是 64,所以(C)是正确的。具体容请参考第三章课件之“程序构造示例”及第三章课件。12、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1),问(newCalc (newCalc (newCalc 11) (newCalc 1 1) (newCalc 1 1)的计算结果为。(A) 1 ; (B)

14、 64; (C) 130; (D) 8。答案：C解释：本题考核新运算符(即过程)的定义和嵌套使用。本题定义的新运算是(x+1)*(y+1)。先计算(newCalc 1 1)= (1+1)*(1+1)=4;再计算(newCalc (newCalc 1 1) (newCalc 1 1)= (newCalc 4 4) = (4+1)*(4+1)=25;最后计算(newCalc (newCalc (newCalc 1 1) (newCalc 1 1) (newCalc 1 1)=(newCalc 25 4) = (25+1)*(4+1)=130,即最终结 果是130,所以(C)是正确的。具体容请参考第

15、三章课件之“程序构造示例”及第三章课件。13、已知一个运算被定义为(define (firstCalc x) (* x x),在其基础上进一步定义新运算 secondCalc为x2+y2+z2,下列运算组合式书写正确的是。(A) (define secondCalc (+(firstCalc x)(firstCalc y)(firstCalc z)；(B) (define (secondCalc x y z)(+firstCalcxy z);(C) (define (secondCalc x y z)(+(firstCalcx)(firstCalcy)(firstCalcz)；(D) (def

16、ine secondCalc x y z (+ (firstCalc x) (firstCalc y) (firstCalc z)。(E) (define (secondCalc x y z)(+(firstCalcx)(firstCalcx)(firstCalcx)。答案：C解释：本题考核新运算符(即过程)的定义，以及形式参数的使用。本题首先定义的新运算是(firstCalc x) = x2 ,最终要定义的新运算是 x2+y2+z2 ,只需要将 (firstCalc x)、 (firstCalc y)和(firstCalc z)这三项加起来即可。其中(A)选项定义的新运算符 secondCa

17、lc后没有跟参数，错误；(B)选项调用运算(firstCalc x)时错误；(C)选项正确；(D)选项 secondCalc x y z没有加括号；(E)选项后面白运算是x2+x2+x2,错误。具体容请参考第三章课件之“程序构造示例”及第三章课件。14、已知一个运算被定义为(define (firstCalc x) (* x x),在其基础上进一步定义新运算为 (define (secondCalc x) (firstCalc (firstCalc (firstCalc x),问 secondCalc表达的运算功能 为。(A) x*x*x ;(B) x2+x2+x2；(C) (x2)2)2；(

18、D) x4。答案：C解释：本题考核新运算符(即过程)的定义和嵌套使用。本题首先定义的新运算是(firstCalc x) = x2 ,下面计算进一步定义的新运算 secondCalc从 最里层开始计算(firstCalc x) = x2 ,然后计算(firstCalc (firstCalc x) = (firstCalc x2) = (x2)2,最 后计算(firstCalc (firstCalc (firstCalc x) = (firstCalc (x2)2) = (x2)2)2,所以(C)选项是正确的。具体容请参考第三章课件之“程序构造示例”及第三章课件。3 yx 1fxy15、用条件运算

19、符定义一个过程f(x,y)0if xy。正确的定义为,y3if xy(A) (define (f x y)(B) (define (f x y)(C) (define (f x y)(D) (define (f x y)(cond (x>y) (* x x x)(x=y ) 0)(x<y ) (* y y y);(cond (> x y ) (* x x x)(=x y )0)(< x y )(* y y y);(cond (x>y) (x*x*x)(x=y ) 0)(x<y ) (y*y*y) )(cond (< x y ) (* x x x)(=x

20、 y )0)(> x y )(* y y y)。(A) (define (f n) (cond(B) (define (f n) (cond(C) (define (f n) (cond(D) (define (f n) (cond答案：B解释：本题考核条件运算符的使用及分支处理。(A)选项，条件书写错误，应该用前缀表示法，即运算符在前面；(B)选项正确；(C)选项，条件和表达式都书写错误，应该用前缀表示法，而选项中用的是中缀表示法；(D)选项，条件书写 错误，把x>y和x<y写颠倒了。具体容请参考第三章课件之“程序构造示例”及第三章课件。1 if n 216、用条件运算符定

21、义一个过程 n!。正确的定义为n* (n 1)! if n 1(n<2 ) 1)(n>1) (n* f(n-1)(< n 2 ) 1)(> n 1 )(* n (f (- n 1);(n<2) 1)(n>1 ) (n* f(n-1);(< n 2 ) 1)(> n 1 )(* n (f n-1)。答案：B解释：本题考核递归过程的定义。(A)选项，首先条件书写错误，其次 n>1时，表达式书写错误，最后右括号数目不够；(B)选项正确；(C)选项，首先条件书写错误，其次 n>1时，表达式书写错误；(D)选项，调用f(n-1) 时书写错误。具

22、体容请参考第三章视频之“运用递归和迭代”及第三章课件。17、若要表达从1计算到n的运算组合式，(*(* (* (* (* 1 1) 2) 3) 4)n) 定义一个过程。正确的定义为 。(A) (define (f product counter max-count)(f (* counter product) (+ counter 1) max-count );(B) (define (f product counter max-count) (cond (> counter max-count) product) (<= counter max-count) (f (counte

23、r*product) (counter+ 1) max-count );(C) (define (f product counter max-count) (cond (> counter max-count) product) (<= counter max-count) (f (* counter product) (+ counter 1) max-count );(D) (define (f product counter max-count)(cond (> counter max-count) product)(<= counter max-count) (

24、f product counter max-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 IP (define (f 1 1 n); (

25、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)复合是构造新函数的一种手段，原始递归也是构造新函数的一种手段；

26、(D)递归函数是描述程序组合与构造问题的一种数学形式。(E)上述说法有不正确的。答案：E解释：本题考核对原始递归函数的理解。(A)、(B)、(C)和(D)的说法都是正确的，所以(E)选项错误。具体容请参考第三章视频之“原始递归”及第三章课件。19、按原始递归的定义，h是由f和g递归地构造出来的。假设已知 h(n) = n!,请给出构造h的f 和g的函数。正确的是。(A) f()是常数为 1 的函数；g(x1,x2) = X1* X2。(B) f()是常数为 1 的函数；g(x1,X2) = X1* (X2+1)O(C) f()是常数为 1 的函数；g(X1,X2) = (X1+1)*(X2+1

27、) o(D) f()是常数为1的函数；g(X1) = n * (X1)。答案：B解释：本题考核原始递归的定义，当f()是常数为1的函数，若g(X1,X2) = x1* x2。则h(n) = 1;若g(X1,X2) =x1* (x2+1)。贝U h(n) = n!;若 g(x1,x2) = (x1+1)*(x2+1)。递归从 2 开始；若 g(x1) = n * (x1)。h(n)为 N的N次方；所以B选项正确。具体容请参考“递归的概念及第三章课件。20、已知f(x)=x , g(X1,X2,X3)=X1+X2+X3,其中X,X1,X2,X3均为自然数，新函数 h可递归的构造如下： h(0,x)

28、 = 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)上述都不正确。解释:本题考核递归。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

29、(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)

30、= 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)=.=

31、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;解释:本题考核递归。h(0,x) = f(x); h(1, x) =h(S(0), x)=g(h(0,x),0,x)=f(x)=x ;h(2,

32、 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项)代入，直到递归基

33、础获取结果，再从前项 计算后项获取结果，直至最终结果的获得；(D) “递归”是由前n-1项计算第n项的一种方法。答案：B解释：本题考核递归相关容。递归”源自于数学上的递推式和数学归， 是自后项(即第n项)向前项(第n-1项)代入，直到递 归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得，是由前 n-1项计算第n项 的一种方法。所以选B;24、关于“递归”(A)可以利用(B)可以利用(C)可以利用,下列说法不正确的是具体容请参考“递归的概念”及第三章课件。“递归”进行具有自相似性无限重复事物的定义。“递归”进行具有自重复性无限重复动作的执行， 即“递归计算”或“递归执行”。“递归”进

34、行具有自相似性无限重复规则的算法的构造；(D)上述说法不全正确。答案：D解释：本题考核递归概念容。递归”可以进行具有自相似性无限重复事物的定义，进行具有自重复 性无限重复动作的执行，即“递归计算”或“递归执行”，进行具有自相似性无限重复规则的算法 的构造。具体容请参考“递归的概念”及第三章课件。25、关于递归定义的函数，下列说确的是 。(A)递归定义的函数一定是“递归计算”的；(B)递归定义的函数一定是“迭代计算”的；(C)有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”；(D)凡是可以“迭代计算”的函数，一定可以“递归计算”，凡是可以“递归计算”的函数, 也一定可以“

35、迭代计算”。答案：C 解释:本题考核递归与迭代，有些递归定义的函数可以“迭代计算” ，有些递归定义的函数则必须“递归计算”所以选Co具体容请参考“递归与迭代概念”及第三章课件。26、用递归是可以定义语言的。如表述命题逻辑的一种语言可以如下定义：(1) 一个命题是其值为真或假的一个判断语句；(2)如果X是一个命题，Y也是一个命题，则 X and Y, X or Y, not X也是一个命题；(3)如果X是一个命题，则(X)也是一个命题，括号的命题运算优先；(4)命题由以上方式构造。若X, Y, Z, M等均是一个命题，问不符合上述递归定义的语句是 。(A) X;(B) ( X and Y not

36、 Z);(C) (X);(D) (X and Y) or (not Z) and (not M)。答案：B 解释:本题考核递归的定义。由前n项或第n项定义第n+1项；由低阶f(k)且k<n ,来构造高阶f(n+1) -执行：由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终结果； 所 以选Bo具体容请参考“递归的概念”及第三章课件。27、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示:n 1右 m 0A( m,n) A(m 1),1)若 n 0A(m 1, A(m, n 1) 若 m,n 0任何一个A(m, n)都可以递归地进行计算，例如 A(1,2)的递归

37、计算过程如下所示：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

38、, 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, A(0 , 2)= A(1 , 3) =A(0 ,A(1 ,2)=A(0,A(0,A(1,1) = A(0, A(0 , A(0, A(1, 0)=A(0,A(0,A(0,A(0,1) = A(0 , A(0 ,A(0 , 2) = A(0,A(0 ,3)=A(0, 4) = 5。所以选D具体容请参考“阿克曼函数”及第三章课件。28、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示:A(1,0) 2A(0, m) 1m 0A(n,0) n 2n 2A(n,m) A(A(n