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

1、关于计算系统与程序，下列说法正确的是。(A) 只有用计算机语言编写出来的代码才是程序，其他都不能称其为程序；(B) 构造计算系统是不需要程序的，程序对构造计算系统没有什么帮助；(C) 任何系统都需要程序，只是这个程序是由人来执行还是由机器自动执行，可 以由机器自动执行程序的系统被称为计算系统；(D) 程序是用户表达的随使用者目的不同而千变万化的复杂动作，不是使用者实 现的而是需要计算系统事先完成的。答案是：C2、关于程序，下列说法不正确的是。(A) “程序”是由人编写的、以告知计算系统实现人所期望的复杂动作;(B) “程序”可以由系统自动解释执行，也可以由人解释由系统执行；(C) 普通人是很难理解“程序”的，其也和“程序”无关；(D) “程序”几乎和每个人都有关系，如自动售票系统、自动取款机等。答案是：C3、关于程序，下列说法不正确的是。(A) 程序的基本特征是复合、抽象与构造；(B) 复合就是对简单元素的各种组合，即将一个(些)元素代入到另一个(些)元素中；(C) 抽象是对各种元素的组合进行命名，并将该名字用于更复杂的组合构造中；(D) 程序就是通过组合、抽象、再组合等构造出来的；(E) 上述说法有不正确的。答案是：E4、一般而言，设计和实现一个计算系统，需要设计和实现(A) 基本动作和程序；(B) 基本动作和控制基本动作的指令；(C) 基本动作、控制基本动作的指令和一个程序执行机构；(D) 基本动作、控制基本动作的指令和程序。5、一般而言，一个较高抽象层次的计算系统是可以这样实现的，即。(A) 将较低抽象层次的重复性组合，命名为较高抽象层次的指令；(B) 利用较高抽象层次的指令进行复合、抽象与构造，即形成高抽象层次的程序;(C) 高抽象层次的程序通过其程序执行机构解释为高抽象层次的指令及其操作次序；(D) 高抽象层次的指令被替换为低抽象层次的程序，再由低抽象层次的程序执行 机构解释并执行。(E) 上述A-D全部。答案是：E6、熟悉下列运算组合式(前缀表达式)，其中结果为56的是。(A) (*7(+52)；(B) (*(+53)(+52)；(C) (+20(+66)；(D) (-(*98)(-202)。本题考查基本运算组合式的构造与计算，尤其是嵌套的运算组合式的计算答案是：B7、对于计算式3*6普*2，其正确的运算组合式(前缀表示法)为。(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)。/本题考查运算组合式的书写与构造答案是：C8、请用define运算，定义一个过程实现计算a3其正确定义的过程为(A)(B)(C)(D)(define(define(define(definecube(cube(cube(cube(*x)(*a (*a)(*a)a)；x)；a)；x)。本题考查新运算符(即过程)的定义答案是：B9、巳知一个新运算被定义为(define(newCalc x y)(*(+ x 1)(* y 2),问newCalc可以完成的计算功能为(A) (x+1)+2y；(B) (x+1)*2y；(C) (x+1) +(y+2)；(D) (x+1)*(y+2)。本题考查新运算符(即过程)的定义答案是：B10、已知一个新运算被定义为(define(newCalc x y)(*(+ x 1)(* y 2),问正确使用了 newCalc并得到正确结果的为_O(A)(newCalc) (45),其结果为50；(B)(newCalc 4)，其结果为40；(C)(newCalc 45),其结果为50；(D)(newCalc 23),其结果为21。本题考查新运算符(即过程)的定义和使用答案是：C11、已知一个新运算被定义为(define (newCalc x y)(*(+ x 1)(+ y 1)，问(newCalc (newCalc (newCalc11)2)3)的计算结果为。(A) 6 ； (B) 13；(C) 64；(D) 24。答案是：C12、已知一个新运算被定义为(define (newCalc x y)(*(+ x 1)(+ y 1)，问(newCalc (newCalc (newCalc11) (newCalc 11) (newCalc1 1)的计算结果为。(A) 1； (B) 64；(C)130；(D) 8。本题考查新运算符(即过程)的定义和嵌套使用(A) (definesecondCalc(+ (firstCalcx) (firstCalc(firstCalcz)；(B) (define(secondCalc xy z) (+ firstCalc x y z)；(C) (define(secondCalc xyz) (+ (firstCalc x)(firstCalc y)(firstCalc z)；(D) (definesecondCalc xyz (+ (firstCalc x)(firstCalc y)(firstCalc z)。(E) (define(secondCalc xyz) (+ (firstCalc x)(firstCalc x)(firstCalc x)。本题考查新运算符(即过程)的定义，以及形式参数的使用y)13、已知一个运算被定义为(define (firstCalc x) (* x x)，在 其基础上进一步定义新运算secondCalc为x2+y2+z2，下列运算组合式书写正确 的是。答案是：Cx x)，在14、已知一个运算被定义为(define(firstCalc x) (*其基础上进一步定义新运算为(define (secondCalc x) (firstCalc (firstCalc (firstCalc x)，问secondCalc表达的运算功能为。(A)x*x*x；(B)x2+x2+x2；(C)(x2)2)2；(D)x4。本题考查新运算符(即过程)的定义和嵌套使用15、用条件运算符定义一个过程o M/刘' k = ywo。正确的定义为(A) (define (f x y) (cond(x>y)(* x x x)(x=y )0)(x<y )(*y y y)；(B) (define (f x y) (cond(> xy )(* x x(=xy )0)(<xy )(*y y y)(C) (define (f x y) (cond)；(x>y)(x*x*x)(x=y )0)(x<y )(y*y*y)；(D) (define (f x y) (cond(< xy )(* x x答案是：Cx)x)(=x y )0)(> x y )(*y yy)。本题考查条件运算符的使用及分支处理答案是：B1if n <216、用条件运算符定义一个过程1置本伊一1)1订巧1。正确的定义为_(A) (define(f n)(cond(n<2 )1)(n>1)(n* f(n-1)(B) (define(f n)(cond(< n2 )1)(> n 1 )(*n (f(-n1)；(C) (define(f n)(cond(n<2)1)(n>1 )(n*f(n-1)；(D) (define(f n)(cond(< n2 )1)(> n 1 )(*n (fn-1)。本题考查递归过程的定义答案是：B17、若要表达从1计算到n的运算组合式，(* (*(*(*(*11)2)3)4)n)定义一个过程。正确的定义为。(A) (define(fproductcountermax-count)(f (* counter product) (+ counter 1) max-count )；(B) (define(fproductcountermax-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 )；本题考查迭代过程的定义18、关于原始递归函数的理解，下列说法不正确的是。(A) “复合”即是将一组函数g,g,g作为参数代入到另一函数f(x,x,x) 中，即n个函数g,g,g被组合到了一起，是按函数f的形式进行的组合。"(B) “原始递归”即是要定义h(0),h(1),，h(n),h(n+1)，其中h(0)需要直接给 出，而h(n+1)需要用h(n)进行定义，即h(n+1)是将h(n)和复合在一起。(C) 复合是构造新函数的一种手段，原始递归也是构造新函数的一种手段；(D) 递归函数是描述程序组合与构造问题的一种数学形式。(E) 上述说法有不正确的。答案是：E19、按原始递归的定义，h是由f和g递归地构造出来的。假设已知h(n)=n!， 请给出构造h的f和g的函数。正确的是。(A) f()是常数为 1 的函数；g(x15x2) = x1 * x2。(B) f()是常数为 1 的函数；g(x：,x：) = x： * (x2+1) o(C) f()是常数为 1 的函数；g(x1，x：) = (x +1) * (x2+1) o(D) f()是常数为1的函数；g(