歷年算法試題(上午)

優(yōu)秀學(xué)習(xí)資料歡迎下載優(yōu)秀學(xué)習(xí)資料歡迎下載優(yōu)秀學(xué)習(xí)資料歡迎下載10下●某一維數(shù)組中依次存放了數(shù)據(jù)元素15,23,38,47,55,62,88,95,102,123，采用折半（二分）法查找元素95時(shí)，依次與（60）進(jìn)行了比較。（60）A.62,88,95B.62,95C.55,88,95D.55,95DAC10上DCBC09下ADA09年上午●現(xiàn)有16枚外形相同的硬幣，其中有一枚比真幣的重量輕的假幣，若采用分治法找出這枚假幣，至少比較（63）次才能夠找出該假幣。（63）A.3B.4C.5D.6B●以下的算法設(shè)計(jì)方法中，（64）以獲取問題最優(yōu)解為目標(biāo)。（64）A.回溯方法B.分治法C.動(dòng)態(tài)規(guī)劃D.遞推C●歸并排序采用的算法設(shè)計(jì)方法屬于（65）。（65）A.歸納法B.分治法C.貪心法D.回溯方法B08年下●程序設(shè)計(jì)語言一般都提供多種循環(huán)語句，例如實(shí)現(xiàn)先判斷循環(huán)條件再執(zhí)行循環(huán)體的while語句和先執(zhí)行循環(huán)體再判斷循環(huán)條件的do-while語句。關(guān)于這兩種循環(huán)語句，在不改變循環(huán)體的條件下，（21）是正確的。（21）A.while語句的功能可由do-while語句實(shí)現(xiàn)B.do-while語句的功能可由while語句實(shí)現(xiàn)C.若已知循環(huán)體的次數(shù)，則只能使用while語句D.循環(huán)條件相同時(shí)，do-while語句的執(zhí)行效率更高B●某一維數(shù)組中依次存放了數(shù)據(jù)元素12,23,30,38,41,52,54,76,85，在用折半（二分）查找方法（向上取整）查找元素54時(shí)，所經(jīng)歷“比較”運(yùn)算的數(shù)據(jù)元素依次為（62）（62）A.41,52,54B.41,76,54C.41,76,52,54D.41,30,76,54BDCD08年上●一個(gè)算法是對某類給定問題求解過程的精確描述，算法中描述的操作都可以通過將已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)，這句話說明算法具有（62）特性。（62）A.有窮性B.可行性C.確定性D.健壯性BCBC07年下●關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，（64）是正確的。（64）A.算法的實(shí)現(xiàn)依賴于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)B.算法的效率與數(shù)據(jù)結(jié)構(gòu)無關(guān)C.數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，算法的效率越高D.數(shù)據(jù)結(jié)構(gòu)越簡單，算法的效率越高A●若一個(gè)問題既可以用迭代方式也可以用遞歸方式求解，則（65）方法具有更高的時(shí)空效率。（65）A.迭代 B.遞歸 C.先遞歸后迭代 D.先迭代后遞歸A07年上●程序設(shè)計(jì)語言中（50）。

（50）A.while循環(huán)語句的執(zhí)行效率比do-while循環(huán)語句的執(zhí)行效率高

B.while循環(huán)語句的循環(huán)體執(zhí)行次數(shù)比循環(huán)條件的判斷次數(shù)多1，而do-while語句的循環(huán)體執(zhí)行次數(shù)比循環(huán)條件的判斷次數(shù)少1

C.while語句的循環(huán)體執(zhí)行次數(shù)比循環(huán)條件的判斷次數(shù)少1，而do-while語句的循環(huán)體執(zhí)行次數(shù)比循環(huán)條件的判斷次數(shù)多1

D.while語句的循環(huán)體執(zhí)行次數(shù)比循環(huán)條件的判斷次數(shù)少1，而do-while語句的循環(huán)體執(zhí)行次數(shù)等于循環(huán)條件的判斷次數(shù)D●設(shè)商店有10元、5元、2元和1元的零幣，每種零幣的數(shù)量充足。售貨員給顧客找零錢時(shí)，零幣的數(shù)量越少越好。例如給顧客找零29元：先選2張10元幣，然后選擇1張5元幣，再選擇兩張2元幣。以上的找零錢方法采用了（62）策略。

（62）A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.回溯B●對n個(gè)元素的數(shù)組進(jìn)行（63），其平均時(shí)間復(fù)雜度和最壞情況下的時(shí)間復(fù)雜度都是O(nlogn)。

（63）A.希爾排序B.快速排序C.堆排序D.選擇排序C06年下●（58）算法策略與遞歸技術(shù)的聯(lián)系最弱。

（58）A．動(dòng)態(tài)規(guī)劃B．貪心C．回溯D．分治B●對于具有n個(gè)元素的一個(gè)數(shù)據(jù)序列，若只需得到其中第k個(gè)元素之前的部分排序，最好采用（59），使用分治(DivideandConquer)策略的是（60）算法。

（59）A．希爾排序B．直接插入排序C．快速排序D．堆排序

（60）A．冒泡排序B．插入排序C．快速排序D．堆排序DC06上●設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式T（n）＝2T（n／2）＋n表示，則該算法的時(shí)間復(fù)雜度為（59）。

（59）A．O（lgn）B．O（nlgn）C．O（n）D．O（n2）

B●（60）在其最好情況下的算法時(shí)間復(fù)雜度為O(n)。

（60）A．插入排序B．歸并排序C．快速排序D．堆排序A05下●設(shè)求解某問題的遞歸算法如下：求解該算法的計(jì)算時(shí)間時(shí),僅考慮算法Move所做的計(jì)算為主要計(jì)算,且Move為常數(shù)級算法。則算法F的計(jì)算時(shí)間T(n)的遞推關(guān)系式為____(53)____；設(shè)算法Move的計(jì)算時(shí)間為k，當(dāng)n=4時(shí)，算法F的計(jì)算時(shí)間為___(54)___。

供選擇的答案：

（53）A.T(n)=T(n-1)+1B.T(n)=2T(n-1)

C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1

（54)A.14kB.15kC.16kD.17kCB●利用貪心法求解0/1背包問題時(shí)，___(55)___能夠確保獲得最優(yōu)解。用動(dòng)態(tài)規(guī)劃方法求解0/1背包問題時(shí)，將“用前i個(gè)物品來裝容量是X的背包”的0/1背包問題記為KNAP(1,i,X),設(shè)fi(X)是KNAP(1,i,X)最優(yōu)解的效益值，第j個(gè)物品的重量和放入背包后取得效益值分別為Wj和pj(j=1~n)。則依次求解f0(X)、f1(X)、...、fn(X)的過程中使用的遞推關(guān)系式為___(56)___。

供選擇的答案：

(55)A.優(yōu)先選取重量最小的物品B.優(yōu)先選取效益最大的物品

C.優(yōu)先選取單位重量效益最大的物品D.沒有任何準(zhǔn)則

(56)A.fi(X)=min{fi-1(X),fi-1(X)+pi}

B.fi(X)=max{fi-1(X),fi-1(X-Wi)+pi}

C.fi(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi}

D.fi(X)=max{fi-1(X-Wi),fi-1(X)+pi}DB05上●在最好和最壞的情況下的時(shí)間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法是___(51)__。

供選擇的答案：

A．基數(shù)排序B．快速排序C．堆排序D．歸并排序C●以比較為基礎(chǔ)的排序算法在最壞情況下的計(jì)算時(shí)間下界為__(55)___。

供選擇的答案：

A．O(n)B．O(n)C．O(log2n)D．O(nlog2n)D●利用動(dòng)態(tài)規(guī)劃方法求解每對結(jié)點(diǎn)之間的最短路徑問題(allpairsshortestpathproblem)時(shí)，設(shè)有向圖G=<V，E>共有n個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)編號1～n，設(shè)C是G的成本鄰接矩陣，用Dk(i，j)即為圖G中結(jié)點(diǎn)i到j(luò)并且不經(jīng)過編號比k還大的結(jié)點(diǎn)的最短路徑的長度（Dk(i，j)即為圖G中結(jié)點(diǎn)i到j(luò)的最短路徑長度），則求解該問題的遞推關(guān)系式為___(56)___。

供選擇的答案：

A.Dk(i，j)=Dk-1(i，j)+C(i，j)

B.Dk(i，j)=min{Dk-1(i，j)，Dk-1(i，j)+C(i，j)}

C.Dk(i，j)=Dk-1(i，k)+Dk-1(k，j)

D.Dk(i，j)=min{Dk-1(i，j)，Dk-1(i，k)+Dk-1(k，j)}D04下●采用動(dòng)態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是__(52)__

（52）A.當(dāng)前所出的決策不會影響后面的決策

B.原問題的最優(yōu)解包含其子問題的最優(yōu)解

C.問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解

D.每次決策必須是當(dāng)前看來最優(yōu)決策才可以找到最優(yōu)解B●下面函數(shù)中漸進(jìn)時(shí)間最小的是__(53)__

(53)A.T1(n)=n+nlognB.T2(n)=2n+nLognC.T3(n)=n2-lognD.T4(n)=n+100lognD●下面的程序段違反了算法的__(54)__原則

voidsam()

{

intn=2

while(!odd(n))n+=2;

printf(n);

}

(54)A.有窮性B.確定性C.可行性D.健壯性A●拉斯維加斯（LasVegas）算法是一種常用的__(55)__算法

(55)A.確定性B.近似C.概率D.加密C●在分支-界限算法設(shè)計(jì)策略中，通常采用__(56)__搜索問題的解空間。

（56）A.深度優(yōu)先B.廣度優(yōu)先C.自底向上D.拓?fù)渑判駼●在下列算法設(shè)計(jì)方法中，__(57)__在求解為題的過程中并不從整體最優(yōu)上加以考慮，而是做出在當(dāng)前看來是最好的選擇。利用該設(shè)計(jì)方法可以解決__(58)__問題

（57）A.分治法B.貪心法C.動(dòng)態(tài)規(guī)劃法D.回溯法

（58）A