中級軟.件設(shè)計師單項選擇考試卷模擬考試題

1、姓名：_ 班級：_ 學(xué)號：_-密-封 -線- 中級軟.件設(shè)計師單項選擇考試卷模擬考試題考試時間：120分鐘 考試總分：100分題號一二三四五總分分?jǐn)?shù)遵守考場紀(jì)律，維護知識尊嚴(yán)，杜絕違紀(jì)行為，確?？荚嚱Y(jié)果公正。1、拉斯維加斯(las vegas)算法是一種常用的（ ）算法。 （ ）a.確定性b.近似c.概率d.加密2、用遞歸算法實現(xiàn)n個相異元素構(gòu)成的有序序列的二分查找，采用一個遞歸工作棧時，該棧的最小容量應(yīng)為（ ）a.nb.n/2c.log2nd.log2(n+1)3、快速排序算法采用的設(shè)計方法是（ ）a.動態(tài)規(guī)劃法(dynamic programming)b.分治法(divideand con

2、quer)c.回溯法(backtracking)d.分枝定界法(branch and bound)4、采用動態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是（ ）a.當(dāng)前所作出的決策不會影響后面的決策b.原問題的最優(yōu)解包含其子問題的最優(yōu)解c.問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解d.每次決策必須是當(dāng)前看來最優(yōu)的決策才可以找到最優(yōu)解5、在分支限界算法設(shè)計策略中，通常采用（ ）搜索問題的解空間。 （ ）a.深度優(yōu)先b.廣度優(yōu)先c.自底向上d.拓?fù)湫蛄?、下面的程序段違反了算法的（ ）原則。void sam（ ）int n=2;while(!odd(n)n+=2printf(n);（

3、）a.有窮性b.確定性c.可行性d.健壯性7、貪婪法是一種（ ）的算法。 （ ）a.不求最優(yōu)，只求滿意b.只求最優(yōu)c.求取全部可行解d.求取全部最優(yōu)解8、利用動態(tài)規(guī)劃法求解每對節(jié)點之間的最短路徑問題時，設(shè)有向圖g=v，e共有n個節(jié)點，節(jié)點編號1n，設(shè)c是g的成本鄰接矩陣，用dk(i,j)表示從i到j(luò)并且不經(jīng)過編號比k還大的節(jié)點的最短路徑的長度(dn(i,j)即為圖g中節(jié)點i到j(luò)的最短路徑長度)，則求解該問題的遞推關(guān)系式為（ ）a.dk(i,j)=dk-1(i,j)+c(i,j)b.dk(i,j)=mindk-1(i,j),dk-1(i,j)+c(i,j)c.dk(i,j)=dk-1(i,k)+

4、dk-1(k,j)d.dk(i,j)=mindk-1(i,j),dk-1(i,k)+dk-1(k,j)9、算法是對問題求解過程的一類精確描述，算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本操作在限定時間內(nèi)執(zhí)行有限次來實現(xiàn)的，這句話說明算法具有（ ）特性。 （ ）a.正確性b.確定性c.可行性d.健壯性10、設(shè)某算法的計算時間可用遞推關(guān)系式t（n）=2t（n/2）+n表示，則該算法的時間復(fù)雜度為（ ）a.o(lgn)b.o(nlgn)c.o(n)d.o(n2)11、用迭代法求解方程x5-x-1=0，下列迭代公式不可能正確的是（ ）。 （ ）a.ab.bc.cd.d12、利用貪心法求解0/1背包問題時

5、，(26)能夠確保獲得最優(yōu)解。用動態(tài)規(guī)劃方求解o/1背包問題時，將“用前i個物品來裝容量是x的背包”的0/1背包問題記為knap(1，i，x)設(shè)fi(x)是knap(1，i，x)最優(yōu)解的效益值，第j個物品的重量和放入背包后取得效益值分別為w和p(j=1n)，則依次求解f0(x)，f1(x)，fn(x)的過程中使用的遞推關(guān)系式為(27)。（26）處填（ ）a.優(yōu)先選取重量最小的物品b.優(yōu)先選取效益最大的物品c.優(yōu)先選取單位重量效益最大的物品d.沒有任何準(zhǔn)則13、利用貪心法求解0/1背包問題時，(26)能夠確保獲得最優(yōu)解。用動態(tài)規(guī)劃方求解o/1背包問題時，將“用前i個物品來裝容量是x的背包”的0/

6、1背包問題記為knap(1，i，x)設(shè)fi(x)是knap(1，i，x)最優(yōu)解的效益值，第j個物品的重量和放入背包后取得效益值分別為w和p(j=1n)，則依次求解f0(x)，f1(x)，fn(x)的過程中使用的遞推關(guān)系式為(27)。（27）處填（ ）a.fi(x)=minfi-1(x),fi-1(x)+pib.fi(x)=maxfi-1(x),fi-1(x-wi)+pic.fi(x)=minfi-1(x-wi),fi-1(x-wi)+pi)d.fi(x)=maxfi-1(x-wi),fi-1(x)+pi14、設(shè)求解某問題的遞歸算法如下：f(int n)if n=1move(1)elsef(n-

7、1)；move(n)；f(n-1)；求解該算法的計算時間時，僅考慮算法move所做的計算為主要計算，且move為常數(shù)級算法。則算法f的計算時間t(n)的遞推關(guān)系式為(9)；設(shè)算法move的計算時間為k，當(dāng) n=4時，算法f的計算時間為(10)。（9）處填（ ）a.t(n)=t(n-1)+1b.t(n)=2t(n-1)c.t(n)=2t(n-1)+1d.t(n)=2t(n+1)+115、設(shè)求解某問題的遞歸算法如下：f(int n)if n=1move(1)elsef(n-1)；move(n)；f(n-1)；求解該算法的計算時間時，僅考慮算法move所做的計算為主要計算，且move為常數(shù)級算法。則

8、算法f的計算時間t(n)的遞推關(guān)系式為(9)；設(shè)算法move的計算時間為k，當(dāng) n=4時，算法f的計算時間為(10)。（10）處填（ ）a.14kb.15kc.16kd.17k16、在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼(huffman)算法可以用來構(gòu)造具有(18)的二叉樹，這是一種采用了(19)的算法。（18）處填（ ）a.前綴碼b.最優(yōu)前綴碼c.后綴碼d.最優(yōu)后綴碼17、在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼(huffman)算法可以用來構(gòu)造具有(18)的二叉樹，這是一種采用了(19)的算法。（19）處填（ ）a.貪心b.分治c.遞推d.回溯18、在下面所列舉的邏輯測試覆蓋中，測試覆蓋最強的是(12)，最

9、弱的是(13)。（12）處填（ ）a.條件覆蓋b.條件組合覆蓋c.語句覆蓋d.判定及條件覆蓋19、在下面所列舉的邏輯測試覆蓋中，測試覆蓋最強的是(12)，最弱的是(13)。（13）處填（ ）a.條件覆蓋b.條件組合覆蓋c.語句覆蓋d.判定及條件覆蓋20、在下列算法設(shè)計方法中，(16)在求解問題的過程中并不從整體最優(yōu)上加以考慮，而是作出在當(dāng)前看來是最好的選擇。利用該設(shè)計方法可以解決(17)問題。（16）處填（ ）a.分治法b.貪心法c.動態(tài)規(guī)劃法d.回溯法21、在下列算法設(shè)計方法中，(16)在求解問題的過程中并不從整體最優(yōu)上加以考慮，而是作出在當(dāng)前看來是最好的選擇。利用該設(shè)計方法可以解決(17)

10、問題。（17）處填（ ）a.排序b.檢索c.背包d.0/1背包22、最小碼字之間的海明距離是一個碼字要變成另一個碼字時必須改變的最小位數(shù)。如果任意碼字之間的最小海明距離是d，則所有少于等于(28)位的錯誤都可以檢查出來，所有少于(29)位的錯誤都可以糾正。（28）處填（ ）a.d-1b.d-2c.d+1d.d/223、最小碼字之間的海明距離是一個碼字要變成另一個碼字時必須改變的最小位數(shù)。如果任意碼字之間的最小海明距離是d，則所有少于等于(28)位的錯誤都可以檢查出來，所有少于(29)位的錯誤都可以糾正。（29）處填（ ）a.d-1b.d-2c.d+1d.d/224、遞歸算法的執(zhí)行過程，一般來說

11、，可先后分成(12)和(13)兩個階段。（12）處填（ ）a.試探b.遞推c.枚舉d.分析25、遞歸算法的執(zhí)行過程，一般來說，可先后分成(12)和(13)兩個階段。（13）處填（ ）a.回溯b.回歸c.返回d.合成26、以關(guān)鍵字比較為基礎(chǔ)的排序算法在最壞情況下的計算時間下界為o(nlogn)。下面的排序算法中，最壞情況下計算時間可以達(dá)到o(nlogn)的是(21)，該算法采用的設(shè)計方法是(22)。（21）處填（ ）a.歸并排序b.插入排序c.選擇排序d.冒泡排序27、以關(guān)鍵字比較為基礎(chǔ)的排序算法在最壞情況下的計算時間下界為o(nlogn)。下面的排序算法中，最壞情況下計算時間可以達(dá)到o(nlogn)的是(21)，該算法采用的設(shè)計方法是(22)。（22）處填（ ）a.分治法b.貪心法c.動態(tài)規(guī)劃方法d.回溯法28、若一個問題的求解既可以用