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

（50）A.while循環語句的執行效率比do-while循環語句的執行效率高

B.while循環語句的循環體執行次數比循環條件的判斷次數多1，而do-while語句的循環體執行次數比循環條件的判斷次數少1

C.while語句的循環體執行次數比循環條件的判斷次數少1，而do-while語句的循環體執行次數比循環條件的判斷次數多1

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

（62）A.分治B.貪心C.動態規劃D.回溯B●對n個元素的數組進行（63），其平均時間復雜度和最壞情況下的時間復雜度都是O(nlogn)。

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

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

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

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

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

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

（60）A．插入排序B．歸并排序C．快速排序D．堆排序A05下●設求解某問題的遞歸算法如下：求解該算法的計算時間時,僅考慮算法Move所做的計算為主要計算,且Move為常數級算法。則算法F的計算時間T(n)的遞推關系式為____(53)____；設算法Move的計算時間為k，當n=4時，算法F的計算時間為___(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背包問題時，___(55)___能夠確保獲得最優解。用動態規劃方法求解0/1背包問題時，將“用前i個物品來裝容量是X的背包”的0/1背包問題記為KNAP(1,i,X),設fi(X)是KNAP(1,i,X)最優解的效益值，第j個物品的重量和放入背包后取得效益值分別為Wj和pj(j=1~n)。則依次求解f0(X)、f1(X)、...、fn(X)的過程中使用的遞推關系式為___(56)___。

供選擇的答案：

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

C.優先選取單位重量效益最大的物品D.沒有任何準則

(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上●在最好和最壞的情況下的時間復雜度均為O(nlogn)且穩定的排序方法是___(51)__。

供選擇的答案：

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

供選擇的答案：

A．O(n)B．O(n)C．O(log2n)D．O(nlog2n)D●利用動態規劃方法求解每對結點之間的最短路徑問題(allpairsshortestpathproblem)時，設有向圖G=<V，E>共有n個結點，結點編號1～n，設C是G的成本鄰接矩陣，用Dk(i，j)即為圖G中結點i到j并且不經過編號比k還大的結點的最短路徑的長度（Dk(i，j)即為圖G中結點i到j的最短路徑長度），則求解該問題的遞推關系式為___(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下●采用動態規劃策略求解問題的顯著特征是滿足最優性原理，其含義是__(52)__

（52）A.當前所出的決策不會影響后面的決策

B.原問題的最優解包含其子問題的最優解

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

D.每次決策必須是當前看來最優決策才可以找到最優解B●下面函數中漸進時間最小的是__(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●在分支-界限算法設計策略中，通常采用__(56)__搜索問題的解空間。

（56）A.深度優先B.廣度優先C.自底向上D.拓撲排序B●在下列算法設計方法中，__(57)__在求解為題的過程中并不從整體最優上加以考慮，而是做出在當前看來是最好的選擇。利用該設計方法可以解決__(58)__問題

（57）A.分治法B.貪心法C.動態規劃法D.回溯法

（58）A