《第3章程序与递归-组合抽象与构造.doc》由会员分享，可在线阅读，更多相关《第3章程序与递归-组合抽象与构造.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 程序与递归：组合、抽象与构造 1、关于计算系统与程序，下列说法正确的是_。(A)只有用计算机语言编写出来的代码才是程序，其他都不能称其为程序； (B)构造计算系统是不需要程序的，程序对构造计算系统没有什么帮助； (C)任何系统都需要程序，只是这个程序是由人来执行还是由机器自动执行，可以由机器自动执行程序的系统被称为计算系统； (D)程序是用户表达的随使用者目的不同而千变万化的复杂动作，不是使用者实现的而是需要计算系统事先完成的。 答案是：C2、关于程序，下列说法不正确的是_。(A)“程序”是由人编写的、以告知计算系统实现人所期望的复杂动作； (B)“程序”可以由系统自动解释执行，也可以
2、由人解释由系统执行； (C)普通人是很难理解“程序”的，其也和“程序”无关； (D)“程序”几乎和每个人都有关系，如自动售票系统、自动取款机等。 答案是：C3、关于程序，下列说法不正确的是_。(A)程序的基本特征是复合、抽象与构造； (B)复合就是对简单元素的各种组合，即将一个(些)元素代入到另一个(些)元素中； (C)抽象是对各种元素的组合进行命名，并将该名字用于更复杂的组合构造中； (D)程序就是通过组合、抽象、再组合等构造出来的； (E)上述说法有不正确的。 答案是：E4、一般而言，设计和实现一个计算系统，需要设计和实现_。(A)基本动作和程序； (B)基本动作和控制基本动作的指令； (
3、C)基本动作、控制基本动作的指令和一个程序执行机构； (D)基本动作、控制基本动作的指令和程序。 答案是：C5、一般而言，一个较高抽象层次的计算系统是可以这样实现的，即_。(A)将较低抽象层次的重复性组合，命名为较高抽象层次的指令； (B)利用较高抽象层次的指令进行复合、抽象与构造，即形成高抽象层次的程序； (C)高抽象层次的程序通过其程序执行机构解释为高抽象层次的指令及其操作次序； (D)高抽象层次的指令被替换为低抽象层次的程序，再由低抽象层次的程序执行机构解释并执行。 (E)上述A-D全部。 答案是：E6、熟悉下列运算组合式(前缀表达式)，其中结果为56的是_。(A) (* 7 (+ 5
4、2)； (B) (* (+ 5 3) (+ 5 2)； (C) (+ 20 (+ 6 6)； (D) (- (* 9 8) (- 20 2)。 /本题考查基本运算组合式的构造与计算，尤其是嵌套的运算组合式的计算 答案是：B7、对于计算式，其正确的运算组合式(前缀表示法)为_。(A) (/ (+ 10 / 20 + 8 4) (+ * 3 6 * 8 2 )； (B) (10 + (20 / (8 + 4) / (3 * 6) + (8 * 2)； (C) (/ (+ 10 (/ 20 (+ 8 4) (+ (* 3 6) (* 8 2)； (D) (/ (/ 20 (+ 10 (+ 8 4)
5、(* (+ 3 6) (+ 8 2)。 /本题考查运算组合式的书写与构造 答案是：C8、请用define运算，定义一个过程实现计算a3，其正确定义的过程为_。(A) (define cube a (* a a a)； (B) (define (cube x) (* x x x)； (C) (define (cube a (* a a a)； (D) (define (cube a) (* x x x)。 /本题考查新运算符(即过程)的定义 答案是：B9、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (* y 2)，问newCalc可以完成的计算功能为_
6、。(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并得到正确结果的为_。(A) (newCalc) (4 5)，其结果为50； (B) (newCalc 4)，其结果为40； (C) (newCalc 4 5)，其结果为50； (D) (newCalc 2 3)，其结果为21。 /本题考查新运算符(即过程)的定义和使用 答案是：C11、已
7、知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)，问(newCalc (newCalc (newCalc 1 1) 2) 3)的计算结果为_。(A) 6 ；(B) 13； (C) 64； (D) 24。 答案是：C12、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)，问(newCalc (newCalc (newCalc 1 1) (newCalc 1 1) (newCalc 1 1)的计算结果为_。(A) 1 ；(B) 64； (C) 130； (D) 8。 /本题考查新运算符(即过程
8、)的定义和嵌套使用 答案是：C13、已知一个运算被定义为(define (firstCalc x) (* x x)，在其基础上进一步定义新运算secondCalc为x2+y2+z2，下列运算组合式书写正确的是_。(A) (define secondCalc (+ (firstCalc x) (firstCalc y) (firstCalc z)； (B) (define (secondCalc x y z) (+ firstCalc x y z)； (C) (define (secondCalc x y z) (+ (firstCalc x) (firstCalc y) (firstCalc
9、z)； (D) (define secondCalc x y z (+ (firstCalc x) (firstCalc y) (firstCalc z)。 (E) (define (secondCalc x y z) (+ (firstCalc x) (firstCalc x) (firstCalc x)。 /本题考查新运算符(即过程)的定义，以及形式参数的使用 答案是：C14、已知一个运算被定义为(define (firstCalc x) (* x x)，在其基础上进一步定义新运算为(define (secondCalc x) (firstCalc (firstCalc (firstCal
10、c x)，问secondCalc表达的运算功能为_。(A) x*x*x； (B) x2+x2+x2； (C) (x2)2)2； (D) x4。 /本题考查新运算符(即过程)的定义和嵌套使用 答案是：C15、用条件运算符定义一个过程。正确的定义为_。(A) (define (f x y) (cond (xy) (* x x x) (x=y ) 0)(x x y ) (* x x x) (= x y ) 0)(y) (x*x*x) (x=y ) 0)(xy ) (y*y*y) )； (D) (define (f x y) (cond ( x y ) (* y y y) )。 /本题考查条件运算符的
11、使用及分支处理 答案是：B16、用条件运算符定义一个过程。正确的定义为_。(A) (define (f n) (cond (n1) (n* f(n-1) )(B) (define (f n) (cond ( n 1 ) (* n (f (- n 1) )； (C) (define (f n) (cond (n1 ) (n* f(n-1) ) )； (D) (define (f n) (cond ( n 1 ) (* n (f n-1) )。 /本题考查递归过程的定义 答案是：B17、若要表达从1计算到n的运算组合式，(* (* (* (* (* 1 1) 2) 3) 4) n)定义一个过程。正
12、确的定义为_。(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) product) ( counter max-count) product) (= counter max-count) (f product counter max-count ) )； /本题考查迭代
13、过程的定义 答案是：C18、关于原始递归函数的理解，下列说法不正确的是_。(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)上述说法有不正确的。 答案是：E19、按原始递归的
14、定义，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)。 答案是：B20、已知f(x)=x，g(x1,x2,x3)=x1+x2+x3, 其中x,x1,x2,x3均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n),
15、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)上述都不正确。 答案是：D21、已知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；
16、 (D) h(4，x) = 5+3x ； (E)上述都不正确。 答案是：A22、已知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； 答案是：D23、关于“递归”，下列说法不正确的是_。(A)“递归”源自于数学上的递推式和数学归纳法。 (B)“递归”与递推式一样，
17、都是自递推基础计算起，由前项(第n-1项)计算后项(第n项)，直至最终结果的获得。 (C)“递归”是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得； (D)“递归”是由前n-1项计算第n项的一种方法。 答案是：B24、关于“递归”，下列说法不正确的是_。(A)可以利用“递归”进行具有自相似性无限重复事物的定义。 (B)可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行”。 (C)可以利用“递归”进行具有自相似性无限重复规则的算法的构造； (D)上述说法不全正确。 答案是：D25、关于递归定义的函数，下列
18、说法正确的是_。(A)递归定义的函数一定是“递归计算”的； (B)递归定义的函数一定是“迭代计算”的； (C)有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”； (D)凡是可以“迭代计算”的函数，一定可以“递归计算”，凡是可以“递归计算”的函数，也一定可以“迭代计算”。 答案是：C26、用递归是可以定义语言的。如表述命题逻辑的一种语言可以如下定义：(1)一个命题是其值为真或假的一个判断语句； (2)如果X是一个命题，Y也是一个命题，则X and Y，X or Y, not X也是一个命题； (3)如果X是一个命题，则(X)也是一个命题，括号内的命题运算优先； (4)命题
19、由以上方式构造。 若X，Y，Z，M等均是一个命题，问不符合上述递归定义的语句是_。(A) X； (B) ( X and Y not Z)； (C) (X)； (D) (X and Y) or (not Z) and (not M)。 答案是：B27、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示： 任何一个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。 请你按上述方法递归计算下列项，并判断，计算结果正
20、确的是_。(A) A(1, 8) = 9； (B) A(2, 0) = 2； (C) A(2, 1) = 4； (D) A(1, n) = n+2。 答案是：D28、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示： 任何一个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,
21、2) = (n+2)2； (D) A(n, 2) = n+2。 答案是：B29、斐波那契数列与阿克曼函数都是递归函数，但它们是不同的，下列说法不正确的是_。斐波那契数列与阿克曼函数(A) 斐波那契数列是原始递归的，而阿克曼函数不是原始递归的； (B) 斐波那契数列可以递推地计算即迭代计算；而阿克曼函数只能递归地计算； (C) 阿克曼函数也可如斐波那契数列一样自前项(第n-1项)计算到后项(第n项)； (D) 阿克曼函数是双递归函数，不仅函数自身是递归定义的，同时函数的变量也是递归定义的。 答案是：B30、关于“程序”和“递归”的关系，下列说法不正确的是_。(A) “程序”是计算系统体现千变万化
22、功能的一种重要手段：计算系统仅需要实现简单元素以及一个程序执行机构即可； (B) 本质上讲，“程序”就是对简单元素的组合(或称复合)；此外，“程序”需要有能力对一些常见的组合A进行命名，并利用该名字参与更为复杂的组合B的构造中，此即为“抽象”；在执行时(或称计算时)，再将该组合A替换组合B中的该名字，实现计算并获取结果； (C) “程序”的基本特征是复合、抽象与构造。而最重要的是，如何解决近乎无限的、具有自相似性的复杂组合的构造问题，这就需要递归和迭代； (D) 递归和迭代是解决近乎无限的、重复的、嵌套的组合构造的基本手段，它采用“利用自身定义自身”、“自身调用自身”、“自身用自身来计算”的方法，将程序的复杂组合构造问题以简便的、明确的形式表达出来计算出来； (E) 上述说法有不正确的。 /本题考查对程序和递归的综合理解，以正面叙述为主，便于学生复习。 答案是：E