1、 模擬 軟件設(shè)計(jì)師算法設(shè)計(jì)和分析選擇題第 1 題：給定一組長(zhǎng)度為 n 的無(wú)序序列，將其存儲(chǔ)在一維數(shù)組 a0.n-1 中?，F(xiàn)采用如 下方法找出其中的最大元素和最小元素：比較 a0 和 an-1 ，若 a0 較大， 則將二者的值進(jìn)行交換；再比較 a1 和 an-2 ，若 a1 較大，則交換二者的 值；然后依次比較 a2 和 an-3 、 a3 和 an-4 、. ，使得每一對(duì)元素中的 較小者被交換到低下標(biāo)端。重復(fù)上述方法，在數(shù)組的前 n/2 個(gè)元素中查找最小 元素，在后 n/2 個(gè)元素查找最大元素，從而得到整個(gè)序列的最小元素和最大元 素。上述方法采用的算法設(shè)計(jì)策略是 。A. 動(dòng)態(tài)規(guī)劃法B. 貪心法

2、C. 分治法D. 回溯法參考答案： CT(n)=T(n-1)+n(n 0)及 T(0)=1 ，則該第 2 題： 設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式 算法的時(shí)間復(fù)雜度為 。A. O(lgn)B. O(nlgn)C. O(n)D. O(n²)參考答案： D第 3 題：一個(gè)算法是對(duì)某類給定問(wèn)題求解過(guò)程的精確描述，算法中描述的操作都可以通過(guò)將已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)，這句話說(shuō)明算法具有 特性。A. 有窮性B. 可行性C. 確定性D. 健壯性參考答案： B斐波那契 (Fibonacci) 數(shù)列可以遞歸地定義為：用遞歸算法求解 F(5) 時(shí)需要執(zhí)行

3、(4) 次“+”運(yùn)算， 該方法采用的算法 策略是 (5) 。第 4 題：A. 5B. 6C. 7D. 8參考答案： C第 5 題：A. 動(dòng)態(tài)規(guī)劃B. 分治C. 回溯D. 分支限界參考答案： B第 6 題： 若總是以待排序列的第一個(gè)元素作為基準(zhǔn)元素進(jìn)行快速排序，那么最好情況下 的時(shí)間復(fù)雜度為 。A. O(log₂n)B. O(n)C. O(nlog₂n)D. O(n²)參考答案： C第 7 題：某算法的時(shí)間復(fù)雜度可用遞歸式 表示，若用表示該算法的漸進(jìn)時(shí)間復(fù)雜度

4、的緊致界， 則正確的是A.B.C.D.參考答案： B第 8 題： 用動(dòng)態(tài)規(guī)劃策略求解矩陣連乘問(wèn)題 M₁*M₂*M₃*M₄，其中 M₁(20*5) 、M₂(5*35) 、M₃(35*4) 和 M₄(4*25) ，則最優(yōu)的計(jì)算次序?yàn)?。

5、A. (M₁*M₂)*M₃)*M₄B. (M₁*M₂)*(M₃*M₄)C. (M₁*(M₂*M₃

6、;)*M₄D. M₁*(M₂*(M₃3*M₄)參考答案： C第 9 題：下面 C 程序段中 count+ 語(yǔ)句執(zhí)行的次數(shù)為 for (int i=1; i =11; i*=2) for(int j=1 ；j =i ； j+) count+;A. 15B. 16C. 31D. 32參考答案： A第 10 題：不能保證求得 0-1 背包問(wèn)題的最優(yōu)解A. 分支限界法B. 貪

7、心算法C. 回溯法D. 動(dòng)態(tài)規(guī)劃策略參考答案： B第 11 題：若某算法在問(wèn)題規(guī)模為 n 時(shí)，其基本操作的重復(fù)次數(shù)可由下式表示，則該算法 的時(shí)間復(fù)雜度為 。A. O(n)B. O(n²)C. O(log₂n)D. O(nlog₂n)參考答案： B第 12 題：若對(duì)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則采用僅設(shè)尾指 針的單向循環(huán)鏈表 (不含頭結(jié)點(diǎn) ) 時(shí)， 。A. 插入和刪除操作的時(shí)間復(fù)雜度都為 O(1)B. 插入和刪除操作的時(shí)間復(fù)雜度都為 O(

8、n)C. 插入操作的時(shí)間復(fù)雜度為 O(1) ，刪除操作的時(shí)間復(fù)雜度為 O(n)D. 插入操作的時(shí)間復(fù)雜度為 O(n) ，刪除操作的時(shí)間復(fù)雜度為 O(1) 參考答案： C第 13 題：某算法的時(shí)間復(fù)雜度表達(dá)式為 T(n)=an²+bnlgn+cn+d ，其中， n 為 問(wèn)題的規(guī)模， a、b、c和 d為常數(shù)，用 O表示其漸近時(shí)間復(fù)雜度為 。A. O(n²)B. O(n)C. O(nlgn)D. O(1)參考答案： A第 14 題：現(xiàn)有 16 枚外形相同的硬幣，其中有一枚比真幣的重量輕的假幣，若采用分治法 找出這枚假幣，至少比較 次才能夠找出該假幣。A. 3B. 4C. 5D