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

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

1、關(guān)于計(jì)算系統(tǒng)與程序，下列說法正確的是_____。

(A)只有用計(jì)算機(jī)語言編寫出來的代碼才是程序，其他都不能稱其為程序；

(B)構(gòu)造計(jì)算系統(tǒng)是不需要程序的，程序?qū)?gòu)造計(jì)算系統(tǒng)沒有什么幫助；

(C)任何系統(tǒng)都需要程序，只是這個(gè)程序是由人來執(zhí)行還是由機(jī)器自動(dòng)執(zhí)行，可以由機(jī)器自動(dòng)執(zhí)行程序的系統(tǒng)被稱為計(jì)算系統(tǒng)；

(D)程序是用戶表達(dá)的隨使用者目的不同而千變?nèi)f化的復(fù)雜動(dòng)作，不是使用者實(shí)現(xiàn)的而是需要計(jì)算系統(tǒng)事先完成的。

答案是：C2、關(guān)于程序，下列說法不正確的是_____。

(A)“程序”是由人編寫的、以告知計(jì)算系統(tǒng)實(shí)現(xiàn)人所期望的復(fù)雜動(dòng)作；

(B)“程序”可以由系統(tǒng)自動(dòng)解釋執(zhí)行，也可以由人解釋由系統(tǒng)執(zhí)行；

(C)普通人是很難理解“程序”的，其也和“程序”無關(guān)；

(D)“程序”幾乎和每個(gè)人都有關(guān)系，如自動(dòng)售票系統(tǒng)、自動(dòng)取款機(jī)等。

答案是：C3、關(guān)于程序，下列說法不正確的是_____。

(A)程序的基本特征是復(fù)合、抽象與構(gòu)造；

(B)復(fù)合就是對(duì)簡(jiǎn)單元素的各種組合，即將一個(gè)(些)元素代入到另一個(gè)(些)元素中；

(C)抽象是對(duì)各種元素的組合進(jìn)行命名，并將該名字用于更復(fù)雜的組合構(gòu)造中；

(D)程序就是通過組合、抽象、再組合等構(gòu)造出來的；

(E)上述說法有不正確的。

答案是：E4、一般而言，設(shè)計(jì)和實(shí)現(xiàn)一個(gè)計(jì)算系統(tǒng)，需要設(shè)計(jì)和實(shí)現(xiàn)_____。

(A)基本動(dòng)作和程序；

(B)基本動(dòng)作和控制基本動(dòng)作的指令；

(C)基本動(dòng)作、控制基本動(dòng)作的指令和一個(gè)程序執(zhí)行機(jī)構(gòu)；

(D)基本動(dòng)作、控制基本動(dòng)作的指令和程序。

答案是：C5、一般而言，一個(gè)較高抽象層次的計(jì)算系統(tǒng)是可以這樣實(shí)現(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、熟悉下列運(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)造與計(jì)算，尤其是嵌套的運(yùn)算組合式的計(jì)算

答案是：B7、對(duì)于計(jì)算式，其正確的運(yùn)算組合式(前綴表示法)為_____。

(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)))

(*

(+

3

6)

(+

8

2)))。

//本題考查運(yùn)算組合式的書寫與構(gòu)造

答案是：C8、請(qǐng)用define運(yùn)算，定義一個(gè)過程實(shí)現(xiàn)計(jì)算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)))。

((=

x

y)

0)

((>

x

y)

(*

y

y

y))))。

//本題考查條件運(yùn)算符的使用及分支處理

答案是：B16、用條件運(yùn)算符定義一個(gè)過程。正確的定義為_____。

(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)))))。

//本題考查遞歸過程的定義

答案是：B17、若要表達(dá)從1計(jì)算到n的運(yùn)算組合式，(*…(*

(*

(*

(*

1

1)

2)

3)

4)…n)

定義一個(gè)過程。正確的定義為_____。

(A)(define

(f

product

counter

max-count)

(f

(*counterproduct)

(+

counter

1)

max-count))；

(B)(define

(f

product

counter

max-count)

(cond((>

counter

max-count)

product)

((<=countermax-count)

(f

(counter*product)

(counter+1)

max-count))))；

(C)(define

(f

product

counter

max-count)

(cond((>

counter

max-count)

product)

((<=countermax-count)

(f

(*counterproduct)

(+

counter

1)max-count))))；

(D)(define

(f

product

counter

max-count)

(cond((>

counter

max-count)

product)

((<=countermax-count)

(f

product

counter

max-count))))；

//本題考查迭代過程的定義

答案是：C18、關(guān)于原始遞歸函數(shù)的理解，下列說法不正確的是_____。

(A)“復(fù)合”即是將一組函數(shù)g1,g2,…,gn作為參數(shù)代入到另一函數(shù)f(x1,x2,…,xn)中，即n個(gè)函數(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(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!，請(qǐng)給出構(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*(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)，請(qǐng)按遞歸式進(jìn)行計(jì)算下列式子，正確的是_____。

(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),且h(S(n),x)=g(h(n,x),n,x)，請(qǐng)按遞歸式進(jìn)行計(jì)算下列式子，正確的是_____。

(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)，請(qǐng)按遞歸式進(jìn)行計(jì)算下列式子，不正確的是_____。

(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ǔ)計(jì)算起，由前項(xiàng)(第n-1項(xiàng))計(jì)算后項(xiàng)(第n項(xiàng))，直至最終結(jié)果的獲得。

(C)“遞歸”是自后項(xiàng)(即第n項(xiàng))向前項(xiàng)(第n-1項(xiàng))代入，直到遞歸基礎(chǔ)獲取結(jié)果，再?gòu)那绊?xiàng)計(jì)算后項(xiàng)獲取結(jié)果，直至最終結(jié)果的獲得；

(D)“遞歸”是由前n-1項(xiàng)計(jì)算第n項(xiàng)的一種方法。

答案是：B24、關(guān)于“遞歸”，下列說法不正確的是_____。

(A)可以利用“遞歸”進(jìn)行具有自相似性無限重復(fù)事物的定義。

(B)可以利用“遞歸”進(jìn)行具有自重復(fù)性無限重復(fù)動(dòng)作的執(zhí)行，即“遞歸計(jì)算”或“遞歸執(zhí)行”。

(C)可以利用“遞歸”進(jìn)行具有自相似性無限重復(fù)規(guī)則的算法的構(gòu)造；

(D)上述說法不全正確。

答案是：D25、關(guān)于遞歸定義的函數(shù)，下列說法正確的是_____。

(A)遞歸定義的函數(shù)一定是“遞歸計(jì)算”的；

(B)遞歸定義的函數(shù)一定是“迭代計(jì)算”的；

(C)有些遞歸定義的函數(shù)可以“迭代計(jì)算”，有些遞歸定義的函數(shù)則必須“遞歸計(jì)算”；

(D)凡是可以“迭代計(jì)算”的函數(shù)，一定可以“遞歸計(jì)算”，凡是可以“遞歸計(jì)算”的函數(shù)，也一定可以“迭代計(jì)算”。

答案是：C26、用遞歸是可以定義語言的。如表述命題邏輯的一種語言可以如下定義：

(1)一個(gè)命題是其值為真或假的一個(gè)判斷語句；

(2)如果X是一個(gè)命題，Y也是一個(gè)命題，則XandY，XorY,notX也是一個(gè)命題；

(3)如果X是一個(gè)命題，則(X)也是一個(gè)命題，括號(hào)內(nèi)的命題運(yùn)算優(yōu)先；

(4)命題由以上方式構(gòu)造。

若X，Y，Z，M等均是一個(gè)命題，問不符合上述遞歸定義的語句是_____。

(A)

X；

(B)(XandYnotZ)；

(C)

(X)；

(D)((X

and

Y)

or

(not

Z))and

(notM)。

答案是：B27、遞歸計(jì)算是重要的執(zhí)行手段。例如一種形式的阿克曼函數(shù)如下所示：

任何一個(gè)A(m,n)都可以遞歸地進(jìn)行計(jì)算，例如A(1,2)的遞歸計(jì)算過程如下所示：

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。

請(qǐng)你按上述方法遞歸計(jì)算下列項(xiàng)，并判斷，計(jì)算結(jié)果正確的是_____。

(A)

A(1,8)=9；

(B)

A(2,0)=2；

(C)

A(2,1)=4；

(D)

A(1,n)=n+2。

答案是：D28、遞歸計(jì)算是重要的執(zhí)行手段。例如一種形式的阿克曼函數(shù)如下所示：

任何一個(gè)A(n,m)都可以遞歸地進(jìn)行計(jì)算，例如m=1時(shí)，A(n,1)的遞歸計(jì)算過程如下所示：

m=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2n

請(qǐng)你按上述方法遞歸計(jì)算m=2時(shí)，即A(n,2)，并判斷計(jì)算結(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ù)列與阿克曼函數(shù)都是遞歸函數(shù)，但它們是不同的，下列說法不正確的是_____。

斐波那契數(shù)列

與阿克曼函數(shù)

(A)斐波那契數(shù)列是原始遞歸的，而阿克曼函數(shù)不是原始遞歸的；

(B)斐波那契數(shù)列可以遞推地計(jì)算即迭代計(jì)算；而阿克曼函數(shù)只能遞歸地計(jì)算；

(C)阿克曼函數(shù)也可如斐波那契數(shù)列一樣自前項(xiàng)(第n-1項(xiàng))計(jì)算到后項(xiàng)(第n項(xiàng))；

(D)阿克曼函數(shù)是雙遞歸函數(shù)，不僅函數(shù)自身是遞歸定義的，同時(shí)函數(shù)的變量也是遞歸定義的。

答案是：B30、關(guān)于“程序”和“遞歸”的關(guān)系，下列說法不正確的是_____。

(A)“程序”是計(jì)算系統(tǒng)體現(xiàn)千變?nèi)f化功能的一種重要手段：計(jì)算系統(tǒng)僅需要實(shí)現(xiàn)簡(jiǎn)單元素以及一個(gè)程序執(zhí)行機(jī)構(gòu)即可；

(B)本質(zhì)上講，“程序”就是對(duì)簡(jiǎn)單元素的組合(或稱復(fù)合)；此外，“程序”需要有能力對(duì)一些常見的組合A進(jìn)行命名，并