第3章 程序與遞歸：組合、抽象與構(gòu)造

1、第3章 程序與遞歸：組合、抽象與構(gòu)造       1、關(guān)于計算系統(tǒng)與程序，下列說法正確的是_。(A)只有用計算機(jī)語言編寫出來的代碼才是程序，其他都不能稱其為程序； (B)構(gòu)造計算系統(tǒng)是不需要程序的，程序?qū)?gòu)造計算系統(tǒng)沒有什么幫助； (C)任何系統(tǒng)都需要程序，只是這個程序是由人來執(zhí)行還是由機(jī)器自動執(zhí)行，可以由機(jī)器自動執(zhí)行程序的系統(tǒng)被稱為計算系統(tǒng)； (D)程序是用戶表達(dá)的隨使用者目的不同而千變?nèi)f化的復(fù)雜動作，不是使用者實現(xiàn)的而是需要計算系統(tǒng)事先完成的。 答案是：C2、關(guān)于程序，下列說法不正確的是_。(A)“程序”是由人編寫的、以告知計算系

2、統(tǒng)實現(xiàn)人所期望的復(fù)雜動作； (B)“程序”可以由系統(tǒng)自動解釋執(zhí)行，也可以由人解釋由系統(tǒng)執(zhí)行； (C)普通人是很難理解“程序”的，其也和“程序”無關(guān)； (D)“程序”幾乎和每個人都有關(guān)系，如自動售票系統(tǒng)、自動取款機(jī)等。  答案是：C3、關(guān)于程序，下列說法不正確的是_。(A)程序的基本特征是復(fù)合、抽象與構(gòu)造； (B)復(fù)合就是對簡單元素的各種組合，即將一個(些)元素代入到另一個(些)元素中； (C)抽象是對各種元素的組合進(jìn)行命名，并將該名字用于更復(fù)雜的組合構(gòu)造中； (D)程序就是通過組合、抽象、再組合等構(gòu)造出來的； (E)上述說法有不正確的。 答案是：E4、一般而言，設(shè)計和實現(xiàn)一個計算系統(tǒng)

3、，需要設(shè)計和實現(xiàn)_。(A)基本動作和程序； (B)基本動作和控制基本動作的指令； (C)基本動作、控制基本動作的指令和一個程序執(zhí)行機(jī)構(gòu)； (D)基本動作、控制基本動作的指令和程序。 答案是：C5、一般而言，一個較高抽象層次的計算系統(tǒng)是可以這樣實現(xiàn)的，即_。(A)將較低抽象層次的重復(fù)性組合，命名為較高抽象層次的指令； (B)利用較高抽象層次的指令進(jìn)行復(fù)合、抽象與構(gòu)造，即形成高抽象層次的程序； (C)高抽象層次的程序通過其程序執(zhí)行機(jī)構(gòu)解釋為高抽象層次的指令及其操作次序； (D)高抽象層次的指令被替換為低抽象層次的程序，再由低抽象層次的程序執(zhí)行機(jī)構(gòu)解釋并執(zhí)行。 (E)上述A-D全部。 答案是：E6、

4、熟悉下列運(yùn)算組合式(前綴表達(dá)式)，其中結(jié)果為56的是_。(A)  (*  7  (+  5  2)； (B)  (*  (+  5  3)  (+  5  2)； (C)  (+  20  (+  6  6)； (D)  (-  (*  9  8)  (-  20  2)。 /本題考查基本運(yùn)算組合式的構(gòu)造與計算，尤其是嵌套的運(yùn)算組合式的計算 答案是：B7、對

5、于計算式，其正確的運(yùn)算組合式(前綴表示法)為_。(A)  (/  (+  10  /  20  +  8  4)  (+  *  3  6  *  8  2 )； (B)  (10 +  (20  /  (8  +  4) / (3 * 6) + (8 * 2)； (C)  (/  (+  10  (/  20  (+ 

6、; 8  4)  (+  (*  3  6)  (*  8  2)； (D)  (/  (/  20  (+  10  (+  8  4)  (*  (+  3  6)  (+  8  2)。 /本題考查運(yùn)算組合式的書寫與構(gòu)造 答案是：C8、請用define運(yùn)算，定義一個過程實現(xiàn)計算a3，其正確定義的過程為_。(A)  (define  cube&

7、#160; 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)。 /本題考查新運(yùn)算符(即過程)的定義 答案是：B9、已知一個新運(yùn)算被定義為

8、(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)。 /本題考查新運(yùn)算符(即過程)的定義 答案是：B10、已知一個新運(yùn)算被定義為(define  (newCalc  x  y) (*  (+  x&#

9、160; 1)  (*  y  2)，問正確使用了newCalc并得到正確結(jié)果的為_。(A)  (newCalc) (4  5)，其結(jié)果為50； (B)  (newCalc  4)，其結(jié)果為40； (C)  (newCalc  4  5)，其結(jié)果為50； (D)  (newCalc  2  3)，其結(jié)果為21。 /本題考查新運(yùn)算符(即過程)的定義和使用 答案是：C11、已知一個新運(yùn)算被定義為(define  (newCalc  x  y

10、) (*  (+  x  1)  (+  y  1)，問(newCalc (newCalc (newCalc 1  1)  2)  3)的計算結(jié)果為_。(A) 6 ；(B) 13； (C) 64； (D) 24。 答案是：C12、已知一個新運(yùn)算被定義為(define  (newCalc  x  y) (*  (+  x  1)  (+  y  1)，問(newCalc  (newCalc (newCalc

11、1  1)  (newCalc 1  1)  (newCalc 1 1)的計算結(jié)果為_。(A) 1 ；(B) 64； (C) 130； (D) 8。 /本題考查新運(yùn)算符(即過程)的定義和嵌套使用 答案是：C13、已知一個運(yùn)算被定義為(define  (firstCalc  x)  (*  x  x)，在其基礎(chǔ)上進(jìn)一步定義新運(yùn)算secondCalc為x2+y2+z2，下列運(yùn)算組合式書寫正確的是_。(A)  (define  secondCalc  (+  (first

12、Calc  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  z)； (D)  (define se

13、condCalc x y z  (+  (firstCalc  x)  (firstCalc  y)  (firstCalc  z)。 (E)  (define (secondCalc x y z)  (+  (firstCalc  x)  (firstCalc  x)  (firstCalc  x)。 /本題考查新運(yùn)算符(即過程)的定義，以及形式參數(shù)的使用 答案是：C14、已知一個運(yùn)算被定義為(define  (firstCalc&#

14、160; x)  (*  x  x)，在其基礎(chǔ)上進(jìn)一步定義新運(yùn)算為(define  (secondCalc  x)  (firstCalc  (firstCalc  (firstCalc  x)，問secondCalc表達(dá)的運(yùn)算功能為_。(A)  x*x*x； (B)  x2+x2+x2； (C)  (x2)2)2； (D)  x4。 /本題考查新運(yùn)算符(即過程)的定義和嵌套使用 答案是：C15、用條件運(yùn)算符定義一個過程。正確的定義為_。(A) (define

15、60; (f  x  y)  (cond  (x>y)  (*  x  x  x) (x=y )  0)(x<y )  (*  y  y  y) )； (B) (define  (f  x  y)  (cond  (>  x  y )  (*  x  x  x) (=  x  y )   

16、0)(<  x  y )    (*  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  (<  x  y )  (*  x  x

17、  x) (=  x  y )    0)(>  x  y )    (*  y  y  y) )。 /本題考查條件運(yùn)算符的使用及分支處理 答案是：B16、用條件運(yùn)算符定義一個過程。正確的定義為_。(A) (define  (f  n)  (cond  (n<2 )  1) (n>1)  (n* f(n-1) )(B) (define  (f  n) 

18、; (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

19、60; 2 )  1) (>  n  1 )    (*  n  (f  n-1) )。 /本題考查遞歸過程的定義 答案是：B17、若要表達(dá)從1計算到n的運(yùn)算組合式，(* (*  (*  (*  (*  1  1)  2)  3)  4) n)定義一個過程。正確的定義為_。(A) (define  (f  product  counter  max-count) (f 

20、(* 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) (d

21、efine  (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 (&

22、gt;  counter  max-count)  product) (<= counter max-count)  (f  product  counter  max-count ) )； /本題考查迭代過程的定義 答案是：C18、關(guān)于原始遞歸函數(shù)的理解，下列說法不正確的是_。(A)“復(fù)合”即是將一組函數(shù)g1,g2,gn作為參數(shù)代入到另一函數(shù)f(x1,x2,xn)中，即n個函數(shù)g1,g2,gn被組合到了一起，是按函數(shù)f的形式進(jìn)行的組合。 (B)“原始遞歸”即是要定義h(0),h(1),h(n),h(n+1)，其中h(

23、0)需要直接給出，而h(n+1)需要用h(n)進(jìn)行定義，即h(n+1)是將h(n)和n復(fù)合在一起。 (C)復(fù)合是構(gòu)造新函數(shù)的一種手段，原始遞歸也是構(gòu)造新函數(shù)的一種手段； (D)遞歸函數(shù)是描述程序組合與構(gòu)造問題的一種數(shù)學(xué)形式。 (E)上述說法有不正確的。 答案是：E19、按原始遞歸的定義，h是由f和g遞歸地構(gòu)造出來的。假設(shè)已知h(n) = n!，請給出構(gòu)造h的f和g的函數(shù)。正確的是_。(A) f()是常數(shù)為1的函數(shù)；g(x1,x2) = x1 * x2。 (B) f()是常數(shù)為1的函數(shù)；g(x1,x2) = x1 * (x2+1)。 (C) f()是常數(shù)為1的函數(shù)；g(x1,x2) = (x1+

24、1) * (x2+1)。 (D) f()是常數(shù)為1的函數(shù)；g(x1) = n * (x1)。 答案是：B20、已知f(x)=x，g(x1,x2,x3)=x1+x2+x3, 其中x,x1,x2,x3均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，請按遞歸式進(jìn)行計算下列式子，正確的是_。(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,x

25、1,x2,x3均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，請按遞歸式進(jìn)行計算下列式子，正確的是_。(A) h(1，x) = 5； (B) h(2，x) = 5+x； (C) h(3，x) = 5+2x； (D) h(4，x) = 5+3x ； (E)上述都不正確。 答案是：A22、已知f(x)=x，g(x1,x2,x3)=x1*(x2+1), 其中x,x1,x2,x3均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，請按遞歸式進(jìn)行計算下列式子

26、，不正確的是_。(A) h(1，x) = x； (B) h(2，x) = 2x； (C) h(3，x) = 6x； (D) h(4，x) = 12x； 答案是：D23、關(guān)于“遞歸”，下列說法不正確的是_。(A)“遞歸”源自于數(shù)學(xué)上的遞推式和數(shù)學(xué)歸納法。 (B)“遞歸”與遞推式一樣，都是自遞推基礎(chǔ)計算起，由前項(第n-1項)計算后項(第n項)，直至最終結(jié)果的獲得。 (C)“遞歸”是自后項(即第n項)向前項(第n-1項)代入，直到遞歸基礎(chǔ)獲取結(jié)果，再從前項計算后項獲取結(jié)果，直至最終結(jié)果的獲得； (D)“遞歸”是由前n-1項計算第n項的一種方法。 答案是：B24、關(guān)于“遞歸”，下列說法不正確的是_。

27、(A)可以利用“遞歸”進(jìn)行具有自相似性無限重復(fù)事物的定義。 (B)可以利用“遞歸”進(jìn)行具有自重復(fù)性無限重復(fù)動作的執(zhí)行，即“遞歸計算”或“遞歸執(zhí)行”。 (C)可以利用“遞歸”進(jìn)行具有自相似性無限重復(fù)規(guī)則的算法的構(gòu)造； (D)上述說法不全正確。 答案是：D25、關(guān)于遞歸定義的函數(shù)，下列說法正確的是_。(A)遞歸定義的函數(shù)一定是“遞歸計算”的； (B)遞歸定義的函數(shù)一定是“迭代計算”的； (C)有些遞歸定義的函數(shù)可以“迭代計算”，有些遞歸定義的函數(shù)則必須“遞歸計算”； (D)凡是可以“迭代計算”的函數(shù)，一定可以“遞歸計算”，凡是可以“遞歸計算”的函數(shù)，也一定可以“迭代計算”。 答案是：C26、用遞歸

28、是可以定義語言的。如表述命題邏輯的一種語言可以如下定義：(1)一個命題是其值為真或假的一個判斷語句； (2)如果X是一個命題，Y也是一個命題，則X and Y，X or Y, not X也是一個命題； (3)如果X是一個命題，則(X)也是一個命題，括號內(nèi)的命題運(yùn)算優(yōu)先； (4)命題由以上方式構(gòu)造。 若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、遞歸計算是重要的執(zhí)行手段。例如一種形式的阿克曼函數(shù)如下所示： 任何一個A(m, n)都可以遞歸地進(jì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。 請你按上述方法遞歸計算下列項，并判斷，計算結(jié)果正確的是_。(A)  A(1, 8) = 9； (B)  A(2, 0) = 2； (C)  A(2, 1) = 4；