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

1、第3章 程序(chngx)與遞歸：組合、抽象與構(gòu)造 1、關(guān)于計算系統(tǒng)(xtng)與程序，下列說法正確的是_。(A)只有(zhyu)用計算機(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)“程序”是由人編寫的、以告知計算系統(tǒng)實現(xiàn)人所期望的復(fù)雜動作； (B)

2、“程序”可以由系統(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)，需要設(shè)計和實現(xiàn)_。(A)基本動作和程序； (

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

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

5、8 2)； (D) (/ (/ 20 (+ 10 (+ 8 4) (* (+ 3 6) (+ 8 2)。 /本題考查運算組合式的書寫與構(gòu)造 答案是：C8、請用define運算，定義一個過程實現(xiàn)計算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、已知一個(y )新運算被定義為(define (newCalc x y) (

6、* (+ x 1) (* y 2)，問newCalc可以(ky)完成的計算功能為_。(A) (x+1)+2y； (B) (x+1)*2y； (C) (x+1) +(y+2)； (D) (x+1)*(y+2)。 /本題考查新運算符(即過程(guchng)的定義 答案是：B10、已知一個新運算被定義為(define (newCalc x y) (* (+ x 1) (* y 2)，問正確使用了newCalc并得到正確結(jié)果的為_。(A) (newCalc) (4 5)，其結(jié)果為50； (B) (newCalc 4)，其結(jié)果為40； (C) (newCalc 4 5)，其結(jié)果為50； (D) (new

7、Calc 2 3)，其結(jié)果為21。 /本題考查新運算符(即過程)的定義和使用 答案是：C11、已知一個新運算被定義為(define (newCalc x y) (* (+ x 1) (+ y 1)，問(newCalc (newCalc (newCalc 1 1) 2) 3)的計算結(jié)果為_。(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)的計算結(jié)

8、果為_。(A) 1 ；(B) 64； (C) 130； (D) 8。 /本題考查新運算符(即過程)的定義和嵌套使用 答案是：C13、已知一個運算被定義為(define (firstCalc x) (* x x)，在其基礎(chǔ)上進(jìn)一步定義新運算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

9、 y z) (+ (firstCalc x) (firstCalc y) (firstCalc 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)。 /本題考查新運算符(即過程)的定義，以及形式參數(shù)的使用 答案是：C14、已知一個運算被定義為(define (firstCalc x) (* x x)，在其基礎(chǔ)上進(jìn)一步定義新運算為(defin

10、e (secondCalc x) (firstCalc (firstCalc (firstCalc x)，問secondCalc表達(dá)(biod)的運算功能為_。(A) x*x*x； (B) x2+x2+x2； (C) (x2)2)2； (D) x4。 /本題考查新運算符(即過程(guchng)的定義和嵌套使用 答案是：C15、用條件運算符定義一個(y )過程。正確的定義為_。(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

11、*y) )； (D) (define (f x y) (cond ( x y ) (* y y y) )。 /本題考查條件運算符的使用及分支處理 答案是：B16、用條件運算符定義(dngy)一個過程。正確(zhngqu)的定義為_。(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) )

12、。 /本題考查遞歸過程(guchng)的定義 答案是：B17、若要表達(dá)從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) product) ( coun

13、ter max-count) product) (= counter max-count) (f product counter max-count ) )； /本題考查迭代過程的定義 答案是：C18、關(guān)于原始遞歸函數(shù)的理解，下列說法(shuf)不正確的是_。(A)“復(fù)合(fh)”即是將一組函數(shù)g1,g2,gn作為(zuwi)參數(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(0)需要直接給出，而h(n+1)需要用h(n)進(jìn)行定義，即h(n+1)是將h

14、(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+1) * (x2+1)。 (D) f()是常數(shù)為1的函數(shù)；g(x1) = n

15、 * (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,x1,x2,x3均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x) = f(x

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

17、) h(2，x) = 2x； (C) h(3，x) = 6x； (D) h(4，x) = 12x； 答案是：D23、關(guān)于“遞歸”，下列說法(shuf)不正確的是_。(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)于“遞歸”，下列說法不正確的是_。(A)可以利用“遞歸”進(jìn)行具有自相似性無

18、限重復(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、用遞歸是可以定義語言的。如表述(bio sh)

19、命題邏輯的一種語言可以如下定義：(1)一個命題是其值為真或假的一個判斷語句； (2)如果X是一個命題，Y也是一個命題，則X and Y，X or Y, not X也是一個命題； (3)如果X是一個命題，則(X)也是一個命題，括號內(nèi)的命題運算優(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ù)(hnsh)如下所示： 任何一個A(m,

20、n)都可以(ky)遞歸地進(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； (D) A(1, n) = n+2。 答案是：D28、遞歸計算是重要的執(zhí)行(zhxng)手段。例如一種形式的阿克曼函數(shù)如下所示： 任何一個A(n, m)都可以遞歸地進(jìn)行計算，例如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請你按上述(shngsh)方法遞歸計算m=2時，即A(n,2)，并判斷計算結(jié)果正確的是_。(A) A(n, 2) = 2n； (B) A(n, 2) = 2n； (C) A(n, 2) = (n+2)2； (D) A(n, 2) = n+2。 答案是：B29、斐波那契數(shù)列(shli)與阿克曼函數(shù)都是遞歸函數(shù)，但它們是不同的，下列說法不正確的是_。斐波那契數(shù)列與阿克曼函數(shù)(A) 斐波那契數(shù)列是原始遞歸的，而阿克曼函數(shù)不是原始遞歸的； (B) 斐波那契數(shù)列