中級(jí)軟.件設(shè)計(jì)師單項(xiàng)選擇考試卷模擬考試題

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

2、quer)c.回溯法(backtracking)d.分枝定界法(branch and bound)4、采用動(dòng)態(tài)規(guī)劃策略求解問(wèn)題的顯著特征是滿(mǎn)足最優(yōu)性原理，其含義是（ ）a.當(dāng)前所作出的決策不會(huì)影響后面的決策b.原問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解c.問(wèn)題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解d.每次決策必須是當(dāng)前看來(lái)最優(yōu)的決策才可以找到最優(yōu)解5、在分支限界算法設(shè)計(jì)策略中，通常采用（ ）搜索問(wèn)題的解空間。 （ ）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)，只求滿(mǎn)意b.只求最優(yōu)c.求取全部可行解d.求取全部最優(yōu)解8、利用動(dòng)態(tài)規(guī)劃法求解每對(duì)節(jié)點(diǎn)之間的最短路徑問(wèn)題時(shí)，設(shè)有向圖g=v，e共有n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)1n，設(shè)c是g的成本鄰接矩陣，用dk(i,j)表示從i到j(luò)并且不經(jīng)過(guò)編號(hào)比k還大的節(jié)點(diǎn)的最短路徑的長(zhǎng)度(dn(i,j)即為圖g中節(jié)點(diǎn)i到j(luò)的最短路徑長(zhǎng)度)，則求解該問(wèn)題的遞推關(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、算法是對(duì)問(wèn)題求解過(guò)程的一類(lèi)精確描述，算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作在限定時(shí)間內(nèi)執(zhí)行有限次來(lái)實(shí)現(xiàn)的，這句話(huà)說(shuō)明算法具有（ ）特性。 （ ）a.正確性b.確定性c.可行性d.健壯性10、設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式t（n）=2t（n/2）+n表示，則該算法的時(shí)間復(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背包問(wèn)題時(shí)

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

6、1背包問(wèn)題記為knap(1，i，x)設(shè)fi(x)是knap(1，i，x)最優(yōu)解的效益值，第j個(gè)物品的重量和放入背包后取得效益值分別為w和p(j=1n)，則依次求解f0(x)，f1(x)，fn(x)的過(guò)程中使用的遞推關(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è)求解某問(wèn)題的遞歸算法如下：f(int n)if n=1move(1)elsef(n-

7、1)；move(n)；f(n-1)；求解該算法的計(jì)算時(shí)間時(shí)，僅考慮算法move所做的計(jì)算為主要計(jì)算，且move為常數(shù)級(jí)算法。則算法f的計(jì)算時(shí)間t(n)的遞推關(guān)系式為(9)；設(shè)算法move的計(jì)算時(shí)間為k，當(dāng) n=4時(shí)，算法f的計(jì)算時(shí)間為(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è)求解某問(wèn)題的遞歸算法如下：f(int n)if n=1move(1)elsef(n-1)；move(n)；f(n-1)；求解該算法的計(jì)算時(shí)間時(shí)，僅考慮算法move所做的計(jì)算為主要計(jì)算，且move為常數(shù)級(jí)算法。則

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

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

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

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