《算法設計與分析》期末考試復習題庫(含答案)1.9n2+10n的漸近表達式是()。答案：A2.使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結點的求解方法稱為()。A、動態(tài)規(guī)劃B、分支限界法C、貪心法D、回溯法答案：D3.回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為()和限界函數(shù)。A、遞歸函數(shù)B、迭代函數(shù)C、非遞歸函數(shù)D、約束函數(shù)答案：DC、算出最優(yōu)解A、n*factorial(n)A、最優(yōu)化原理B、無前效性C、最優(yōu)化原理和后效性D、最優(yōu)化原理和無后效性C、貪心算法D、回溯算法A、不確定B、排列樹19.采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大A、深度優(yōu)先搜索B、空間24.多階段決策問題就是要在可以選擇的那些策略中間選取一個()策略使在預定D、任意25.在尋找n個元素中第k小元素問題中如快速排序算法思想運用分治算法對nB、后進先出B、不一定能求得問題的解C、所求得的解總是正確的間的差別2為這個算法的()。A、漸進時間復雜度或時間復雜度B、空間復雜度B、NP類問題包含在P類問題中D、最優(yōu)子結構答案：D32.3n2+10n的漸進表達式為()。答案：A33.對于數(shù)值概率算法，下面的說法不正確的是()。A、常用于數(shù)值問題的求解，得到的往往是近似解B、解的精度隨計算時間的增加而提高C、解的精度和計算時間之間沒有關系D、在很多情況下，計算出問題的精確解是不可能或沒必要答案：C答案：C35.哈夫曼編碼可利用()算法實現(xiàn)。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：C36.貪心算法是一種只顧眼前的步驟，而難以顧忌全局步驟的算法，對于貪心算法表現(xiàn)出的特點，下面說法錯誤的是()。A、不能保證最后求得的解是最佳的，即多半是近似解。(少數(shù)問題除外)C、策略單一，結果也單一。答案：C37.應用分治法的兩個前提是()。A、問題的可分性和解的可歸并性B、問題的可分性和解的存在性C、問題的復雜性和解的可歸并性D、問題的可分性和解的復雜性答案：A38.算法分析是()。A、將算法用某種程序設計語言恰當?shù)乇硎境鰜鞡、在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會產(chǎn)生錯誤的結果C、對算法需要多少計算時間和存儲空間作定量分析D、證明算法對所有可能的合法輸入都能算出正確的A、定義最優(yōu)解C、算出最優(yōu)解B、分治C、貪心A、回溯法B、分支限界法C、回溯法和分支限界法B、回溯法D、以上3種方法都需要排序A、遞歸B、分治C、迭代D、模擬。答案：B46.算法分析的兩個主要方面是()。A、空間復雜度和時間復雜度B、正確性和簡單性C、可讀性和文檔性D、數(shù)據(jù)復雜度和程序復雜度47.回溯法的效率不依賴于下面的哪一個因素()。A、產(chǎn)生x[k]的時間B、滿足顯約束的x[k]值的個數(shù)C、問題的解空間的形式D、計算上界函數(shù)bound的時間答案：C48.使用二分搜索算法在1000個有序元素表中搜索一個特定元素，在最壞情況下，搜索總共需要比較的次數(shù)為()。答案：A50.能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征(),這個性質(zhì)并不是動態(tài)規(guī)劃A、子問題的可求解性B、子問題的獨立性C、子問題的可合并性D、子問題的重疊性51.當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜C、拉斯維加斯算法52.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與()算法框架。A、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹A、0(1)55.當輸入規(guī)模為n時算法增長率最小的是()。答案：B56.學校要舉行運動會，請你設計一個能夠對運動員分數(shù)自動排序的軟件，如果要設計此軟件，以下最好的方法和步驟是()。答案：C57.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的()。A、重疊子問題B、最優(yōu)子結構性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：BA、正的常數(shù)B、負的常數(shù)C、不確定D、以上說法都不對59.動態(tài)規(guī)劃算法的基本要素是()。A、最優(yōu)子結構性質(zhì)與貪心選擇性質(zhì)B、重疊子問題性質(zhì)與貪心選擇性質(zhì)C、最優(yōu)子結構性質(zhì)與重疊子問題性質(zhì)D、預排序與遞歸調(diào)用答案：C60.順序查找的時間復雜度為()。A、0(n)答案：A61.分支限界法的搜索策略是：在擴展結點處，先生成其()兒子結點(分支),然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數(shù)值(限界),并根據(jù)這些已計算出的函數(shù)值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。A、一個B、二個C、任意多個D、所有的答案：D62.設有n項獨立的作業(yè){1,2,…,n},由m臺相同的機器加工處理。作業(yè)i所需要的處理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但未完工前不C、貪心法D、回溯法66.在對問題的解空間樹進行搜索的方法中一個活結點有多次機會成為活結點的是()。A、回溯法B、分支限界法C、回溯法和分支限界法C、三個解D、三個以上的解C、合并、遞歸求解、分解D、分解、合并、遞歸求解答案：A69.下面哪個不屬于算法設計的質(zhì)量指標()。B、可讀性C、健壯性D、有窮性答案：D70.對于分支限界法與回溯法，下面說法錯誤的是()。A、求解目標不同B、搜索方式相同C、對擴展結點的擴展方式不同D、存儲空間的要求不同答案：B71.分治法的設計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題()。A、問題規(guī)模相同，問題性質(zhì)相同B、問題規(guī)模相同，問題性質(zhì)不同C、問題規(guī)模不同，問題性質(zhì)相同D、問題規(guī)模不同，問題性質(zhì)不同A、廣度優(yōu)先B、深度優(yōu)先D、以上說法都不對答案：B73.下列序列中，()是執(zhí)行第一趟快速排序后所得的序列。A、[68,11,18,69][23,9答案：C74.對于0/1背包問題和背包問題的解法下面()A、0/1背包問題和背包問題都可用貪心算法求解B、0/1背包問題可用貪心算法求解但背包問題則不能用貪心算法求解C、0/1背包問題不能用貪心算法求解但可以使用動態(tài)規(guī)劃或搜索算法求解，而背包問題則可以用貪心算法求解D、因為0/1背包問題不具有最優(yōu)子結構性質(zhì)所以不能用貪心算法求解答案：C75.對于棧操作數(shù)據(jù)的原則是()。A、先進先出B、后進先出C、后進后出D、不分順序76.下列算法中不能解決0/1背包問題的是()。A、貪心法C、回溯法C、貪心算法D、回溯算法B、數(shù)據(jù)之間的關系即數(shù)據(jù)結構按遞歸定義D、概率問題A、能行性B、確定性C、有窮性D、輸入和輸出D、無法有效判定所得到的解是否肯定正確A、分治法C、貪心法D、回溯法A、偽代碼B、最壞時間復雜度C、漸進時間復雜度D、最優(yōu)時間復雜度答案：C87.下列隨機算法一定有解但解不一定正確的是()。D、三者都不是答案：C88.對于迭代法，下面的說法不正確的是()。A、需要確定迭代模型B、需要建立迭代關系式C、需要對迭代過程進行控制，要考慮什么時候結束迭代過程D、不需要對迭代過程進行控制答案：D89.一般地講，當一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法和備A、效果一樣B、動態(tài)規(guī)劃效果好C、備忘錄方法效果好D、無法判斷哪個效果好答案：BA、大0表示法D、隨機序列A、push,pop,push,pop,push,A、操作B、控制結構C、數(shù)據(jù)結構A、貪心算法B、回溯法D、重量最小B、循環(huán)隊列A、最小解C、最優(yōu)解D、局部最優(yōu)解答案：C101.備忘錄方法是那種算法的變形()。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B答案：B103.n2+10n-1的漸進表達式為()。答案：C104.對于隊列操作數(shù)據(jù)的原則是()。B、后進先出C、先進后出A、RAMA、貪心算法B、遞歸算法110.有6個元素按6,5,4,3,2,1的順序進棧，問下列()不是合法的出棧序列?B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹A、單源最短路徑問題C、最小花費生成樹問題D、背包問題114.算法必須具備輸入、輸出和()等5個特性。A、可執(zhí)行性、可移植性和可擴充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性B、任意A、0(1)<0(log2n)<0(n)<0(nlog2n)<0(nC、0(1)<0(log2n)<0(n)<0(D、回溯法C、貪心算法123.分支限界算法中根據(jù)從活結點表中選擇下一擴展結點的不A、采用FIF0隊列的隊列式分支限界法B、采用最小值堆的優(yōu)先隊列式分支限界法C、采用最大值堆的優(yōu)先隊列式分支限界法D、以上都常用針對具體問題可以選擇采用其中某種更為合適的方式A、可以由多項式時間算法求解的問題是難處理的C、可以由多項式時間算法求解的問題是易處理的D、可終止性A、有序的線性表D、數(shù)組130.設A[1.60]={11,12,…,70}。算法折半查找在A上搜索x=33、7、70、77時A、計算方法B、排序方法C、解決問題的方法和過程A、該問題的規(guī)模縮小到一定的程度就可以容易地解決C、利用該問題分解出的子問題的解可以合并為該問題的解C、任意次序C、貪心法D、回溯法C、局部最小B、求解目標不同搜索方式也不同D、求解目標相同搜索方式也相同B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹A、廣度優(yōu)先D、深度優(yōu)先D、動態(tài)規(guī)劃B、搜索方式相同C、對擴展結點的擴展方式相同B、時間復雜度可以達到多項式時間的算法C、時間復雜度可以達到對數(shù)階的算法D、時間復雜度可以達到指數(shù)階的算法答案：B144.漸進算法分析是指()。A、算法在最佳情況、最差情況和平均情況下的代價B、當規(guī)模逐步往極限方向增大時對算法資源開銷“增長率”上的簡化分析C、數(shù)據(jù)結構所占用的空間D、在最小輸入規(guī)模下算法的資源代價答案：B145.找最小生成樹的算法Kruskal的時間復雜度為()。答案：D146.關于0/1背包問題，以下描述正確的是()。A、可以使用貪心算法找到最優(yōu)解B、能找到多項式時間的有效算法C、使用教材介紹的動態(tài)規(guī)劃方法可求解任意0/1背包問題D、對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做0/1背包問題。答案：DC、貪心法D、回溯法A、廣度優(yōu)先B、深度優(yōu)先A、初始值D、遞歸函數(shù)入口A、插入D、快速A、空間復雜度C、冗余度D、迭代次數(shù)B、單位重量收益大157.若一棵二叉樹具有10個度為2的結點，5個度為1的結點，那么度為0的結C、貪心法D、回溯法A、貪心算法C、分治法A、深度優(yōu)先D、活結點優(yōu)先B、低C、和具體問題有關D、以上都不正確163.解決0/1背包問題時需要排序的方法是回溯法和()。C、貪心法B、通信復雜性C、時間復雜性D、存儲復雜性A、廣度優(yōu)先B、回溯A、備忘錄法C、貪心法D、回溯法168.一個棧的輸入序列為123…n,若輸出序列的第一個元素是n,那么輸出第iC、iD、回溯算法需要借助隊列這種結構來保存從根結點到當前擴展結點的路徑答案：D172.動態(tài)規(guī)劃算法與貪心法的主要區(qū)別是()。A、最優(yōu)子結構B、貪心選擇性質(zhì)C、構造最優(yōu)解D、定義最優(yōu)解答案：B1)。該問題的最大效益值為()。答案：C174.對于最長公共子序列，下面說法錯誤的是()。一個序列S,如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則S稱為已知序列的最長公共子序列。C、最長公共子串和最長公共子序列是不同的D、最長公共子串和最長公共子序列是相同的C、貪心法D、回溯法D、數(shù)組B、分支限界法中活結點一旦成為擴展結點就兒子結點中那些導致不可行解或導致非最優(yōu)解的兒子結活結點表中B、排列樹TD、解空間樹TA、計數(shù)排序191.對于貨箱裝船問題根據(jù)貪心策略首先選擇()的貨箱然后選()的貨箱如此下答案：A196.f(n)=0(g(n))表示當且僅當存在正的常數(shù)C和NO,使得對于所有的n>=NO,有()。答案：AA、動態(tài)規(guī)劃(dynamicprogramming)是運籌學的一個分支B、動態(tài)規(guī)劃是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學方法C、雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃),只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。D、動態(tài)規(guī)劃類似搜索或數(shù)值計算那樣，具有一個標準的數(shù)學表達式和明確清晰的解題方法。答案：D198.n個人拎著水桶在一個水龍頭前面排隊打水水桶有大有小水桶必須打滿水水流恒定。如下()說法不正確A、讓水桶大的人先打水可以使得每個人排隊時間之和最小B、讓水桶小的人先打水可以使得每個人排隊時間之和最小C、讓水桶小的人先打水在某個確定的時間t內(nèi)可以讓盡可能多的人打上水C、貪心法D、回溯法1.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干(),先求解(),然后從這些()的解得到原問題的解。2.動態(tài)規(guī)劃算法中存儲子問題的解是為了()。3.()是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法主要區(qū)4.在隊列中，允許插入的一端稱為()。5.在隊列中，允許刪除的一端稱為()。6.動態(tài)規(guī)劃算法的兩個基本要素是.()性質(zhì)和()性質(zhì)。7.如何從兩個方面評價一個算法的優(yōu)劣：()。8.算法的復雜性有()復雜性和()復雜性之分。答案：時間|空間9.一個棧的輸入序列是：1,2,3則不可能的棧輸出序列是()。答案：{312}10.遞歸是指函數(shù)()或者()通過一些語句調(diào)用自身。答案：直接|間接11.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為()。答案：回溯法12.在有n個元素的棧中，進棧操作的時間復雜度為()。答案：0[1]13.二分搜索算法是利用()算法思想設計的。答案：分治14.算法是指解決問題的()。答案：方法或過程15.矩陣連乘問題的算法可由()設計實現(xiàn)。答案：動態(tài)規(guī)劃16.分支限界法主要有())分支限界法和()分支限界法。答案：隊列式(FIFO|優(yōu)先隊列式17.矩陣連乘問題的算法可由()算法設計實現(xiàn)。答案：動態(tài)規(guī)劃答案：為0[nm]19.算法是由若干條指令組成的有窮序列，且要滿足輸入()、確定性和()四條20.分支限界法是一種既帶有()又帶有()的搜索算法。21.算法的“確定性”指的是組成算法的每條()是清晰的，無歧義的。22.貪心算法的基本要素是()質(zhì)和()性質(zhì)。23.計算下面算法的時間復雜度記為：()。24.合并排序算法使用的是()算法設計的思想。25.問題的()是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。26.回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為()和()。的是(),需要排序的是(),()。28.已知順序棧S,在對S進行進棧操作之前首先要判斷()。答案：棧是否滿29.大整數(shù)乘積算法是用()來設計的。30.計算機的資源最重要的是()和()資源.因而，算法的復雜性有()和()31.以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為()。32.計算下面算法的時間復雜度記為：()。?33.在快速排序、插入排序和合并排序算法中，()算法不是分治算34.算法運行所需要的計算機資源的量，稱為算法復雜性，主要包括()和()。35.()是被限定為只能在表的一端進行插入36.()是問題能用動態(tài)規(guī)劃算法求解的前提。37.若進棧的次序是A,B,C,D,E,執(zhí)行3次出棧操作以后，棧頂元素為()。39.回溯法是一種既帶有()又帶有()的搜索算法。40.從分治法的一般設計模式可以看出，用它設計出的程