第3章 程序与递归：组合、抽象与构造

答案是：B 16、用条件运算符定义一个过程

(A) (define (f n) (cond ((n<2 ) 1) ((n>1) (n* f(n-1)) )

(B) (define (f n) (cond ((< n 2 ) 1) ((> n 1 ) (* n (f (- n 1)))) ))； (C) (define (f n) (cond ((n<2) 1) ((n>1 ) (n* f(n-1) )) ))；

(D) (define (f n) (cond ((< n 2 ) 1) ((> n 1 ) (* n (f n-1))) ))。 //本题考查递归过程的定义

答案是：B 。正确的定义为_____。

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 (counter*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) (f product counter max-count )) ))； //本题考查迭代过程的定义

答案是：C 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 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)。 (C) f()是常数为1的函数；g(x1,x2) = (x1+1) * (x2+1)。 (D) f()是常数为1的函数；g(x1) = n * (x1)。

答案是：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 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 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 23、关于“递归”，下列说法不正确的是_____。 (A)“递归”源自于数学上的递推式和数学归纳法。

(B)“递归”与递推式一样，都是自递推基础计算起，由前项(第n-1项)计算后项(第n项)，直至最终结果的获得。

(C)“递归”是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得； (D)“递归”是由前n-1项计算第n项的一种方法。

答案是：B 24、关于“递归”，下列说法不正确的是_____。

(A)可以利用“递归”进行具有自相似性无限重复事物的定义。

(B)可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行”。

(C)可以利用“递归”进行具有自相似性无限重复规则的算法的构造； (D)上述说法不全正确。

答案是：D 25、关于递归定义的函数，下列说法正确的是_____。 (A)递归定义的函数一定是“递归计算”的； (B)递归定义的函数一定是“迭代计算”的；

(C)有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”；

(D)凡是可以“迭代计算”的函数，一定可以“递归计算”，凡是可以“递归计算”的函数，也一定可以“迭代计算”。

答案是：C 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 Z)； (C) (X)；

(D) ((X and Y) or (not Z)) and (not M)。

答案是：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 28、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示：

任何一个A(n, m)都可以递归地进行计算，例如m=1时，A(n,1)的递归计算过程如下所示：

m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2n

请你按上述方法递归计算m=2时，即A(n,2)，并判断计算结果正确的是_____。 (A) A(n, 2) = 2n； (B) A(n, 2) = 2n； (C) A(n, 2) = (n+2)2； (D) A(n, 2) = n+2。

答案是：B 29、斐波那契数列与阿克曼函数都是递归函数，但它们是不同的，下列说法不正确的是_____。

斐波那契数列

与阿克曼函数

(A) 斐波那契数列是原始递归的，而阿克曼函数不是原始递归的；

(B) 斐波那契数列可以递推地计算即迭代计算；而阿克曼函数只能递归地计算； (C) 阿克曼函数也可如斐波那契数列一样自前项(第n-1项)计算到后项(第n项)；

(D) 阿克曼函数是双递归函数，不仅函数自身是递归定义的，同时函数的变量也是递归定义的。

答案是：B 30、关于“程序”和“递归”的关系，下列说法不正确的是_____。 (A) “程序”是计算系统体现千变万化功能的一种重要手段：计算系统仅需要实现简单元素以及一个程序执行机构即可；

(B) 本质上讲，“程序”就是对简单元素的组合(或称复合)；此外，“程序”需要有能力对一些常见的组合A进行命名，并利用该名字参与更为复杂的组合B的构造中，此即为“抽象”；在执行时(或称计算时)，再将该组合A替换组合B中的该名字，实现计算并获取结果； (C) “程序”的基本特征是复合、抽象与构造。而最重要的是，如何解决近乎无限的、具有自相似性的复杂组合的构造问题，这就需要递归和迭代；

(D) 递归和迭代是解决近乎无限的、重复的、嵌套的组合构造的基本手段，它采用“利用自身定义自身”、“自身调用自身”、“自身用自身来计算”的方法，将程序的复杂组合构造问题以简便的、明确的形式表达出来计算出来； (E) 上述说法有不正确的。

//本题考查对程序和递归的综合理解，以正面叙述为主，便于学生复习。

答案是：E