《算法設(shè)計(jì)與分析》期末考試復(fù)習(xí)題庫(kù)（含答案）

PAGEPAGE1《算法設(shè)計(jì)與分析》期末考試復(fù)習(xí)題庫(kù)（含答案）一、單選題1.9n2+10n的漸近表達(dá)式是()。A、O(n2)B、O(n3)C、O(n)D、O(n4)答案：A2.使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點(diǎn)的求解方法稱為()。A、動(dòng)態(tài)規(guī)劃B、分支限界法C、貪心法D、回溯法答案：D3.回溯法搜索解空間樹時(shí),常用的兩種剪枝函數(shù)為()和限界函數(shù)。A、遞歸函數(shù)B、迭代函數(shù)C、非遞歸函數(shù)D、約束函數(shù)答案：D4.當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時(shí),最大子段和為()。A、24B、22C、20D、15答案：C5.合并排序法的基本思想是:將待排序元素分成大小大致相同的()個(gè)子集合,分別對(duì)每個(gè)子集合進(jìn)行排序,最終將排好序的子集合合并成為所要求的排好序的集合。A、4B、3C、2D、5答案：C6.采用“順序搜索法”從一個(gè)長(zhǎng)度為N的隨機(jī)分布數(shù)組中搜尋值為K的元素,以下對(duì)順序搜索法分析正確的是()。A、最佳情況、最差情況和平均情況下順序搜索法的漸進(jìn)代價(jià)都相同B、最佳情況的漸進(jìn)代價(jià)要好于最差情況和平均情況的漸進(jìn)代價(jià)C、最佳情況和平均情況的漸進(jìn)代價(jià)要好于最差情況的漸進(jìn)代價(jià)D、最佳情況的漸進(jìn)代價(jià)要好于平均情況的漸進(jìn)代價(jià)而平均情況的漸進(jìn)代價(jià)要好于最差情況的漸進(jìn)代價(jià)答案：B7.若進(jìn)隊(duì)的序列為:A,B,C,D,則出隊(duì)的序列是()。A、B,C,D,AB、A,C,B,DC、A,B,C,DD、C,B,D,A答案：C8.下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是()。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解答案：A9.階乘函數(shù)用遞歸定義intfactorial(intn){if(n==0)return1;return():}A、n?factorial(n)B、n?factorial(n-1)C、n?factorial(n-2)D、n?factorial(n+1)答案：B10.適用動(dòng)態(tài)規(guī)劃的問題必須滿足()。A、最優(yōu)化原理B、無前效性C、最優(yōu)化原理和后效性D、最優(yōu)化原理和無后效性答案：D11.算法分析中,記號(hào)O表示()。A、漸進(jìn)下界B、漸進(jìn)上界C、非緊上界D、緊漸近界答案：B12.廣度優(yōu)先是()的一種搜索方式。A、分支限界算法B、動(dòng)態(tài)規(guī)劃法C、貪心算法D、回溯算法答案：A13.下列哪個(gè)問題不能用貪心法求解()。A、哈夫曼編碼問題B、單源最短路徑問題C、0/1背包問題D、最小生成樹問題答案：C14.如果給定權(quán)值總數(shù)有n個(gè),則其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()。A、不確定B、2nC、2n+1D、2n-1答案：D15.在算法的三種情況下的復(fù)雜性中,可操作性最好且最有實(shí)際價(jià)值的是()情況下的時(shí)間復(fù)雜度。A、最好B、最壞C、平均D、以上都不正確答案：B16.采用舍伍德算法進(jìn)行查找的時(shí)間復(fù)雜度為()。A、O(1)B、O(n)C、O(n2)D、O(log2n)答案：B17.回溯法解旅行售貨員問題時(shí)的解空間樹是()。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：B18.以Bitonic旅行路線問題為例,動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為()。A、O(n)B、O(n!)C、O(n2)D、O(n3)答案：C19.采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序,故算法的時(shí)間復(fù)雜度為()。A、O(n2^n)B、O(nlogn)C、O(2^n)D、O(n)答案：B20.回溯算法是嘗試搜索算法中最為基本的一種算法,其采用了一種()的思想作為其控制結(jié)構(gòu)。A、深度優(yōu)先搜索B、廣度優(yōu)先搜索C、不能走就掉頭D、分治答案：C21.多項(xiàng)式A(n)=amn^m+…+a2n^2+a1n+a0的上界為()。A、O(n^m)B、O(n^m-1)C、O(n^m-2)D、O(a0)答案：A22.在算法的時(shí)間和空間關(guān)系上,()是決定性因素。A、時(shí)間B、空間C、兩者都是D、以上說法都不對(duì)答案：A23.()能夠求得問題的解但卻無法有效地判定解的正確性。A、數(shù)值概率算法B、蒙特卡羅算法C、拉斯維加斯算法D、舍伍得算法答案：B24.多階段決策問題就是要在可以選擇的那些策略中間選取一個(gè)()策略使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。A、最優(yōu)B、最差C、平衡D、任意答案：A25.在尋找n個(gè)元素中第k小元素問題中如快速排序算法思想運(yùn)用分治算法對(duì)n個(gè)元素進(jìn)行劃分如何選擇劃分基準(zhǔn)下面()A、隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)B、取子序列的第一個(gè)元素作為劃分基準(zhǔn)C、用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D、以上皆可行。但不同方法算法復(fù)雜度上界可能不同答案：D26.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是()。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)答案：C27.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略()。A、遞歸函數(shù)B、剪枝函數(shù)C、隨機(jī)數(shù)函數(shù)D、搜索函數(shù)答案：B28.對(duì)于舍伍德算法,下面的說法不正確的是()。A、總能求得問題的一個(gè)解B、不一定能求得問題的解C、所求得的解總是正確的D、將確定性算法引入隨機(jī)性改造成舍伍德算法,可消除或減少問題對(duì)于好壞實(shí)例間的差別答案：B29.當(dāng)一個(gè)算法的運(yùn)行時(shí)間為n2+n+1時(shí),由于n2+n+1與n2的數(shù)量級(jí)相等,則稱n2為這個(gè)算法的()。A、漸進(jìn)時(shí)間復(fù)雜度或時(shí)間復(fù)雜度B、空間復(fù)雜度C、問題規(guī)模D、輸入規(guī)模答案：A30.對(duì)于P問題和NP問題,下面的關(guān)系正確的是()。A、P類問題包含在NP類問題中B、NP類問題包含在P類問題中C、P=NPD、NP完全問題是P類問題的子集答案：A31.下面哪項(xiàng)是動(dòng)態(tài)規(guī)劃算法基本要素之一()。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、最優(yōu)子結(jié)構(gòu)答案：D32.3n2+10n的漸進(jìn)表達(dá)式為()。A、n2B、10nC、3nD、3n2答案：A33.對(duì)于數(shù)值概率算法,下面的說法不正確的是()。A、常用于數(shù)值問題的求解,得到的往往是近似解B、解的精度隨計(jì)算時(shí)間的增加而提高C、解的精度和計(jì)算時(shí)間之間沒有關(guān)系D、在很多情況下,計(jì)算出問題的精確解是不可能或沒必要答案：C34.下面程序段的時(shí)間復(fù)雜度是()。For(i=0;iFor(j=0;jA、O(n)B、O(n3)C、O(n2)D、O(n4)答案：C35.哈夫曼編碼可利用()算法實(shí)現(xiàn)。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：C36.貪心算法是一種只顧眼前的步驟,而難以顧忌全局步驟的算法,對(duì)于貪心算法表現(xiàn)出的特點(diǎn),下面說法錯(cuò)誤的是()。A、不能保證最后求得的解是最佳的,即多半是近似解。(少數(shù)問題除外)B、策略容易發(fā)現(xiàn),而且運(yùn)用簡(jiǎn)單,被廣泛應(yīng)用。C、策略單一,結(jié)果也單一。D、算法實(shí)現(xiàn)過程中,通常用到輔助算法:排序。答案：C37.應(yīng)用分治法的兩個(gè)前提是()。A、問題的可分性和解的可歸并性B、問題的可分性和解的存在性C、問題的復(fù)雜性和解的可歸并性D、問題的可分性和解的復(fù)雜性答案：A38.算法分析是()。A、將算法用某種程序設(shè)計(jì)語(yǔ)言恰當(dāng)?shù)乇硎境鰜鞡、在抽象數(shù)據(jù)集合上執(zhí)行程序,以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果C、對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析D、證明算法對(duì)所有可能的合法輸入都能算出正確的答案：C39.下列是動(dòng)態(tài)規(guī)劃算法基本要素的是()。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子空間重疊性質(zhì)答案：D40.根據(jù)排序元素所在位置的不同,排序分()。A、內(nèi)排序和外排序B、首排序和尾排序C、順序排序和逆序排序D、堆排序和棧排序答案：A41.一個(gè)遞歸算法必須包括()。A、遞歸部分B、終止條件和遞歸部分C、迭代部分D、終止條件和迭代部分答案：B42.若當(dāng)子問題之間包含公共的子子問題時(shí),則分治法要做許多不必要的工作,重復(fù)地解公共的子問題,此時(shí)一般用()法較好。A、動(dòng)態(tài)規(guī)劃B、分治C、貪心D、概率答案：A43.在對(duì)問題的解空間樹進(jìn)行搜索的方法中一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是()。A、回溯法B、分支限界法C、回溯法和分支限界法D、回溯法求解子集樹問題答案：B44.解決0/1背包問題可以使用動(dòng)態(tài)規(guī)劃,回溯法,分支限界法。其中不需要排序的是()。A、動(dòng)態(tài)規(guī)劃B、回溯法C、分支限界法D、以上3種方法都需要排序答案：A45.秦始皇吞并六國(guó)使用的遠(yuǎn)交近攻逐個(gè)擊破的連橫策略采用了以下哪種算法思想()。A、遞歸B、分治C、迭代D、模擬。答案：B46.算法分析的兩個(gè)主要方面是()。A、空間復(fù)雜度和時(shí)間復(fù)雜度B、正確性和簡(jiǎn)單性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜度和程序復(fù)雜度答案：A47.回溯法的效率不依賴于下面的哪一個(gè)因素()。A、產(chǎn)生x[k]的時(shí)間B、滿足顯約束的x[k]值的個(gè)數(shù)C、問題的解空間的形式D、計(jì)算上界函數(shù)bound的時(shí)間答案：C48.使用二分搜索算法在1000個(gè)有序元素表中搜索一個(gè)特定元素,在最壞情況下,搜索總共需要比較的次數(shù)為()。A、10B、11C、500D、1000答案：A49.分支限界法主要有()分支限界法和優(yōu)先隊(duì)列式分支限界法。A、隊(duì)列式(FIFO)B、棧式C、二叉樹式D、鏈?zhǔn)酱鸢福篈50.能夠用動(dòng)態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征(),這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件,但是如果該性質(zhì)無法滿足,動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。A、子問題的可求解性B、子問題的獨(dú)立性C、子問題的可合并性D、子問題的重疊性答案：D51.當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí),可以使用()來消除或減少問題的好壞實(shí)例間的這種差別。A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法答案：B52.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與()算法框架。A、排列樹B、二叉樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：A53.當(dāng)一個(gè)算法的空間復(fù)雜度與問題的規(guī)模n成正比時(shí),則表示為()。A、O(1)B、O(n)C、O(n?n)D、O(n2)答案：B54.對(duì)于分治法與動(dòng)態(tài)規(guī)劃法,下面的說法正確的是()。A、適合于用動(dòng)態(tài)規(guī)劃法求解的問題,經(jīng)分解得到的子問題往往是相互獨(dú)立的B、使用分治法求解的問題,經(jīng)分解得到的子問題往往不是相互獨(dú)立的C、適合于用動(dòng)態(tài)規(guī)劃法求解的問題,經(jīng)分解得到的子問題往往不是相互獨(dú)立的D、分治法可以不需要將待求解問題分成若干個(gè)子問題答案：C55.當(dāng)輸入規(guī)模為n時(shí)算法增長(zhǎng)率最小的是()。A、5nB、20log2nC、2nD、3nlog3n答案：B56.學(xué)校要舉行運(yùn)動(dòng)會(huì),請(qǐng)你設(shè)計(jì)一個(gè)能夠?qū)\(yùn)動(dòng)員分?jǐn)?shù)自動(dòng)排序的軟件,如果要設(shè)計(jì)此軟件,以下最好的方法和步驟是()。A、分析問題,編寫程序,設(shè)計(jì)算法,調(diào)試程序B、設(shè)計(jì)算法,編寫程序,提出問題,調(diào)試程序C、提出問題,設(shè)計(jì)算法,編寫程序,調(diào)試程序D、設(shè)計(jì)算法,提出問題,編寫程序,調(diào)試程序答案：C57.一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的()。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：B58.O(Pf(N))=O(f(N)),其中P是一個(gè)()。A、正的常數(shù)B、負(fù)的常數(shù)C、不確定D、以上說法都不對(duì)答案：A59.動(dòng)態(tài)規(guī)劃算法的基本要素是()。A、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B、重疊子問題性質(zhì)與貪心選擇性質(zhì)C、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D、預(yù)排序與遞歸調(diào)用答案：C60.順序查找的時(shí)間復(fù)雜度為()。A、O(n)B、O(logn)C、O(n2)D、O(nlogn)答案：A61.分支限界法的搜索策略是:在擴(kuò)展結(jié)點(diǎn)處,先生成其()兒子結(jié)點(diǎn)(分支),然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn),以加速搜索的進(jìn)程,在每一活結(jié)點(diǎn)處,計(jì)算一個(gè)函數(shù)值(限界),并根據(jù)這些已計(jì)算出的函數(shù)值,從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn),使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn),以便盡快地找出一個(gè)最優(yōu)解。A、一個(gè)B、二個(gè)C、任意多個(gè)D、所有的答案：D62.設(shè)有n項(xiàng)獨(dú)立的作業(yè){1,2,…,n},由m臺(tái)相同的機(jī)器加工處理。作業(yè)i所需要的處理時(shí)間為ti。約定:任何一項(xiàng)作業(yè)可在任何一臺(tái)機(jī)器上處理,但未完工前不準(zhǔn)中斷處理;任何作業(yè)不能拆分更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種調(diào)度方案,使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器處理完(n>m)。對(duì)于多級(jí)調(diào)度問題,使用哪種貪心策略比較合適()。A、作業(yè)從小到大依次分配給空閑的機(jī)器B、作業(yè)從大到小依次分配給空閑的機(jī)器C、每個(gè)機(jī)器分配一樣的作業(yè)數(shù)D、使用以上幾種貪心策略都能找到最優(yōu)解,所以都合適答案：B63.實(shí)現(xiàn)合并排序利用的算法是()。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：A64.快速排序算法的性能取決于()。A、劃分的對(duì)稱性B、數(shù)據(jù)的原始序列C、隨機(jī)選擇策略D、以上都不正確答案：A65.二分查找是利用()實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、分支限界法D、概率算法答案：A66.在對(duì)問題的解空間樹進(jìn)行搜索的方法中一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)的是()。A、回溯法B、分支限界法C、回溯法和分支限界法D、動(dòng)態(tài)規(guī)劃答案：A67.舍伍德算法總能求得問題的()。A、一個(gè)解B、兩個(gè)解C、三個(gè)解D、三個(gè)以上的解答案：A68.快速排序算法是基于分治策略的一個(gè)算法,其基本思想是,對(duì)于輸入的子數(shù)組a[p:r],按以下三個(gè)步驟進(jìn)行排序:()。A、分解、遞歸求解、合并B、遞歸求解、分解、合并C、合并、遞歸求解、分解D、分解、合并、遞歸求解答案：A69.下面哪個(gè)不屬于算法設(shè)計(jì)的質(zhì)量指標(biāo)()。A、正確性B、可讀性C、健壯性D、有窮性答案：D70.對(duì)于分支限界法與回溯法,下面說法錯(cuò)誤的是()。A、求解目標(biāo)不同B、搜索方式相同C、對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D、存儲(chǔ)空間的要求不同答案：B71.分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題()。A、問題規(guī)模相同,問題性質(zhì)相同B、問題規(guī)模相同,問題性質(zhì)不同C、問題規(guī)模不同,問題性質(zhì)相同D、問題規(guī)模不同,問題性質(zhì)不同答案：C72.回溯法在問題的解空間樹中,按()策略,從根節(jié)點(diǎn)出發(fā)搜索解空間樹。A、廣度優(yōu)先B、深度優(yōu)先C、隨機(jī)D、以上說法都不對(duì)答案：B73.下列序列中,()是執(zhí)行第一趟快速排序后所得的序列。A、[68,11,18,69][23,93,73]B、[68,11,69,23][18,93,73]C、[93,73][68,11,69,23,18]D、[68,11,69,23,18][93,73]答案：C74.對(duì)于0/1背包問題和背包問題的解法下面()A、0/1背包問題和背包問題都可用貪心算法求解B、0/1背包問題可用貪心算法求解但背包問題則不能用貪心算法求解C、0/1背包問題不能用貪心算法求解但可以使用動(dòng)態(tài)規(guī)劃或搜索算法求解,而背包問題則可以用貪心算法求解D、因?yàn)?/1背包問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)所以不能用貪心算法求解答案：C75.對(duì)于棧操作數(shù)據(jù)的原則是()。A、先進(jìn)先出B、后進(jìn)先出C、后進(jìn)后出D、不分順序答案：B76.下列算法中不能解決0/1背包問題的是()。A、貪心法B、動(dòng)態(tài)規(guī)劃C、回溯法D、分支限界法答案：A77.對(duì)于n個(gè)元素的排序問題。n=2時(shí)只要作()次比較即可排好序。A、3B、2C、1D、4答案：C78.對(duì)于下列算法,有時(shí)找不到問題解的是()。A、蒙特卡羅算法B、拉斯維加斯算法C、快速排序算法D、數(shù)值概率算法答案：B79.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為()。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：D80.遞歸算法不適用以下場(chǎng)合()。A、數(shù)據(jù)的定義形式按遞歸定義B、數(shù)據(jù)之間的關(guān)系即數(shù)據(jù)結(jié)構(gòu)按遞歸定義C、問題解法按遞歸算法實(shí)現(xiàn)D、概率問題答案：D81.算法與程序的區(qū)別在于算法具有()。A、能行性B、確定性C、有窮性D、輸入和輸出答案：C82.對(duì)于蒙特卡羅算法,下面的說法不正確的是()。A、蒙特卡羅算法用于求解問題的準(zhǔn)確解,且該解一定是正確的B、求得正確解的概率依賴于算法的計(jì)算時(shí)間C、多次執(zhí)行蒙特卡羅算法,可以提高獲得正確解的概率D、無法有效判定所得到的解是否肯定正確答案：A83.下列算法中通常以自頂向下的方式求解最優(yōu)解的是()。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：C84.寫出下列f(n)的漸進(jìn)性態(tài),若f(n)=3n+2,則f(n)=()。A、O(1)B、O(n)C、O(n2)D、O(n3)答案：B85.算法就是一組有窮的(),它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算。A、偽代碼B、語(yǔ)言C、代碼D、規(guī)則答案：D86.當(dāng)問題規(guī)模n趨向于無窮大時(shí),時(shí)間復(fù)雜度的數(shù)量級(jí)(階)稱為算法的()。A、平均時(shí)間復(fù)雜度B、最壞時(shí)間復(fù)雜度C、漸進(jìn)時(shí)間復(fù)雜度D、最優(yōu)時(shí)間復(fù)雜度答案：C87.下列隨機(jī)算法一定有解但解不一定正確的是()。A、SherwoodB、LasVegasC、MonteCarloD、三者都不是答案：C88.對(duì)于迭代法,下面的說法不正確的是()。A、需要確定迭代模型B、需要建立迭代關(guān)系式C、需要對(duì)迭代過程進(jìn)行控制,要考慮什么時(shí)候結(jié)束迭代過程D、不需要對(duì)迭代過程進(jìn)行控制答案：D89.一般地講,當(dāng)一個(gè)問題的所有子問題都至少要解一次時(shí),用動(dòng)態(tài)規(guī)劃算法和備忘錄算法相比:()。A、效果一樣B、動(dòng)態(tài)規(guī)劃效果好C、備忘錄方法效果好D、無法判斷哪個(gè)效果好答案：B90.當(dāng)上下限表達(dá)式相等時(shí)我們使用下列哪種表示法來描述算法代價(jià)()。A、大O表示法B、大Ω表示法C、Θ表示法D、小o表示法答案：C91.優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列,并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值p來表示。結(jié)點(diǎn)優(yōu)先級(jí)的高低與p值大小相關(guān),根據(jù)問題的不同情況,采用()來描述優(yōu)先隊(duì)列。A、先進(jìn)先出隊(duì)列B、后進(jìn)先出的棧C、最大堆或最小堆D、隨機(jī)序列答案：C92.輸入序列為ABC,可以變?yōu)镃BA時(shí),經(jīng)過的棧操作為()。A、push,pop,push,pop,push,popB、push,push,push,pop,pop,popC、push,push,pop,pop,push,popD、push,pop,push,push,pop,pop答案：B93.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分成若干()。A、遞歸問題B、子問題C、小問題D、非遞歸問題答案：B94.下面哪個(gè)不屬于算法的三要素()。A、操作B、控制結(jié)構(gòu)C、數(shù)據(jù)結(jié)構(gòu)D、程序答案：D95.當(dāng)輸入規(guī)模為n時(shí),算法增長(zhǎng)率最快的是()。A、12nB、100log2^nC、2n^2D、3nlog3^n答案：C96.下列不屬于一個(gè)好的算法應(yīng)具有的特性的是()。A、正確性B、簡(jiǎn)明性C、無限性D、最優(yōu)性答案：C97.下列哪一種算法是隨機(jī)化算法()。A、貪心算法B、回溯法C、動(dòng)態(tài)規(guī)劃算法D、舍伍德算法答案：D98.用貪心法求解背包問題時(shí),為了使收益最大化要選擇()的物品裝入背包。A、單位重量收益最大B、收益最大C、重量最大D、重量最小答案：A99.插入和刪除只能在一端進(jìn)行的線性表,稱為()。A、隊(duì)列B、循環(huán)隊(duì)列C、棧D、循環(huán)棧答案：C100.貪心方法是一種求()的方法。A、最小解B、最大解C、最優(yōu)解D、局部最優(yōu)解答案：C101.備忘錄方法是那種算法的變形()。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：B102.寫出下列f(n)的漸進(jìn)性態(tài),若f(n)=6?2n+n,則f(n)=()。A、O(1)B、O(2n)C、O(n2)D、O(n3)答案：B103.n2+10n-1的漸進(jìn)表達(dá)式為()。A、1B、2nC、n2D、n3答案：C104.對(duì)于隊(duì)列操作數(shù)據(jù)的原則是()。A、先進(jìn)先出B、后進(jìn)先出C、先進(jìn)后出D、不分順序答案：A105.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟為:(1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征。(2)()。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)計(jì)算最優(yōu)值得到的信息,構(gòu)造最優(yōu)解。A、非遞歸的定義最優(yōu)值B、遞歸的定義最優(yōu)值C、迭代的定義最優(yōu)值D、遞推的定義最優(yōu)值答案：B106.下列不是基本計(jì)算模型的是()。A、RAMB、ROMC、RASPD、TM答案：B107.有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧,則下列哪一個(gè)不是合法的出棧序列()。A、5,4,3,6,1,2B、4,5,3,1,2,6C、3,4,6,5,2,1D、2,3,4,1,5,6答案：C108.直接或間接的調(diào)用自身的算法稱為()。A、貪心算法B、遞歸算法C、迭代算法D、動(dòng)態(tài)規(guī)劃算法答案：B109.21+1/n的漸進(jìn)表達(dá)式為()。A、21B、1/nC、nD、n2答案：A110.有6個(gè)元素按6,5,4,3,2,1的順序進(jìn)棧,問下列()不是合法的出棧序列?A、543612B、453126C、346521D、234156答案：C111.用回溯法解批處理作業(yè)調(diào)度問題時(shí),該問題的解空間結(jié)構(gòu)為()結(jié)構(gòu)。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：B112.如果無向連通圖G中不包含任何關(guān)節(jié)點(diǎn),則稱該圖G為()。A、雙連通圖B、單連通圖C、強(qiáng)連通圖D、弱連通圖答案：A113.下面問題()不能使用貪心法解決。A、單源最短路徑問題B、N皇后問題C、最小花費(fèi)生成樹問題D、背包問題答案：B114.算法必須具備輸入、輸出和()等5個(gè)特性。A、可執(zhí)行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性答案：B115.活動(dòng)安排問題就是在所給的活動(dòng)集合中,選出()的相容活子集。A、最小B、任意C、最大D、一個(gè)答案：C116.算法分析中,記號(hào)Ω表示()。A、漸進(jìn)下界B、漸進(jìn)上界C、非緊上界D、緊漸近界答案：A117.通常用來表示時(shí)間算法的有以下六種多項(xiàng)式:O(1),O(n3),O(log2n),O(n2),O(n),O(nlog2n),按從小到大的順序排列是()。A、O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)B、O(1)<O(n)<O(log2n)<O(nlog2n)<O(n2)<O(n3)C、O(1)<O(log2n)<O(n)<O(n2)<O(nlog2n)<O(n3)D、O(1)<O(n)<O(log2n)<O(nlog2n)<O(n2)<O(n3)答案：A118.折半查找的時(shí)間復(fù)雜度為()。A、O(n)B、O(logn)C、O(n2)D、O(nlogn)答案：B119.二分搜索算法是利用()實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：A120.下面哪個(gè)問題不是典型的NP完全問題()。A、m-著色問題B、旅行商問題C、哈密爾頓回路問題D、排序問題答案：D121.隊(duì)列是限定在()進(jìn)行操作的線性表。A、中間B、隊(duì)首C、隊(duì)尾D、端點(diǎn)答案：D122.投點(diǎn)法是()的一種。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：B123.分支限界算法中根據(jù)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式可有幾種常用分類,以下()描述最為準(zhǔn)確。A、采用FIFO隊(duì)列的隊(duì)列式分支限界法B、采用最小值堆的優(yōu)先隊(duì)列式分支限界法C、采用最大值堆的優(yōu)先隊(duì)列式分支限界法D、以上都常用針對(duì)具體問題可以選擇采用其中某種更為合適的方式答案：D124.以下關(guān)于判定問題難易處理的敘述中正確的是()。A、可以由多項(xiàng)式時(shí)間算法求解的問題是難處理的B、需要超過多項(xiàng)式時(shí)間算法求解的問題是易處理的C、可以由多項(xiàng)式時(shí)間算法求解的問題是易處理的D、需要超過多項(xiàng)式時(shí)間算法求解的問題是不能處理的答案：C125.棧和隊(duì)列的共同點(diǎn)是()。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒有共同點(diǎn)答案：C126.()是問題能用貪婪算法或動(dòng)態(tài)規(guī)劃算法求解的前提。A、無后效性B、問題規(guī)模不能太大C、時(shí)間復(fù)雜度不能太高D、空間復(fù)雜度不能太高答案：A127.一個(gè)算法應(yīng)該包含如下幾條性質(zhì)除了()。A、二義性B、有限性C、正確性D、可終止性答案：A128.常見的兩種分支限界法為()。A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法B、隊(duì)列式(FIFO)分支限界法與堆棧式分支限界法C、排列樹法與子集樹法D、隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法答案：D129.遞歸通常用()來實(shí)現(xiàn)。A、有序的線性表B、隊(duì)列C、棧D、數(shù)組答案：C130.設(shè)A[1.60]={11,12,…,70}。算法折半查找在A上搜索x=33、7、70、77時(shí)執(zhí)行的元素比較次數(shù)分別為a、b、c、d,則()。A、<b<c<dB、a>b=c=dC、a<b=c=dD、a<c<b=d答案：C131.計(jì)算機(jī)算法指的是()。A、計(jì)算方法B、排序方法C、解決問題的方法和過程D、調(diào)度方法答案：C132.分治法所能解決的問題應(yīng)具有的最關(guān)鍵特征是()。A、該問題的規(guī)模縮小到一定的程度就可以容易地解決B、該問題可以分解為若干個(gè)規(guī)模較小的相同問題C、利用該問題分解出的子問題的解可以合并為該問題的解D、該問題所分解出的各個(gè)子問題是相互獨(dú)立的答案：C133.二分查找只適用()存儲(chǔ)結(jié)構(gòu)。A、堆B、順序C、任意次序D、棧答案：B134.FIFO是()的一搜索方式。A、分支限界法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：A135.貪心算法從初始階段開始,每一個(gè)階段總是作一個(gè)使()的貪心選擇。A、全局最優(yōu)B、局部最大C、局部最小D、局部最優(yōu)答案：D136.寫出下列f(n)的漸進(jìn)性態(tài),若f(n)=C0,C0為常數(shù),則f(n)=()。A、O(1)B、O(n)C、O(n2)D、O(n3)答案：A137.分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解,二者()。A、求解目標(biāo)不同搜索方式相同B、求解目標(biāo)不同搜索方式也不同C、求解目標(biāo)相同搜索方式不同D、求解目標(biāo)相同搜索方式也相同答案：B138.用回溯法解0/1背包問題時(shí),該問題的解空間結(jié)構(gòu)為()結(jié)構(gòu)。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：A139.下面不是分支界限法搜索方式的是()。A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先答案：D140.快速排序算法是基于()的一種排序算法。A、分治策略B、貪心C、回溯D、動(dòng)態(tài)規(guī)劃答案：A141.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟為:(1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征。(2)遞歸的定義最優(yōu)值。(3)()。(4)計(jì)算最優(yōu)值得到的信息,構(gòu)造最優(yōu)解。A、以自底向上的方式計(jì)算出最優(yōu)值B、以自頂向下的方式計(jì)算出最優(yōu)值C、迭代的方式計(jì)算出最優(yōu)值D、遞推的方式算出最優(yōu)值答案：A142.對(duì)于分支限界法與回溯法,下面說法正確的是()。A、求解目標(biāo)相同B、搜索方式相同C、對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式相同D、都是一種在問題的解空間樹中搜索問題解的算法答案：D143.我們通常說的有效算法或?qū)嶋H可行算法是指()。A、時(shí)間復(fù)雜度可以達(dá)到常數(shù)階的算法B、時(shí)間復(fù)雜度可以達(dá)到多項(xiàng)式時(shí)間的算法C、時(shí)間復(fù)雜度可以達(dá)到對(duì)數(shù)階的算法D、時(shí)間復(fù)雜度可以達(dá)到指數(shù)階的算法答案：B144.漸進(jìn)算法分析是指()。A、算法在最佳情況、最差情況和平均情況下的代價(jià)B、當(dāng)規(guī)模逐步往極限方向增大時(shí)對(duì)算法資源開銷“增長(zhǎng)率”上的簡(jiǎn)化分析C、數(shù)據(jù)結(jié)構(gòu)所占用的空間D、在最小輸入規(guī)模下算法的資源代價(jià)答案：B145.找最小生成樹的算法Kruskal的時(shí)間復(fù)雜度為()。A、O(n2)B、O(mlogn)C、O(nlogm)D、O(mlogm)答案：D146.關(guān)于0/1背包問題,以下描述正確的是()。A、可以使用貪心算法找到最優(yōu)解B、能找到多項(xiàng)式時(shí)間的有效算法C、使用教材介紹的動(dòng)態(tài)規(guī)劃方法可求解任意0/1背包問題D、對(duì)于同一背包與相同的物品,做背包問題取得的總價(jià)值一定大于等于做0/1背包問題。答案：D147.解決一個(gè)問題通常有多種方法。若說一個(gè)算法“有效”是指()。A、這個(gè)算法能在一定的時(shí)間和空間資源限制內(nèi)將問題解決B、這個(gè)算法能在人的反應(yīng)時(shí)間內(nèi)將問題解決C、這個(gè)算法比其他已知算法都更快地將問題解決D、A和C答案：D148.最長(zhǎng)公共子序列算法利用的算法是()。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：B149.分支限界法在問題的解空間樹中,按()策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A、廣度優(yōu)先B、深度優(yōu)先C、活結(jié)點(diǎn)優(yōu)先D、擴(kuò)展結(jié)點(diǎn)優(yōu)先答案：A150.遞歸算法設(shè)計(jì)的關(guān)鍵在于找出遞歸關(guān)系和()。A、初始值B、遞歸終止(邊界)條件C、遞歸方程D、遞歸函數(shù)入口答案：B151.下列各步驟的先后順序是()。①調(diào)試程序,②分析問題,③設(shè)計(jì)算法,④編寫程序。A、②③①④B、②③④①C、③②④①D、③②①④答案：B152.一個(gè)算法是對(duì)特定問題求解的一種描述,它是()。A、指令的有限序列B、程序的有限序列C、語(yǔ)句的有限序列D、代碼的有限序列答案：A153.對(duì)于拉斯維加斯算法,下面的說法不正確的是()。A、不會(huì)得到不正確的解B、有時(shí)找不到問題的解C、找到正確解的概率隨算法計(jì)算時(shí)間的增加而提高D、用同一拉斯維加斯算法對(duì)同一問題求解多次,對(duì)求解失敗的概率沒有影響答案：D154.排序趟數(shù)與原始序列有關(guān)的排序方法是()排序法。A、插入B、選擇C、冒泡D、快速答案：C155.當(dāng)問題規(guī)模n趨向于無窮大時(shí),()的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。A、空間復(fù)雜度B、時(shí)間復(fù)雜度C、冗余度D、迭代次數(shù)答案：B156.最優(yōu)裝載問題可用貪心算法求解,采用()先裝的貪心選擇策略,可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。A、重量最重者B、單位重量收益大C、重量最輕者D、收益最大答案：C157.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn),那么度為0的結(jié)點(diǎn)個(gè)數(shù)是()。A、9B、11C、15D、不確定答案：B158.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是()。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：D159.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是()。A、貪心算法B、分支限界法C、分治法D、動(dòng)態(tài)規(guī)劃算法答案：D160.在下列算法中有時(shí)找不到問題解的是()。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：B161.回溯法在解空間樹T上的搜索方式是()。A、深度優(yōu)先B、廣度優(yōu)先C、最小耗費(fèi)優(yōu)先D、活結(jié)點(diǎn)優(yōu)先答案：A162.大符號(hào)用來描述增長(zhǎng)率的下限,這個(gè)下限的階越(),結(jié)果就越有價(jià)值。A、高B、低C、和具體問題有關(guān)D、以上都不正確答案：A163.解決0/1背包問題時(shí)需要排序的方法是回溯法和()。A、動(dòng)態(tài)規(guī)劃B、分支限界法C、貪心法D、線性規(guī)劃答案：B164.算法的復(fù)雜性有空間復(fù)雜性和()復(fù)雜性之分。A、處理器復(fù)雜性B、通信復(fù)雜性C、時(shí)間復(fù)雜性D、存儲(chǔ)復(fù)雜性答案：C165.對(duì)于分支限界法,下面不屬于分支限界法搜索方式的是()。A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、層次優(yōu)先答案：D166.折半查找、合并排序、二叉樹遍歷等算法中均采用了()策略。A、動(dòng)態(tài)規(guī)劃B、回溯C、分治D、貪心選擇答案：C167.下列算法中通常以自底向上的方式求解最優(yōu)解的是()。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：B168.一個(gè)棧的輸入序列為123…n,若輸出序列的第一個(gè)元素是n,那么輸出第i()個(gè)元素是()。A、不確定B、n-i+1C、iD、n-i答案：B169.一個(gè)棧的入棧次序ABCDE,則棧的不可能的輸出序列是()。A、EDCBAB、DECBAC、DCEABD、ABCDE答案：C170.算法的時(shí)間復(fù)雜度的性能為當(dāng)n=1時(shí),f(n)=1,當(dāng)n大于等于2時(shí),f(n)=8f(3n/7),則算法的時(shí)間復(fù)雜度的階為()。A、n2B、log2nC、nD、nlog7/38答案：D171.關(guān)于回溯搜索法的介紹,下面()是不正確描述。A、回溯法有“通用解題法”之稱它可以系統(tǒng)地搜索一個(gè)問題的所有解或任意解B、回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C、回溯算法在生成解空間的任一結(jié)點(diǎn)時(shí)先判斷該結(jié)點(diǎn)是否可能包含問題的解,如果肯定不包含,則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索,逐層向祖先結(jié)點(diǎn)回溯D、回溯算法需要借助隊(duì)列這種結(jié)構(gòu)來保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑答案：D172.動(dòng)態(tài)規(guī)劃算法與貪心法的主要區(qū)別是()。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解答案：B173.考慮背包問題:n=6,M=10,V(1:6)=(15,59,21,30,60,5),W(1:6)=(1,5,2,3,6,1)。該問題的最大效益值為()。A、101B、110C、115D、120答案：C174.對(duì)于最長(zhǎng)公共子序列,下面說法錯(cuò)誤的是()。A、最長(zhǎng)公共子序列,英文縮寫為L(zhǎng)CS(LongestCommonSubsequence)。其定義是,一個(gè)序列S,如果分別是兩個(gè)或多個(gè)已知序列的子序列,且是所有符合此條件序列中最長(zhǎng)的,則S稱為已知序列的最長(zhǎng)公共子序列。B、最長(zhǎng)公共子序列是一個(gè)十分實(shí)用的問題,它可以描述兩段文字之間的“相似度”。C、最長(zhǎng)公共子串和最長(zhǎng)公共子序列是不同的D、最長(zhǎng)公共子串和最長(zhǎng)公共子序列是相同的答案：D175.最優(yōu)二叉搜索樹即是()的二叉搜索樹。A、最小平均查找時(shí)間B、最小最壞查找時(shí)間C、最小平均存儲(chǔ)空間D、最小最壞存儲(chǔ)空間答案：A176.()的基本運(yùn)算是把兩個(gè)或多個(gè)有序序列合并成一個(gè)有序序列。A、快速排序B、希爾排序C、合并排序D、堆排序答案：C177.從分治法的一般設(shè)計(jì)模式可以看出,用它設(shè)計(jì)出的程序一般是()。A、非遞歸算法B、遞歸算法C、數(shù)值算法D、非數(shù)值算法答案：B178.14+5/n+1/n2的漸進(jìn)表達(dá)式為()。A、14B、1/nC、1/n2D、5/n答案：A179.若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示,其中n的含義是()。A、問題規(guī)模B、語(yǔ)句條數(shù)C、循環(huán)層數(shù)D、函數(shù)數(shù)量答案：A180.采用廣度優(yōu)先策略搜索的算法是()。A、分支限界法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：A181.哈夫曼編碼的貪心算法所需的計(jì)算時(shí)間為()。A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)答案：B182.二分搜索算法的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半,取a[n/2]與x進(jìn)行比較:如果(),則只要在數(shù)組a的右半部繼續(xù)搜索x。A、x<a[n/2]B、x=a[n/2]C、x>a[n/2]D、x>=a[n/2]答案：C183.衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是()。A、運(yùn)行速度快B、占用空間少C、時(shí)間復(fù)雜度低D、代碼短答案：C184.分支限界法求解最大團(tuán)問題時(shí),活結(jié)點(diǎn)表的組織形式是()。A、最小堆B、最大堆C、棧D、數(shù)組答案：B185.關(guān)于回溯算法和分支限界法以下()是不正確描述。A、回溯法中每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)B、分支限界法中活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)在這些兒子結(jié)點(diǎn)中那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄其余兒子加入活結(jié)點(diǎn)表中C、回溯法采用深度優(yōu)先的結(jié)點(diǎn)生成策略D、分支限界法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先最大效益優(yōu)先的結(jié)點(diǎn)生成策略答案：A186.對(duì)于含有n個(gè)元素的子集樹問題,最壞情況下其解空間的葉結(jié)點(diǎn)數(shù)目為()。A、2n-1B、2nC、2n+1-1D、2n+1答案：B187.分支限界法與回溯法的相同點(diǎn)是:都是一種在問題的()中搜索問題解的算法。A、子集樹TB、排列樹TC、二叉搜索樹TD、解空間樹T答案：D188.背包問題的貪心算法所需的計(jì)算時(shí)間為()。A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)答案：B189.以下()不能在線性時(shí)間完成排序A、計(jì)數(shù)排序B、基數(shù)排序C、堆排序D、桶排序答案：C190.背包問題可獲得最優(yōu)解的輸入是按()。A、重量密度排序B、價(jià)值密度排序C、單位重量收益大小排序D、重量大小排序答案：B191.對(duì)于貨箱裝船問題根據(jù)貪心策略首先選擇()的貨箱然后選()的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。A、最輕次輕B、最重次重C、最輕次重D、最重次輕答案：A192.4個(gè)元素按:A,B,C,D順序連續(xù)進(jìn)隊(duì)Q,則隊(duì)尾元素是()。A、B、C、D、答案：D193.對(duì)于高級(jí)語(yǔ)言,下面的說法不正確的是()。A、高級(jí)語(yǔ)言更接近算法語(yǔ)言,易學(xué),易掌握B、高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具C、高級(jí)語(yǔ)言依賴于機(jī)器語(yǔ)言D、高級(jí)語(yǔ)言不依賴于機(jī)器語(yǔ)言答案：C194.優(yōu)先隊(duì)列通常用以下()數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。A、棧B、堆C、隊(duì)列D、二叉查找樹答案：B195.算法的復(fù)雜性是()的度量,是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。A、算法效率B、計(jì)算時(shí)間C、存儲(chǔ)空間D、運(yùn)行時(shí)間答案：A196.f(n)=O(g(n))表示當(dāng)且僅當(dāng)存在正的常數(shù)C和N0,使得對(duì)于所有的n>=N0,有()。A、f(n)<=Cg(n)B、f(n)>=Cg(n)C、f(n)>Cg(n)D、f(n)=Cg(n)答案：A197.對(duì)于動(dòng)態(tài)規(guī)劃,下面說法錯(cuò)誤的是()。A、動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支B、動(dòng)態(tài)規(guī)劃是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法C、雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題,但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃),只要人為地引進(jìn)時(shí)間因素,把它視為多階段決策過程,也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。D、動(dòng)態(tài)規(guī)劃類似搜索或數(shù)值計(jì)算那樣,具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。答案：D198.n個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水水桶有大有小水桶必須打滿水水流恒定。如下()說法不正確A、讓水桶大的人先打水可以使得每個(gè)人排隊(duì)時(shí)間之和最小B、讓水桶小的人先打水可以使得每個(gè)人排隊(duì)時(shí)間之和最小C、讓水桶小的人先打水在某個(gè)確定的時(shí)間t內(nèi)可以讓盡可能多的人打上水D、若要在盡可能短的時(shí)間內(nèi)n個(gè)人都打完水按照什么順序其實(shí)都一樣答案：A199.以下()不一定得到問題的最優(yōu)解。A、貪心算法B、回溯算法C、分支限界法D、動(dòng)態(tài)規(guī)劃法答案：A200.實(shí)現(xiàn)最大子段和利用的算法是()。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：B201.()是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：C202.二分搜索過程的算法行為可以用一棵()來描述。A、二叉排序樹B、二叉判定樹C、子集樹D、排列樹答案：B填空題1.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干（）,先求解（）,然后從這些（）的解得到原問題的解。答案：子問題|子問題|子問題2.動(dòng)態(tài)規(guī)劃算法中存儲(chǔ)子問題的解是為了（）。答案：避免重復(fù)求解子問題3.（）是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法主要區(qū)別。答案：貪心選擇性質(zhì)4.在隊(duì)列中,允許插入的一端稱為（）。答案：隊(duì)尾5.在隊(duì)列中,允許刪除的一端稱為（）。答案：隊(duì)頭6.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是.（）性質(zhì)和（）性質(zhì)。答案：最優(yōu)子結(jié)構(gòu)|重疊子問題7.如何從兩個(gè)方面評(píng)價(jià)一個(gè)算法的優(yōu)劣:（）。答案：時(shí)間復(fù)雜度、空間復(fù)雜度8.算法的復(fù)雜性有（）復(fù)雜性和（）復(fù)雜性之分。答案：時(shí)間|空間9.一個(gè)棧的輸入序列是:1,2,3則不可能的棧輸出序列是（）。答案：{312}10.遞歸是指函數(shù)（）或者（）通過一些語(yǔ)句調(diào)用自身。答案：直接|間接11.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為（）。答案：回溯法12.在有n個(gè)元素的棧中,進(jìn)棧操作的時(shí)間復(fù)雜度為（）。答案：O[1]13.二分搜索算法是利用（）算法思想設(shè)計(jì)的。答案：分治14.算法是指解決問題的（）。答案：方法或過程15.矩陣連乘問題的算法可由（）設(shè)計(jì)實(shí)現(xiàn)。答案：動(dòng)態(tài)規(guī)劃16.分支限界法主要有（）)分支限界法和（）分支限界法。答案：隊(duì)列式(FIFO|優(yōu)先隊(duì)列式17.矩陣連乘問題的算法可由（）算法設(shè)計(jì)實(shí)現(xiàn)。答案：動(dòng)態(tài)規(guī)劃18.多項(xiàng)式的上界（）。答案：為O[nm]19.算法是由若干條指令組成的有窮序列,且要滿足輸入（）、確定性和（）四條性質(zhì)。答案：,輸出|有限性20.分支限界法是一種既帶有（）又帶有（）的搜索算法。答案：系統(tǒng)性|跳躍性21.算法的“確定性”指的是組成算法的每條（）是清晰的,無歧義的。答案：指令22.貪心算法的基本要素是（）質(zhì)和