《算法設(shè)計與分析》期末考試題庫及答案

PAGEPAGE1《算法設(shè)計與分析》期末考試題庫及答案一、單選題1.設(shè)有n項獨立的作業(yè){1,2,…,n},由m臺相同的機器加工處理。作業(yè)i所需要的處理時間為ti。約定:任何一項作業(yè)可在任何一臺機器上處理,但未完工前不準中斷處理;任何作業(yè)不能拆分更小的子作業(yè)。多機調(diào)度問題要求給出一種調(diào)度方案,使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器處理完(n>m)。對于多級調(diào)度問題,使用哪種貪心策略比較合適()。A、作業(yè)從小到大依次分配給空閑的機器B、作業(yè)從大到小依次分配給空閑的機器C、每個機器分配一樣的作業(yè)數(shù)D、使用以上幾種貪心策略都能找到最優(yōu)解,所以都合適答案：B2.最長公共子序列算法利用的算法是()。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B3.對于最長公共子序列,下面說法錯誤的是()。A、最長公共子序列,英文縮寫為LCS(LongestmonSubsequence)。其定義是,一個序列S,如果分別是兩個或多個已知序列的子序列,且是所有符合此條件序列中最長的,則S稱為已知序列的最長公共子序列。B、最長公共子序列是一個十分實用的問題,它可以描述兩段文字之間的“相似度”。C、最長公共子串和最長公共子序列是不同的D、最長公共子串和最長公共子序列是相同的答案：D4.21+1/n的漸進表達式為()。A、21B、1/nC、nD、n2答案：A5.()的基本運算是把兩個或多個有序序列合并成一個有序序列。A、快速排序B、希爾排序C、合并排序D、堆排序答案：C6.寫出下列f(n)的漸進性態(tài),若f(n)=6?2n+n,則f(n)=()。A、O(1)B、O(2n)C、O(n2)D、O(n3)答案：B7.考慮背包問題: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答案：C8.根據(jù)排序元素所在位置的不同,排序分()。A、內(nèi)排序和外排序B、首排序和尾排序C、順序排序和逆序排序D、堆排序和棧排序答案：A9.對于蒙特卡羅算法,下面的說法不正確的是()。A、蒙特卡羅算法用于求解問題的準確解,且該解一定是正確的B、求得正確解的概率依賴于算法的計算時間C、多次執(zhí)行蒙特卡羅算法,可以提高獲得正確解的概率D、無法有效判定所得到的解是否肯定正確答案：A10.回溯法的效率不依賴于下面的哪一個因素()。A、產(chǎn)生x[k]的時間B、滿足顯約束的x[k]值的個數(shù)C、問題的解空間的形式D、計算上界函數(shù)bound的時間答案：C11.設(shè)A[1..60]={11,12,…,70}。算法折半查找在A上搜索x=33、7、70、77時執(zhí)行的元素比較次數(shù)分別為a、b、c、d,則()。A、<b<c<dB、a>b=c=dC、a<b=c=dD、a<c<b=d答案：C12.用回溯法解批處理作業(yè)調(diào)度問題時,該問題的解空間結(jié)構(gòu)為()結(jié)構(gòu)。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：B13.對于含有n個元素的子集樹問題,最壞情況下其解空間的葉結(jié)點數(shù)目為()。A、2n-1B、2nC、2n+1-1D、2n+1答案：B14.對于舍伍德算法,下面的說法不正確的是()。A、總能求得問題的一個解B、不一定能求得問題的解C、所求得的解總是正確的D、將確定性算法引入隨機性改造成舍伍德算法,可消除或減少問題對于好壞實例間的差別答案：B15.下列算法中不能解決0/1背包問題的是()。A、貪心法B、動態(tài)規(guī)劃C、回溯法D、分支限界法答案：A16.當問題規(guī)模n趨向于無窮大時,()的數(shù)量級(階)稱為算法的漸進時間復(fù)雜度。A、空間復(fù)雜度B、時間復(fù)雜度C、冗余度D、迭代次數(shù)答案：B17.優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是()。A、先進先出B、后進先出C、結(jié)點的優(yōu)先級D、隨機答案：C18.當問題規(guī)模n趨向于無窮大時,時間復(fù)雜度的數(shù)量級(階)稱為算法的()。A、平均時間復(fù)雜度B、最壞時間復(fù)雜度C、漸進時間復(fù)雜度D、最優(yōu)時間復(fù)雜度答案：C19.常見的兩種分支限界法為()。A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法B、隊列式(FIFO)分支限界法與堆棧式分支限界法C、排列樹法與子集樹法D、隊列式(FIFO)分支限界法與優(yōu)先隊列式分支限界法答案：D20.當輸入規(guī)模為n時,算法增長率最快的是()。A、12nB、100log2^nC、2n^2D、3nlog3^n答案：C21.當上下限表達式相等時我們使用下列哪種表示法來描述算法代價()。A、大O表示法B、大Ω表示法C、Θ表示法D、小o表示法答案：C22.對于分支限界法與回溯法,下面說法錯誤的是()。A、求解目標不同B、搜索方式相同C、對擴展結(jié)點的擴展方式不同D、存儲空間的要求不同答案：B23.對于貨箱裝船問題根據(jù)貪心策略首先選擇()的貨箱然后選()的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。A、最輕次輕B、最重次重C、最輕次重D、最重次輕答案：A24.下列各步驟的先后順序是()。①調(diào)試程序,②分析問題,③設(shè)計算法,④編寫程序。A、②③①④B、②③④①C、③②④①D、③②①④答案：B25.下面程序段的時間復(fù)雜度是()。For(i=0;iFor(j=0;jA、O(n)B、O(n3)C、O(n2)D、O(n4)答案：C26.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的()。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：B27.以下()不能在線性時間完成排序A、計數(shù)排序B、基數(shù)排序C、堆排序D、桶排序答案：C28.二分搜索算法的基本思想是將n個元素分成個數(shù)大致相同的兩半,取a[n/2]與x進行比較:如果(),則只要在數(shù)組a的右半部繼續(xù)搜索x。A、x<a[n/2]B、x=a[n/2]C、x>a[n/2]D、x>=a[n/2]答案：C29.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是()。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：D30.下列序列中,()是執(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]答案：C31.O(Pf(N))=O(f(N)),其中P是一個()。A、正的常數(shù)B、負的常數(shù)C、不確定D、以上說法都不對答案：A32.遞歸算法設(shè)計的關(guān)鍵在于找出遞歸關(guān)系和()。A、初始值B、遞歸終止(邊界)條件C、遞歸方程D、遞歸函數(shù)入口答案：B33.一個棧的輸入序列為123…n,若輸出序列的第一個元素是n,那么輸出第i()個元素是()。A、不確定B、n-i+1C、iD、n-i答案：B34.一般地講,當一個問題的所有子問題都至少要解一次時,用動態(tài)規(guī)劃算法和備忘錄算法相比:()。A、效果一樣B、動態(tài)規(guī)劃效果好C、備忘錄方法效果好D、無法判斷哪個效果好答案：B35.下列隨機算法一定有解但解不一定正確的是()。A、SherwoodB、LasVegasC、MonteCarloD、三者都不是答案：C36.對于高級語言,下面的說法不正確的是()。A、高級語言更接近算法語言,易學(xué),易掌握B、高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具C、高級語言依賴于機器語言D、高級語言不依賴于機器語言答案：C37.當一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時,可以使用()來消除或減少問題的好壞實例間的這種差別。A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法答案：B38.快速排序算法是基于分治策略的一個算法,其基本思想是,對于輸入的子數(shù)組a[p:r],按以下三個步驟進行排序:()。A、分解、遞歸求解、合并B、遞歸求解、分解、合并C、合并、遞歸求解、分解D、分解、合并、遞歸求解答案：A39.在對問題的解空間樹進行搜索的方法中一個活結(jié)點有多次機會成為活結(jié)點的是()。A、回溯法B、分支限界法C、回溯法和分支限界法D、動態(tài)規(guī)劃答案：A40.采用“順序搜索法”從一個長度為N的隨機分布數(shù)組中搜尋值為K的元素,以下對順序搜索法分析正確的是()。A、最佳情況、最差情況和平均情況下順序搜索法的漸進代價都相同B、最佳情況的漸進代價要好于最差情況和平均情況的漸進代價C、最佳情況和平均情況的漸進代價要好于最差情況的漸進代價D、最佳情況的漸進代價要好于平均情況的漸進代價而平均情況的漸進代價要好于最差情況的漸進代價答案：B41.若當子問題之間包含公共的子子問題時,則分治法要做許多不必要的工作,重復(fù)地解公共的子問題,此時一般用()法較好。A、動態(tài)規(guī)劃B、分治C、貪心D、概率答案：A42.回溯算法是嘗試搜索算法中最為基本的一種算法,其采用了一種()的思想作為其控制結(jié)構(gòu)。A、深度優(yōu)先搜索B、廣度優(yōu)先搜索C、不能走就掉頭D、分治答案：C43.對于動態(tài)規(guī)劃,下面說法錯誤的是()。A、動態(tài)規(guī)劃(dynamicprogramming)是運籌學(xué)的一個分支B、動態(tài)規(guī)劃是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法C、雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題,但是一些與時間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃),只要人為地引進時間因素,把它視為多階段決策過程,也可以用動態(tài)規(guī)劃方法方便地求解。D、動態(tài)規(guī)劃類似搜索或數(shù)值計算那樣,具有一個標準的數(shù)學(xué)表達式和明確清晰的解題方法。答案：D44.4個元素按:A,B,C,D順序連續(xù)進隊Q,則隊尾元素是()。A、B、C、D、答案：D45.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為()。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：D46.n個人拎著水桶在一個水龍頭前面排隊打水水桶有大有小水桶必須打滿水水流恒定。如下()說法不正確A、讓水桶大的人先打水可以使得每個人排隊時間之和最小B、讓水桶小的人先打水可以使得每個人排隊時間之和最小C、讓水桶小的人先打水在某個確定的時間t內(nèi)可以讓盡可能多的人打上水D、若要在盡可能短的時間內(nèi)n個人都打完水按照什么順序其實都一樣答案：A47.對于0/1背包問題和背包問題的解法下面()A、0/1背包問題和背包問題都可用貪心算法求解B、0/1背包問題可用貪心算法求解但背包問題則不能用貪心算法求解C、0/1背包問題不能用貪心算法求解但可以使用動態(tài)規(guī)劃或搜索算法求解,而背包問題則可以用貪心算法求解D、因為0/1背包問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)所以不能用貪心算法求解答案：C48.哈夫曼編碼可利用()算法實現(xiàn)。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：C49.折半查找、合并排序、二叉樹遍歷等算法中均采用了()策略。A、動態(tài)規(guī)劃B、回溯C、分治D、貪心選擇答案：C50.遞歸算法不適用以下場合()。A、數(shù)據(jù)的定義形式按遞歸定義B、數(shù)據(jù)之間的關(guān)系即數(shù)據(jù)結(jié)構(gòu)按遞歸定義C、問題解法按遞歸算法實現(xiàn)D、概率問題答案：D51.解決0/1背包問題可以使用動態(tài)規(guī)劃,回溯法,分支限界法。其中不需要排序的是()。A、動態(tài)規(guī)劃B、回溯法C、分支限界法D、以上3種方法都需要排序答案：A52.回溯法的效率不依賴于下列哪些因素()。A、滿足顯約束的值的個數(shù)B、計算約束函數(shù)的時間C、計算限界函數(shù)的時間D、確定解空間的時間答案：D53.若進隊的序列為:A,B,C,D,則出隊的序列是()。A、B,C,D,AB、A,C,B,DC、A,B,C,DD、C,B,D,A答案：C54.在下列算法中有時找不到問題解的是()。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：B55.在算法的時間和空間關(guān)系上,()是決定性因素。A、時間B、空間C、兩者都是D、以上說法都不對答案：A56.二分查找是利用()實現(xiàn)的算法。A、分治策略B、動態(tài)規(guī)劃法C、分支限界法D、概率算法答案：A57.以下()不一定得到問題的最優(yōu)解。A、貪心算法B、回溯算法C、分支限界法D、動態(tài)規(guī)劃法答案：A58.學(xué)校要舉行運動會,請你設(shè)計一個能夠?qū)\動員分數(shù)自動排序的軟件,如果要設(shè)計此軟件,以下最好的方法和步驟是()。A、分析問題,編寫程序,設(shè)計算法,調(diào)試程序B、設(shè)計算法,編寫程序,提出問題,調(diào)試程序C、提出問題,設(shè)計算法,編寫程序,調(diào)試程序D、設(shè)計算法,提出問題,編寫程序,調(diào)試程序答案：C59.采用舍伍德算法進行查找的時間復(fù)雜度為()。A、O(1)B、O(n)C、O(n2)D、O(log2n)答案：B60.設(shè)有一個順序棧S,元素A,B,C,D,E,F,依次進棧,如果6個元素出棧的順序是B,D,C,F,E,A,則棧的容量至少應(yīng)是()。A、3B、4C、5D、6答案：A61.回溯法解旅行售貨員問題時的解空間樹是()。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：B62.衡量一個算法好壞的標準是()。A、運行速度快B、占用空間少C、時間復(fù)雜度低D、代碼短答案：C63.下列不是動態(tài)規(guī)劃算法基本步驟的是()。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解答案：A64.下面哪個不屬于算法設(shè)計的質(zhì)量指標()。A、正確性B、可讀性C、健壯性D、有窮性答案：D65.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與()算法框架。A、排列樹B、二叉樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：A66.使用二分搜索算法在1000個有序元素表中搜索一個特定元素,在最壞情況下,搜索總共需要比較的次數(shù)為()。A、10B、11C、500D、1000答案：A67.對于隊列操作數(shù)據(jù)的原則是()。A、先進先出B、后進先出C、先進后出D、不分順序答案：A68.采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序,故算法的時間復(fù)雜度為()。A、O(n2^n)B、O(nlogn)C、O(2^n)D、O(n)答案：B69.最優(yōu)二叉搜索樹即是()的二叉搜索樹。A、最小平均查找時間B、最小最壞查找時間C、最小平均存儲空間D、最小最壞存儲空間答案：A70.對于棧操作數(shù)據(jù)的原則是()。A、先進先出B、后進先出C、后進后出D、不分順序答案：B71.合并排序法的基本思想是:將待排序元素分成大小大致相同的()個子集合,分別對每個子集合進行排序,最終將排好序的子集合合并成為所要求的排好序的集合。A、4B、3C、2D、5答案：C72.二分搜索算法是利用()實現(xiàn)的算法。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：A73.排序趟數(shù)與原始序列有關(guān)的排序方法是()排序法。A、插入B、選擇C、冒泡D、快速答案：C74.在算法的三種情況下的復(fù)雜性中,可操作性最好且最有實際價值的是()情況下的時間復(fù)雜度。A、最好B、最壞C、平均D、以上都不正確答案：B75.能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征(),這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件,但是如果該性質(zhì)無法滿足,動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。A、子問題的可求解性B、子問題的獨立性C、子問題的可合并性D、子問題的重疊性答案：D76.關(guān)于0/1背包問題,以下描述正確的是()。A、可以使用貪心算法找到最優(yōu)解B、能找到多項式時間的有效算法C、使用教材介紹的動態(tài)規(guī)劃方法可求解任意0/1背包問題D、對于同一背包與相同的物品,做背包問題取得的總價值一定大于等于做0/1背包問題。答案：D77.一個遞歸算法必須包括()。A、遞歸部分B、終止條件和遞歸部分C、迭代部分D、終止條件和迭代部分答案：B78.寫出下列f(n)的漸進性態(tài),若f(n)=3n+2,則f(n)=()。A、O(1)B、O(n)C、O(n2)D、O(n3)答案：B79.算法分析中,記號Ω表示()。A、漸進下界B、漸進上界C、非緊上界D、緊漸近界答案：A80.下列不是基本計算模型的是()。A、RAMB、ROMC、RASPD、TM答案：B81.算法的復(fù)雜性有空間復(fù)雜性和()復(fù)雜性之分。A、處理器復(fù)雜性B、通信復(fù)雜性C、時間復(fù)雜性D、存儲復(fù)雜性答案：C82.輸入序列為ABC,可以變?yōu)镃BA時,經(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答案：B83.直接或間接的調(diào)用自身的算法稱為()。A、貪心算法B、遞歸算法C、迭代算法D、動態(tài)規(guī)劃算法答案：B84.在對問題的解空間樹進行搜索的方法中一個活結(jié)點最多有一次機會成為活結(jié)點的是()。A、回溯法B、分支限界法C、回溯法和分支限界法D、回溯法求解子集樹問題答案：B85.算法分析中,記號O表示()。A、漸進下界B、漸進上界C、非緊上界D、緊漸近界答案：B86.下列算法中通常以自底向上的方式求解最優(yōu)解的是()。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B87.當一個算法的空間復(fù)雜度與問題的規(guī)模n成正比時,則表示為()。A、O(1)B、O(n)C、O(n?n)D、O(n2)答案：B88.下面哪項是動態(tài)規(guī)劃算法基本要素之一()。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、最優(yōu)子結(jié)構(gòu)答案：D89.貪心算法從初始階段開始,每一個階段總是作一個使()的貪心選擇。A、全局最優(yōu)B、局部最大C、局部最小D、局部最優(yōu)答案：D90.多階段決策問題就是要在可以選擇的那些策略中間選取一個()策略使在預(yù)定的標準下達到最好的效果。A、最優(yōu)B、最差C、平衡D、任意答案：A91.動態(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)用答案：C92.動態(tài)規(guī)劃算法的基本思想是將待求解問題分成若干()。A、遞歸問題B、子問題C、小問題D、非遞歸問題答案：B93.算法必須具備輸入、輸出和()等5個特性。A、可執(zhí)行性、可移植性和可擴充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性答案：B94.()是問題能用貪婪算法或動態(tài)規(guī)劃算法求解的前提。A、無后效性B、問題規(guī)模不能太大C、時間復(fù)雜度不能太高D、空間復(fù)雜度不能太高答案：A95.設(shè)計動態(tài)規(guī)劃算法的步驟為:(1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征。(2)()。(3)以自底向上的方式計算出最優(yōu)值。(4)計算最優(yōu)值得到的信息,構(gòu)造最優(yōu)解。A、非遞歸的定義最優(yōu)值B、遞歸的定義最優(yōu)值C、迭代的定義最優(yōu)值D、遞推的定義最優(yōu)值答案：B96.采用廣度優(yōu)先策略搜索的算法是()。A、分支限界法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：A97.9n2+10n的漸近表達式是()。A、O(n2)B、O(n3)C、O(n)D、O(n4)答案：A98.如果給定權(quán)值總數(shù)有n個,則其哈夫曼樹的結(jié)點總數(shù)為()。A、不確定B、2nC、2n+1D、2n-1答案：D99.背包問題的貪心算法所需的計算時間為()。A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)答案：B100.3n2+10n的漸進表達式為()。A、n2B、10nC、3nD、3n2答案：A101.實現(xiàn)合并排序利用的算法是()。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：A102.舍伍德算法是()的一種。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：B103.下面問題()不能使用貪心法解決。A、單源最短路徑問題B、N皇后問題C、最小花費生成樹問題D、背包問題答案：B104.解決一個問題通常有多種方法。若說一個算法“有效”是指()。A、這個算法能在一定的時間和空間資源限制內(nèi)將問題解決B、這個算法能在人的反應(yīng)時間內(nèi)將問題解決C、這個算法比其他已知算法都更快地將問題解決D、A和C答案：D105.從分治法的一般設(shè)計模式可以看出,用它設(shè)計出的程序一般是()。A、非遞歸算法B、遞歸算法C、數(shù)值算法D、非數(shù)值算法答案：B106.算法的時間復(fù)雜度的性能為當n=1時,f(n)=1,當n大于等于2時,f(n)=8f(3n/7),則算法的時間復(fù)雜度的階為()。A、n2B、log2nC、nD、nlog7/38答案：D107.()是貪心算法可行的第一個基本要素,也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：C108.對于下列算法,有時找不到問題解的是()。A、蒙特卡羅算法B、拉斯維加斯算法C、快速排序算法D、數(shù)值概率算法答案：B109.算法就是一組有窮的(),它們規(guī)定了解決某一特定類型問題的一系列運算。A、偽代碼B、語言C、代碼D、規(guī)則答案：D110.貪心算法是一種只顧眼前的步驟,而難以顧忌全局步驟的算法,對于貪心算法表現(xiàn)出的特點,下面說法錯誤的是()。A、不能保證最后求得的解是最佳的,即多半是近似解。(少數(shù)問題除外)B、策略容易發(fā)現(xiàn),而且運用簡單,被廣泛應(yīng)用。C、策略單一,結(jié)果也單一。D、算法實現(xiàn)過程中,通常用到輔助算法:排序。答案：C111.通常用來表示時間算法的有以下六種多項式: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)答案：A112.算法分析是()。A、將算法用某種程序設(shè)計語言恰當?shù)乇硎境鰜鞡、在抽象數(shù)據(jù)集合上執(zhí)行程序,以確定是否會產(chǎn)生錯誤的結(jié)果C、對算法需要多少計算時間和存儲空間作定量分析D、證明算法對所有可能的合法輸入都能算出正確的答案：C113.適用動態(tài)規(guī)劃的問題必須滿足()。A、最優(yōu)化原理B、無前效性C、最優(yōu)化原理和后效性D、最優(yōu)化原理和無后效性答案：D114.有6個元素按6,5,4,3,2,1的順序進棧,問下列()不是合法的出棧序列?A、543612B、453126C、346521D、234156答案：C115.當(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時,最大子段和為()。A、24B、22C、20D、15答案：C116.以Bitonic旅行路線問題為例,動態(tài)規(guī)劃的時間復(fù)雜度為()。A、O(n)B、O(n!)C、O(n2)D、O(n3)答案：C117.在尋找n個元素中第k小元素問題中如快速排序算法思想運用分治算法對n個元素進行劃分如何選擇劃分基準下面()A、隨機選擇一個元素作為劃分基準B、取子序列的第一個元素作為劃分基準C、用中位數(shù)的中位數(shù)方法尋找劃分基準D、以上皆可行。但不同方法算法復(fù)雜度上界可能不同答案：D118.對于分支限界法與回溯法,下面說法正確的是()。A、求解目標相同B、搜索方式相同C、對擴展結(jié)點的擴展方式相同D、都是一種在問題的解空間樹中搜索問題解的算法答案：D119.解決0/1背包問題時需要排序的方法是回溯法和()。A、動態(tài)規(guī)劃B、分支限界法C、貪心法D、線性規(guī)劃答案：B120.對于分治法與動態(tài)規(guī)劃法,下面的說法正確的是()。A、適合于用動態(tài)規(guī)劃法求解的問題,經(jīng)分解得到的子問題往往是相互獨立的B、使用分治法求解的問題,經(jīng)分解得到的子問題往往不是相互獨立的C、適合于用動態(tài)規(guī)劃法求解的問題,經(jīng)分解得到的子問題往往不是相互獨立的D、分治法可以不需要將待求解問題分成若干個子問題答案：C121.隊列是限定在()進行操作的線性表。A、中間B、隊首C、隊尾D、端點答案：D122.分支限界算法中根據(jù)從活結(jié)點表中選擇下一擴展結(jié)點的不同方式可有幾種常用分類,以下()描述最為準確。A、采用FIFO隊列的隊列式分支限界法B、采用最小值堆的優(yōu)先隊列式分支限界法C、采用最大值堆的優(yōu)先隊列式分支限界法D、以上都常用針對具體問題可以選擇采用其中某種更為合適的方式答案：D123.快速排序算法是基于()的一種排序算法。A、分治策略B、貪心C、回溯D、動態(tài)規(guī)劃答案：A124.貪心方法是一種求()的方法。A、最小解B、最大解C、最優(yōu)解D、局部最優(yōu)解答案：C125.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是()。A、貪心算法B、分支限界法C、分治法D、動態(tài)規(guī)劃算法答案：D126.下列哪個問題不能用貪心法求解()。A、哈夫曼編碼問題B、單源最短路徑問題C、0/1背包問題D、最小生成樹問題答案：C127.多項式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)答案：A128.插入和刪除只能在一端進行的線性表,稱為()。A、隊列B、循環(huán)隊列C、棧D、循環(huán)棧答案：C129.關(guān)于回溯算法和分支限界法以下()是不正確描述。A、回溯法中每個活結(jié)點只有一次機會成為擴展結(jié)點B、分支限界法中活結(jié)點一旦成為擴展結(jié)點就一次性產(chǎn)生其所有兒子結(jié)點在這些兒子結(jié)點中那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄其余兒子加入活結(jié)點表中C、回溯法采用深度優(yōu)先的結(jié)點生成策略D、分支限界法采用廣度優(yōu)先或最小耗費優(yōu)先最大效益優(yōu)先的結(jié)點生成策略答案：A130.分支限界法主要有()分支限界法和優(yōu)先隊列式分支限界法。A、隊列式(FIFO)B、棧式C、二叉樹式D、鏈式答案：A131.備忘錄方法是那種算法的變形()。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B132.算法與程序的區(qū)別在于算法具有()。A、能行性B、確定性C、有窮性D、輸入和輸出答案：C133.下面哪個不屬于算法的三要素()。A、操作B、控制結(jié)構(gòu)C、數(shù)據(jù)結(jié)構(gòu)D、程序答案：D134.使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點的求解方法稱為()。A、動態(tài)規(guī)劃B、分支限界法C、貪心法D、回溯法答案：D135.大符號用來描述增長率的下限,這個下限的階越(),結(jié)果就越有價值。A、高B、低C、和具體問題有關(guān)D、以上都不正確答案：A136.哈夫曼編碼的貪心算法所需的計算時間為()。A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)答案：B137.14+5/n+1/n2的漸進表達式為()。A、14B、1/nC、1/n2D、5/n答案：A138.當一個算法的運行時間為n2+n+1時,由于n2+n+1與n2的數(shù)量級相等,則稱n2為這個算法的()。A、漸進時間復(fù)雜度或時間復(fù)雜度B、空間復(fù)雜度C、問題規(guī)模D、輸入規(guī)模答案：A139.一個算法是對特定問題求解的一種描述,它是()。A、指令的有限序列B、程序的有限序列C、語句的有限序列D、代碼的有限序列答案：A140.分支限界法在問題的解空間樹中,按()策略,從根結(jié)點出發(fā)搜索解空間樹。A、廣度優(yōu)先B、深度優(yōu)先C、活結(jié)點優(yōu)先D、擴展結(jié)點優(yōu)先答案：A141.漸進算法分析是指()。A、算法在最佳情況、最差情況和平均情況下的代價B、當規(guī)模逐步往極限方向增大時對算法資源開銷“增長率”上的簡化分析C、數(shù)據(jù)結(jié)構(gòu)所占用的空間D、在最小輸入規(guī)模下算法的資源代價答案：B142.對于n個元素的排序問題。n=2時只要作()次比較即可排好序。A、3B、2C、1D、4答案：C143.快速排序算法的性能取決于()。A、劃分的對稱性B、數(shù)據(jù)的原始序列C、隨機選擇策略D、以上都不正確答案：A144.()能夠求得問題的解但卻無法有效地判定解的正確性。A、數(shù)值概率算法B、蒙特卡羅算法C、拉斯維加斯算法D、舍伍得算法答案：B145.若一個算法的時間復(fù)雜度用T(n)表示,其中n的含義是()。A、問題規(guī)模B、語句條數(shù)C、循環(huán)層數(shù)D、函數(shù)數(shù)量答案：A146.算法是由若干條指令組成的有窮序列,且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。其中算法的“確定性”是指組成算法的每條()是清晰的,無歧義的。A、程序B、指令C、語句D、語句塊答案：B147.對于迭代法,下面的說法不正確的是()。A、需要確定迭代模型B、需要建立迭代關(guān)系式C、需要對迭代過程進行控制,要考慮什么時候結(jié)束迭代過程D、不需要對迭代過程進行控制答案：D148.回溯法搜索解空間樹時,常用的兩種剪枝函數(shù)為()和限界函數(shù)。A、遞歸函數(shù)B、迭代函數(shù)C、非遞歸函數(shù)D、約束函數(shù)答案：D149.寫出下列f(n)的漸進性態(tài),若f(n)=C0,C0為常數(shù),則f(n)=()。A、O(1)B、O(n)C、O(n2)D、O(n3)答案：A150.最大效益優(yōu)先是()的一種搜索方式。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：A151.對于P問題和NP問題,下面的關(guān)系正確的是()。A、P類問題包含在NP類問題中B、NP類問題包含在P類問題中C、P=NPD、NP完全問題是P類問題的子集答案：A152.FIFO是()的一搜索方式。A、分支限界法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：A153.一個算法應(yīng)該包含如下幾條性質(zhì)除了()。A、二義性B、有限性C、正確性D、可終止性答案：A154.應(yīng)用分治法的兩個前提是()。A、問題的可分性和解的可歸并性B、問題的可分性和解的存在性C、問題的復(fù)雜性和解的可歸并性D、問題的可分性和解的復(fù)雜性答案：A155.設(shè)計動態(tài)規(guī)劃算法的步驟為:(1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征。(2)遞歸的定義最優(yōu)值。(3)()。(4)計算最優(yōu)值得到的信息,構(gòu)造最優(yōu)解。A、以自底向上的方式計算出最優(yōu)值B、以自頂向下的方式計算出最優(yōu)值C、迭代的方式計算出最優(yōu)值D、遞推的方式算出最優(yōu)值答案：A156.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略()。A、遞歸函數(shù)B、剪枝函數(shù)C、隨機數(shù)函數(shù)D、搜索函數(shù)答案：B157.我們通常說的有效算法或?qū)嶋H可行算法是指()。A、時間復(fù)雜度可以達到常數(shù)階的算法B、時間復(fù)雜度可以達到多項式時間的算法C、時間復(fù)雜度可以達到對數(shù)階的算法D、時間復(fù)雜度可以達到指數(shù)階的算法答案：B158.優(yōu)先隊列通常用以下()數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。A、棧B、堆C、隊列D、二叉查找樹答案：B159.分治法所能解決的問題應(yīng)具有的最關(guān)鍵特征是()。A、該問題的規(guī)模縮小到一定的程度就可以容易地解決B、該問題可以分解為若干個規(guī)模較小的相同問題C、利用該問題分解出的子問題的解可以合并為該問題的解D、該問題所分解出的各個子問題是相互獨立的答案：C160.分支限界法與回溯法的相同點是:都是一種在問題的()中搜索問題解的算法。A、子集樹TB、排列樹TC、二叉搜索樹TD、解空間樹T答案：D161.下列是動態(tài)規(guī)劃算法基本要素的是()。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子空間重疊性質(zhì)答案：D162.對于數(shù)值概率算法,下面的說法不正確的是()。A、常用于數(shù)值問題的求解,得到的往往是近似解B、解的精度隨計算時間的增加而提高C、解的精度和計算時間之間沒有關(guān)系D、在很多情況下,計算出問題的精確解是不可能或沒必要答案：C163.下面不是分支界限法搜索方式的是()。A、廣度優(yōu)先B、最小耗費優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先答案：D164.棧和隊列的共同點是()。A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、沒有共同點答案：C165.下列算法中通常以自頂向下的方式求解最優(yōu)解的是()。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：C166.用貪心法求解背包問題時,為了使收益最大化要選擇()的物品裝入背包。A、單位重量收益最大B、收益最大C、重量最大D、重量最小答案：A167.一個棧的入棧次序ABCDE,則棧的不可能的輸出序列是()。A、EDCBAB、DECBAC、DCEABD、ABCDE答案：C168.算法的復(fù)雜性是()的度量,是評價算法優(yōu)劣的重要依據(jù)。A、算法效率B、計算時間C、存儲空間D、運行時間答案：A169.分支限界法求解最大團問題時,活結(jié)點表的組織形式是()。A、最小堆B、最大堆C、棧D、數(shù)組答案：B170.關(guān)于回溯搜索法的介紹,下面()是不正確描述。A、回溯法有“通用解題法”之稱它可以系統(tǒng)地搜索一個問題的所有解或任意解B、回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C、回溯算法在生成解空間的任一結(jié)點時先判斷該結(jié)點是否可能包含問題的解,如果肯定不包含,則跳過對該結(jié)點為根的子樹的搜索,逐層向祖先結(jié)點回溯D、回溯算法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當前擴展結(jié)點的路徑答案：D171.下面哪個問題不是典型的NP完全問題()。A、m-著色問題B、旅行商問題C、哈密爾頓回路問題D、排序問題答案：D172.計算機算法指的是()。A、計算方法B、排序方法C、解決問題的方法和過程D、調(diào)度方法答案：C173.當輸入規(guī)模為n時算法增長率最小的是()。A、5nB、20log2nC、2nD、3nlog3n答案：B174.順序查找的時間復(fù)雜度為()。A、O(n)B、O(logn)C、O(n2)D、O(nlogn)答案：A175.算法分析的兩個主要方面是()。A、空間復(fù)雜度和時間復(fù)雜度B、正確性和簡單性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜度和程序復(fù)雜度答案：A176.優(yōu)先隊列的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列,并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的高低與p值大小相關(guān),根據(jù)問題的不同情況,采用()來描述優(yōu)先隊列。A、先進先出隊列B、后進先出的棧C、最大堆或最小堆D、隨機序列答案：C177.以下關(guān)于判定問題難易處理的敘述中正確的是()。A、可以由多項式時間算法求解的問題是難處理的B、需要超過多項式時間算法求解的問題是易處理的C、可以由多項式時間算法求解的問題是易處理的D、需要超過多項式時間算法求解的問題是不能處理的答案：C178.回溯法在解空間樹T上的搜索方式是()。A、深度優(yōu)先B、廣度優(yōu)先C、最小耗費優(yōu)先D、活結(jié)點優(yōu)先答案：A179.下列不屬于一個好的算法應(yīng)具有的特性的是()。A、正確性B、簡明性C、無限性D、最優(yōu)性答案：C180.分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題()。A、問題規(guī)模相同,問題性質(zhì)相同B、問題規(guī)模相同,問題性質(zhì)不同C、問題規(guī)模不同,問題性質(zhì)相同D、問題規(guī)模不同,問題性質(zhì)不同答案：C181.n2+10n-1的漸進表達式為()。A、1B、2nC、n2D、n3答案：C182.分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解,二者()。A、求解目標不同搜索方式相同B、求解目標不同搜索方式也不同C、求解目標相同搜索方式不同D、求解目標相同搜索方式也相同答案：B183.背包問題可獲得最優(yōu)解的輸入是按()。A、重量密度排序B、價值密度排序C、單位重量收益大小排序D、重量大小排序答案：B184.實現(xiàn)最大子段和利用的算法是()。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：B185.折半查找的時間復(fù)雜度為()。A、O(n)B、O(logn)C、O(n2)D、O(nlogn)答案：B186.分支限界法的搜索策略是:在擴展結(jié)點處,先生成其()兒子結(jié)點(分支),然后再從當前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點,以加速搜索的進程,在每一活結(jié)點處,計算一個函數(shù)值(限界),并根據(jù)這些已計算出的函數(shù)值,從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點,使搜索朝著解空間樹上有最優(yōu)解的分支推進,以便盡快地找出一個最優(yōu)解。A、一個B、二個C、任意多個D、所有的答案：D187.如果無向連通圖G中不包含任何關(guān)節(jié)點,則稱該圖G為()。A、雙連通圖B、單連通圖C、強連通圖D、弱連通圖答案：A188.用回溯法解0/1背包問題時,該問題的解空間結(jié)構(gòu)為()結(jié)構(gòu)。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹答案：A189.對于拉斯維加斯算法,下面的說法不正確的是()。A、不會得到不正確的解B、有時找不到問題的解C、找到正確解的概率隨算法計算時間的增加而提高D、用同一拉斯維加斯算法對同一問題求解多次,對求解失敗的概率沒有影響答案：D190.遞歸通常用()來實現(xiàn)。A、有序的線性表B、隊列C、棧D、數(shù)組答案：C191.舍伍德算法總能求得問題的()。A、一個解B、兩個解C、三個解D、三個以上的解答案：A192.階乘函數(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)答案：B193.對于分支限界法,下面不屬于分支限界法搜索方式的是()。A、廣度優(yōu)先B、最小耗費優(yōu)先C、最大效益優(yōu)先D、層次優(yōu)先答案：D194.下列哪一種算法是隨機化算法()。A、貪心算法B、回溯法C、動態(tài)規(guī)劃算法D、舍伍德算法答案：D195.投點法是()的一種。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：B196.若一棵二叉樹具有10個度為2的結(jié)點,5個度為1的結(jié)點,那么度為0的結(jié)點個數(shù)是()。A、9B、11C、15D、不確定答案：B197.廣度優(yōu)先是()的一種搜索方式。A、分支限界算法B、動態(tài)規(guī)劃法C、貪心算法D、回溯算法答案：A198.回溯法在問題的解空間樹中,按()策略,從根節(jié)點出發(fā)搜索解空間樹。A、廣度優(yōu)先B、深度優(yōu)先C、隨機D、以上說法都不對答案：B199.找最小生成樹的算法Kruskal的時間復(fù)雜度為()。A、O(n2)B、O(mlogn)C、O(nlogm)D、O(mlogm)答案：D200.f(n)=O(g(n))表示當且僅當存在正的常數(shù)C和N0,使得對于所有的n>=N0,有()。A、f(n)<=Cg(n)B、f(n)>=Cg(n)C、f(n)>Cg(n)D、f(n)=Cg(n)答案：A201.二分搜索過程的算法行為可以用一棵()來描述。A、二叉排序樹B、二叉判定樹C、子集樹D、排列樹答案：B202.最優(yōu)裝載問題可用貪心算法求解,采用()先裝的貪心選擇策略,可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。A、重量最重者B、單位重量收益大C、重量最輕者D、收益最大答案：C203.二分查找只適用()存儲結(jié)構(gòu)。A、堆B、順序C、任意次序D、棧答案：B204.動態(tài)規(guī)劃算法與貪心法的主要區(qū)別是()。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解答案：B205.有六個元素6,5,4,3,2,1的順序進棧,則下列哪一個不是合法的出棧序列()。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答案：C填空題1.計算一個算法時間復(fù)雜度通?？梢杂嬎悖ǎⅲǎ┗蛴嬎悴?。答案：循環(huán)次數(shù)|基本操作的頻率2.合并排序算法使用的是（）算法設(shè)計的思想。答案：分治3.在隊列中存取數(shù)據(jù)應(yīng)遵循的原則是（）。答案：先進先出4.算法的基本特征:（）。答案：輸入、輸出、確定性、有限性、可行性5.（）是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。答案：隊列6.算法設(shè)計的基本要求:（）。答案：正確性和可讀性7.分支限界法是一種既帶有（）又帶有（）的搜索算法。答案：系統(tǒng)性|跳躍性8.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干（）,先求解（）,然后從這些（）的解得到原問題的解。答案：子問題|子問題|子問題9.快速排序算法的性能取決于（）答案：劃分的對稱性。10.快速排序算法是基于（）的一種排序算法。答案：分治策略11.（）是貪心算法可行的第一個基本要素,也是貪心算法與動態(tài)規(guī)劃算法主要區(qū)別。答案：貪心選擇性質(zhì)12.在快速排序、插入排序和合并排序算法中,（）算法不是分治算法。答案：插入排序13.動態(tài)規(guī)劃算法中存儲子問題的解是為了（）。答案：避免重復(fù)求解子問題14.任何可用計算機求解的問題所需的時間都與其（）有關(guān)。答案：規(guī)模15.算法的“確定性”指的是組成算法的每條（）是清晰的,無歧義的。答案：指令16.計算機的資源最重要的是（）和（）資源.因而,算法的復(fù)雜性有（）和（）之分。答案：時間|空間|時間復(fù)雜度|空間復(fù)雜度17.算法是由若干條指令組成的有窮序列,且要滿足輸入（）、確定性和（）四條性質(zhì)。答案：,輸出|有限性18.在隊列中,允許插入的一端稱為（）。答案：隊尾19.循環(huán)隊列的引入