贏在大學(xué)領(lǐng)英工程整理匯編—算法試卷

《贏在大學(xué)領(lǐng)英工程整理匯編—算法試卷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、B卷（視頻中只有判斷題部分）一．判斷題：1.算法分析，我們更關(guān)注算法的空間效率問題。2．在很多情況下，數(shù)據(jù)結(jié)構(gòu)的設(shè)計直接影響基于該結(jié)構(gòu)之上設(shè)計的時間性能。3.算法可以采用自然語言、流程圖、偽代碼等多種方式來描述。4.不是所有的問題都可以用計算機來求解。5.問題規(guī)?？梢杂绊懰惴ǖ膱?zhí)行時間。6..P類問題是NP問題的子集。7.分治法和動態(tài)規(guī)劃都將待求解問題分解成若干個子問題。8.貪心法的典型應(yīng)用是求解最優(yōu)化問題。9.回溯法問題的解空間樹是虛擬的，并不需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)。10.分支限界法是一種有組織的系統(tǒng)化搜索技術(shù)。11.減治法分解出來的子問題不需要分別求解，只需求解其中的

2、一個子問題。A卷一．判斷題：1.算法研究核心問題是時間（速度）問題。2.算法是程序別名。3.算法只能采用偽代碼來描述。4.現(xiàn)實生活中只要有足夠的時間和空間，所有的問題都可以用計算機解決。5.要評估一個算法的時間效率必須要該算法的執(zhí)行時間。6.NP完全問題是NP類問題的子類。7.在用分治設(shè)計算法時，最好是各子問題之間相互獨立。8.作為一種算法設(shè)計技術(shù)，貪心法是一種簡單有效的方法。9.回溯法每次只能構(gòu)造可能解的一部分。10.回溯法就是一種有組織的系統(tǒng)化的搜索技術(shù)。11.一個問題用貪心法求解時只會有一種貪心法策略。二．單項選擇題：1.設(shè)函數(shù)f（n）和g（n）是定義在非負整數(shù)集合上的正函數(shù)，如

3、果存在兩個正常數(shù)c和n0，使得當n≧n0時，有f（n）≦cg（n），則記做（A）A．f(n)=O(g(n))B.f(n)=Ω(g(n))第一小題和08屆卷子的單項選擇第一小題一樣。2.蠻力法所依賴的基本技術(shù)是（）A．掃描技術(shù)B.查找技術(shù)C．分治技術(shù)D.動態(tài)規(guī)劃3.基于比較的排序算法的時間復(fù)雜度下界為（）A．Ω（n）B.Ω（n2）C．Ω（nlogn）D.視頻太模糊，看不清楚此選項4.下列哪個問題是NP完全問題（）A．停機問題B.圖著色問題C．最小生成樹問題D.八皇后問題5.快速排序算法是利用（）實現(xiàn)的算法。A．分治策略B.動態(tài)規(guī)劃C．貪心法D.回溯法6.通過貪心法必定可以求得下列哪個問題

4、的最優(yōu)解（）A．圖著色問題B.最小生成樹問題C．多機調(diào)度問題D.TSP問題7.用動態(tài)規(guī)劃法求解的問題除了能夠分解為相互重疊的子問題外，還需要滿足（）A．最優(yōu)先問題B.最優(yōu)量度問題C．目標函數(shù)D.貪心規(guī)劃8.以下哪種方法要將待求解的問題分解成若干子問題（）A.分治法B.貪心法C．回溯法D.分支限界法9.以下哪個函數(shù)是間接函數(shù)（）A．遞歸函數(shù)B.階乘函數(shù)C．約束函數(shù)D.__函數(shù)（視頻太模糊，看不清楚此選項）10.回溯法按（）遍歷問題的解空間樹。A．深度優(yōu)先策略B.廣度優(yōu)先策略C.最小耗費優(yōu)先D.隨機搜索11.（A）可以用多項式時間的確定性算法來進行判定和求解。A．P類問題B.NP類問題C．

5、NP完全問題D.子集和問題三．按照漸近階從低到高的順序排列以下表達式。4n2，logn，3n，20n，2，n，n！（此題只能看個大概的內(nèi)容）四．算法填空1.n皇后問題的片段在書本P174第一處空白：while（x[k]<=n&&(1)）填寫內(nèi)容為：!Place(k)第二、三處空白：elseif（x[k]<=n&&k

6、(4);S[i][j]=1;}elseif(L[i][j-1]>=L[i-1][j]){(5);S[i][j]=2;}空白（4）填寫:L[i][j]=L[i-1][j-1]+1空白（5）填寫：L[i][j]=L[i][j-1]五．簡答題（A卷B卷的綜合）1.什么是算法，它有哪些重要的特性？2.分治算法的求解過程？（分治算法的基本思想和分割原則？）3.應(yīng)用動態(tài)規(guī)劃思想有哪些步驟及其設(shè)計思想？（動態(tài)規(guī)劃的基本要素？）