北京航空航天大學(xué)算法導(dǎo)論期末參考題有一部分考到了

1、一、選擇題1 .算法分析中,記號(hào)O表示(B),記號(hào)標(biāo)售(A),記號(hào)6)表示(D)A漸進(jìn)下界B漸進(jìn)上界C非緊上界D緊漸進(jìn)界E非緊下界2 .以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有：(A)A f(n)=0(g(n),g(n)=0(h(n)? f(n) =6) (h(n)B f(n) =O(g(n),g(n) =O(h(n)? h(n) =O(f(n)C O(f(n)+O(g(n) = O(minf(n),g(n)D f(n) = O(g(n)? g(n) = O(f(n)3 .記號(hào)O的定義正確的選項(xiàng)是(A).A O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有nAn0有：0< f(n) &

2、lt; cg(n) ;B O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有nAn0有：0wcg(n) < f(n) ;C O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有 nAm有：0 < f(n)<cg(n) ;D O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有 nnnO 有：0 < cg(n) < f(n) ;4 .記號(hào)的定義正確的選項(xiàng)是(B).A O(g(n) = f(n) |存在正常數(shù)c和n.使得對(duì)所有nn有：0< f(n) < cg(n)

3、;B O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有nAn0有：0< cg(n) < f(n) ;C (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n()>0使 得對(duì)所有 nAn.有：0 <f(n)<cg(n) ;D (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n.>0使 得對(duì)所有 nnno 有：0 < cg(n) < f(n) ;5. T (n)表示當(dāng)輸入規(guī)模為n時(shí)的算法效率,以下算法效率最優(yōu)的 是(C )A T (n) = T (n - 1 ) +1, T (1) =1B T (n)

4、= 2n 2C T (n) = T (n/2 ) +1, T (1) =1D T (n) = 3nlog2n6 .動(dòng)態(tài)規(guī)劃算法的根本要素為(C)A最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D預(yù)排序與遞歸調(diào)用7 .以下不是動(dòng)態(tài)規(guī)劃算法根本步驟的是( A ).A找出最優(yōu)解的性質(zhì)B 構(gòu)造最優(yōu)解C算出最優(yōu)解D定義最優(yōu)解8 .能采用貪心算法求最優(yōu)解的問題,一般具有的重要性質(zhì)為：(A)A最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D預(yù)排序與遞歸調(diào)用9 .下面是貪心算法的根本要素的是C .A重疊子問題B構(gòu)造最優(yōu)解C

5、貪心選擇性質(zhì)D定義最優(yōu)解10 D 是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn).A重疊子問題B 構(gòu)造最優(yōu)解C貪心選擇性質(zhì)D最優(yōu)子結(jié)構(gòu)性質(zhì)11 .使用分治法求解不需要滿足的條件是A oA子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用相同的方法解12 .實(shí)現(xiàn)循環(huán)賽日程表利用的算法是A oA分治策略 B動(dòng)態(tài)規(guī)劃法C貪心法 D 回溯法13 .使用分治法求解不需要滿足的條件是A oA子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用相同的方法解14 .以下算法中不能解決0/1背包問題的是A A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法15 .以下C 不能不能在線性時(shí)

6、間完成排序A計(jì)數(shù)排序B基數(shù)排序 C 堆排序D 桶排序16 .以下哪一種算法是隨機(jī)化算法 D A貪心算法B回溯法C 動(dòng)態(tài)規(guī)劃算法 D 舍伍德算法17 .以下算法中通常以自底向上的方式求解最優(yōu)解的A分治法 B動(dòng)態(tài)規(guī)劃法C 貪心法 D 回溯法18 . n個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水,水桶有大有小,水桶必須打滿水,水流恒定.如下(A )說法不正確 AA讓水桶大的人先打水,可以使得每個(gè)人排隊(duì)時(shí)間之和最小B讓水桶小的人先打水,可以使得每個(gè)人排隊(duì)時(shí)間之和最小C讓水桶小的人先打水,在某個(gè)確定的時(shí)間t內(nèi),可以讓盡可能多的 人打上水D假設(shè)要在盡可能短的時(shí)間內(nèi),n個(gè)人都打完水,根據(jù)什么順序其實(shí)都 一樣19

7、.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為 ( B ).A O(n2n)B O(nlogn) C O(2n) D O(n)20 .下面關(guān)于NP問題說法正確的選項(xiàng)是(B )A NP問題都是不可能解決的問題B P類問題包含在NP類問題中C NP完全問題是P類問題的子集D NP類問題包含在P類問題中21 .背包問題貪心算法所需的計(jì)算時(shí)間為(B )A O(n2n)B O(nlogn)C O(2n)D O(n)22 .背包問題的回溯算法所需的計(jì)算時(shí)間為(A )A O(n2n)B O(nlogn)C O(2n)D O(n)23 .采用最大效益優(yōu)先搜索方式的算法是(A )A分支界限發(fā)B動(dòng)態(tài)規(guī)劃法C 貪心法 D

8、回溯法24 .在棋盤覆蓋問題中,對(duì)于2kx 2k的特殊棋盤有一個(gè)特殊方塊,所需的L型骨牌的個(gè)數(shù)是 A A 4k - 1/3 B 2k /3 C 4k D 2k25 .以下隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是 C A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法26 .實(shí)現(xiàn)大整數(shù)的乘法是利用的算法 C .A貪心法 B 動(dòng)態(tài)規(guī)劃法 C分治策略D回溯法二、填空題1 .算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分.2 .矩陣連乘問題的算法可由動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn).3 .從分治法的一般設(shè)計(jì)模式可以看出,用它設(shè)計(jì)出的程序一般是遞歸算法 .4 .算法是由假設(shè)干條指令組成的有窮序列,且要滿足輸入、輸出、確定 性和有限性四條件質(zhì).5 .快速排序算法的性能取決于劃分的對(duì)稱性 .6 .使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素,在最正確 情況下,搜索的時(shí)間復(fù)雜性為 01,在最壞情況下,搜索的時(shí)間 復(fù)雜性為0 logn °三、解做題1 .給定已按升序排好序的n個(gè)元素a0:n-1,現(xiàn)要在這n個(gè)元素中 找出一特定元素x,返回其在數(shù)組中的位置,如果未找到返回-1.寫 出二分搜索的算法,并