數(shù)據(jù)與計(jì)算科學(xué)基礎(chǔ) 習(xí)題答案（陳展榮） 第四章

習(xí)題4

一、單項(xiàng)選擇題

l.B2.C3.C4.A5.D6.A7.A8.D9.C10.A

ll.D12,C13.C14.B15.D16.A17.C18.C19.C20.B

21.D22.A23.C24.B25.D26.B27.C28.B29.D30.B

31.D32.A

二、判斷題JX

1.V2.X3.X4.X5.X6.V7.V8.X9.V10.V

11.X12.X

三、簡答題

1.【解答】

算法是一組可以方便轉(zhuǎn)化為計(jì)算機(jī)指令的明確步驟,它能在有限的時(shí)間內(nèi)終止并產(chǎn)生運(yùn)

算結(jié)果。符合用現(xiàn)代計(jì)算機(jī)來實(shí)現(xiàn)的算法應(yīng)有以下5個(gè)特征：

（1）明確性。算法的每個(gè)步驟必須有明確、具體的含義，算法表示中所使用的運(yùn)算符號、

控制符號也是前后一致的。

（2）可行性。算法的每一個(gè)步驟都可以轉(zhuǎn)化為一個(gè)或多個(gè)計(jì)算機(jī)可執(zhí)行的運(yùn)算，并實(shí)際可

執(zhí)行。

（3）有窮性。算法必須能在執(zhí)行有限個(gè)步驟后終止。

（4）0個(gè)或多個(gè)輸入。算法是用于處理數(shù)據(jù)的，必須接收到外部輸入的初始數(shù)據(jù)，才能對

這些數(shù)據(jù)進(jìn)行處理。如果算法內(nèi)包含了初始數(shù)據(jù)，則不需外部再輸入數(shù)據(jù)。

（5）1個(gè)或多個(gè)輸出。算法對數(shù)據(jù)加工處理后，一定要有輸出結(jié)果。

2.【解答】

條件驅(qū)動問題求解策略進(jìn)行求解是首先輸入數(shù)據(jù)，然后逐步求得中間值，并最終計(jì)算出

輸出結(jié)果。

在條件驅(qū)動問題求解策略中，變量的作用有標(biāo)識或保存輸入值、求解過程的中間值以及

輸出結(jié)果。

3.【解答】

目標(biāo)驅(qū)動問題求解策略進(jìn)行求解是將問題分解為若干個(gè)子問題，子問題再分解為更小的

子問題，直到子問題簡單可解為止，建立起一條從問題追溯到已知條件的通道，再從已知條

件出發(fā)，沿著這條通道回溯到問題，從而得到求解。相應(yīng)地，若將問題求解定義為一個(gè)算法，

則算法可以分解為若干個(gè)子算法，子算法再分解為更小的子子算法，直到子算法足夠簡單。

算法標(biāo)識的作用有兩點(diǎn)：

（1）作為算法定義的標(biāo)識。包括算法名、輸入數(shù)據(jù)名、輸出數(shù)據(jù)名。

（2）作為調(diào)用算法的標(biāo)識。使用算法名和輸入數(shù)據(jù)調(diào)用該算法，同時(shí)作為輸出的占位。

4.【解答】

偽代碼是注重算法結(jié)構(gòu)嚴(yán)謹(jǐn)性的算法表示方法。它借助計(jì)算機(jī)語言的控制結(jié)構(gòu)表達(dá)算法

的結(jié)構(gòu)，結(jié)合自然語言和數(shù)學(xué)符號來表示數(shù)據(jù)和操作。偽代碼具有書寫簡潔、結(jié)構(gòu)清晰、易

閱讀等優(yōu)點(diǎn)。

5.【解答】

迭代算法從一個(gè)假設(shè)的目標(biāo)值出發(fā)，計(jì)算出目標(biāo)值；再從這個(gè)目標(biāo)值出發(fā)，計(jì)算出新的

目標(biāo)值;如此不斷重復(fù)，直到目標(biāo)值符合要求為止。一個(gè)完備的迭代算法具有3個(gè)關(guān)鍵要素：

（1）確定迭代變量。一個(gè)或多個(gè)直接或間接地不斷由舊值推出新值的變量。在迭代開始前，

這些變量的值為假設(shè)值，稱為迭代初值。在循環(huán)結(jié)構(gòu)中，迭代變量初值在初始化階段完成。

（2）建立迭代式。迭代變量從舊值推出新值的計(jì)算過程。在循環(huán)控制結(jié)構(gòu)中，迭代式體現(xiàn)

1

在循環(huán)體中。

（3）迭代過程控制?？刂剖抢^續(xù)迭代還是終止迭代?？梢允枪潭ǖ牡螖?shù)，也可以用條

件來控制迭代。在循環(huán)控制結(jié)構(gòu)中，由循環(huán)條件來控制迭代過程。

6.【解答】

適合分治法求解的問題應(yīng)具有如下特點(diǎn)：

（1）可以分解為多個(gè)規(guī)模較原問題小的、性質(zhì)和原問題相同的子問題。這是可以使用分治

法求解的前提。

（2）分解出的子問題之間相互無關(guān)，不會產(chǎn)生重復(fù)計(jì)算。子問題的獨(dú)立性是分治法執(zhí)行效

率的保證。

（3）問題分解不會無休無止，即問題的規(guī)模小到一定程度就變得簡單可解。

（4）子問題的解可以合并構(gòu)成原問題的解。

7.【解答】

算法的輸出結(jié)果是13。

8.【解答】

算法的輸出結(jié)果是4。

begin

x,y<-48,28

whiley#0:

r<-xmody

x,y<-y,r

outputX

end

9.【解答】

如果x是一個(gè)升序或降序的列表，則可以使用二分查找算法來查找其中的數(shù)據(jù)元素（簡

稱key）o其基本原理是：在x的索引區(qū)間［left-right］之間查找key,left<=right,i是［left?right］

之間的值，如果x［i］Wkey,則如果key存在，只能出現(xiàn)在索引區(qū)間［left-i-1］中異或出現(xiàn)在索

引區(qū)間［i+1-right］中。如果每次取i值是［left?right］中的中間值，即i等于（left+right）/2的整

2

數(shù)商，則存在三種不同的判定：已找到、還在索引區(qū)間［left-i-1］中、還在索引區(qū)間［i+1-right］

中。如果沒找到，新的查找范圍就是索引區(qū)間［left-i-l］、［i+1-right］中的一個(gè)，故稱二分查

找；新的查找范圍只有原來范圍的一半，也稱折半查找。

10.【解答】

在算法的定義中，直接或間接出現(xiàn)算法本身，稱這樣的算法為遞歸算法。如果函數(shù)定義

中包含直接或間接調(diào)用函數(shù)自身，稱這樣的函數(shù)為遞歸函數(shù)。

遞歸定義包含2個(gè)要素：

(1)遞歸出口。結(jié)束遞歸過程的條件和結(jié)束值，遞歸出口也是問題最小規(guī)模下的求解方法。

(2)遞歸公式。一個(gè)沿著遞歸出口方向，直接或間接調(diào)用自身的函數(shù)定義，是問題非最小

規(guī)模下的遞歸求解方法。

四、應(yīng)用題

1?【解答】

步驟查找區(qū)間left值right值i值判斷

1[2,5,8,16,33,38,45,62]07316,24,數(shù)據(jù)在＞i的區(qū)間

2[33,38,45,62]47538H24,數(shù)據(jù)在＜i的區(qū)間

3[33]44433H24,數(shù)據(jù)在＜i的區(qū)間

4[]43已沒有查找區(qū)間，該數(shù)不存在

2.【解答】

1索引1012341數(shù)據(jù)元素的位置值1

0

1初始排列1825217911

1第1個(gè)相鄰比較118252179118與25的位置不交換

I第2個(gè)相鄰比較2交換位置的結(jié)果

I第3個(gè)相鄰比較|18217259|25與17交換位置的結(jié)果|

1第4個(gè)相鄰比較|18217925|25與9交換位置的結(jié)果

第1趟排序結(jié)果：18,2,17,9,25

第2趟排序結(jié)果：2,17,9,18,25

第3趟排序結(jié)果：2,9,17,18,25

第4趟排序結(jié)果：2,9,17,18,25

3.【解答】

1索引1012341數(shù)據(jù)元素的位置值1

心

1初始排列1182521791淺灰色底紋表示待排數(shù)1

1第1趟排序122518179118與2交換位置的結(jié)果

1第2趟排序I29181725|25與9交換位置的結(jié)果

1第3趟排序|29171825118與17交換位置的結(jié)果

1第4趟排序|29171825118與18交換位置的結(jié)果

3

4.【解答】

假設(shè)列表為x,x=[28,35,2,7,18],x中元素的索引值用i表示(索引值從左向右分別為

0,123,4),x中元素用x[i]表示，到目前為止求得的最小值用mini表示，求解過程如下：

步驟索引值ix[i]x[i]>mini運(yùn)算mini

0i賦初值0mini賦初值x[0],mini=28

1i值加1,i=l+l,i=l35Truemini值不變

2i值加1,i=l+l,i=22Falsemini值改變?yōu)閤[i]值,mini=2

3i值加1,i=l+l,i=37Truemini值不變

4i值加1,i=l+l,i=418Truemini值不變

求解結(jié)束，mini的值就是最小值，即2。

5.【解答】

begin

x=input#輸入一組數(shù)據(jù)defbubbleSortflistData^eginldex^ndlndex):

n=len(x)出4%^x中數(shù)據(jù)個(gè)數(shù)^begin

i=l#控制排序趟數(shù)初始化/i=beginldex

whilei<=n-l:whilei<endlndex:

x=bubbleSort(x,0,n-i)4iflistData[i]>listData[i+l]:

i=i+llistData[i]JistData[i+l]=listData[i+l]JistData[i]

outputXreturnlistData

end%nd

6.【解答】

defC(n,k):

begin

ifk=0ork=n:

return1

else：

returnC(n-l,k)+C(n-l,k-l)

end

7.【解答】

begin

n=input#輸入一個(gè)正整數(shù)，存入n

s=0#數(shù)列的和用s表示，初值為0

i=0#已經(jīng)求到i項(xiàng)的和

whilei<n:

i=i+l

s=s+1/(i*i)

outputs

end

8.【解答】

begin

n=input#輸入一個(gè)正整數(shù)，存入n

s=0#各位數(shù)的和用s表示，初值為0

m=n#已經(jīng)求到i項(xiàng)的和

whilem#0:

a=mmod10#a表示個(gè)位數(shù)符的十進(jìn)制值

4

m=m//10#移除個(gè)位數(shù)后的十進(jìn)制值

s=s+a#將數(shù)符十進(jìn)制值加入s中

outputS

end

9.【解答】

迭代求解：

(1)迭代變量：x、n、0dd為迭代變量。x,n的初始值為輸入值，odd的初值為1,表示奇

數(shù)次基的乘積。

(2)建立迭代式：如果n為奇數(shù)，則n=n?l,odd=odd*Xo如果n>0,則n=n/2,x=x*xo

(3)迭代過程控制：n#0o

算法的偽代碼表示如下：

begin

n=input

x=input

odd=1

whilen#0:

ifnmod2=1:

n=n-l

odd=odd*x

ifn>0:

n=n/2

x=x*x