川農(nóng)大算法分析期末復(fù)習(xí)

..算法分析與設(shè)計復(fù)習(xí)題HYPERLINK判斷題1HYPERLINK選擇題：2判斷題1.算法就是一組有窮的規(guī)那么。答案：正確2.概率算法中蒙特卡羅算法得到的解必是正確的。答案：錯誤3.程序和算法一樣，都是某種程序設(shè)計語言的具體實現(xiàn)。答案：錯誤4.合并排序算法是漸近最優(yōu)算法。答案：正確5.遞歸定義必須是有確切含義是指必須一步比一步簡單，最后是有終結(jié)的，決不能無限循環(huán)下去。答案：正確6.二分搜索方法在最壞的情況下用O(logn)時間完成搜索任務(wù)。答案：正確7.能否利用分治法完全取決于問題是否具有如下特征：利用該問題分解出的子問題的解可以合并為該問題的解。答案：正確8.分治法的根本思想是將一個規(guī)模較大的問題分解成假設(shè)干個規(guī)模較小的子問題，這些子問題之間并不一定相互獨立。答案：錯誤9.遞歸算法的效率往往很低，費時和費存空間。答案：正確10.當(dāng)一個問題具有最優(yōu)子構(gòu)造性質(zhì)時只能用動態(tài)規(guī)劃方法求解。答案：錯誤11.如果一類活動過程一個階段的決策確定以后，常影響到下一個階段的決策，那么稱它為多階段決策問題。答案：正確12.反復(fù)應(yīng)用分治手段，不能使子問題與原問題類型一致而其規(guī)模卻不斷縮小。答案：錯誤13.裴波那契數(shù)列的定義：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其數(shù)據(jù)的定義形式不是按遞歸定義。答案：錯誤14.0-1背包問題與背包問題這兩類問題都可以用貪心算法求解。答案：錯誤15.證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子構(gòu)造性質(zhì)。答案：錯誤16.子問題之間不包含公共的子問題，這個條件涉及到分治法的效率。答案：正確17.概率算法允許在執(zhí)行過程中隨機地選擇下一個計算步驟。答案：正確18.二分搜索法的二分查找只適用于順序存儲構(gòu)造。答案：正確19.要想在電腦上擴大所處理問題的規(guī)模，有效的途徑是降低算法的計算復(fù)雜度。答案：正確20.用回溯法解題一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。答案：錯誤21.從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是一個遞歸過程。因此，分治法的計算效率通?？梢杂眠f歸方程來進展分析。答案：正確22.多階段決策問題中，每一個階段可能有假設(shè)干個決策可供選擇答案：正確23.拉斯維加斯算法不會得到不正確的解，但有時找不到解。答案：正確24.在通往邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧保存的每次調(diào)用的中間結(jié)果是局部變量和返回地址值。答案：正確25.要想在電腦上擴大所處理問題的規(guī)模，有效的途徑是提高算法的計算復(fù)雜度。答案：錯誤26.程序必須滿足算法具有數(shù)據(jù)輸出的性質(zhì)。答案：正確27.反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小答案：正確28.一個算法產(chǎn)生一個或多個輸出，它們是同輸入有某種特定關(guān)系的量答案：正確29.最優(yōu)子構(gòu)造性質(zhì)特征反映了遞歸思想的應(yīng)用答案：正確30.遞歸邊界本身并不使用遞歸的定義答案：正確31.用分治法求解一個問題，所需的時間是由子問題的個數(shù)、大小以及把這個問題分解為子問題所需的工作總量來確定的。答案：正確32.應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個〔最優(yōu)〕解。答案：正確33.好的約束函數(shù)能顯著地減少所生成的結(jié)點數(shù)，但這樣的約束函數(shù)往往計算量較大。因此，在選擇約束函數(shù)時通常存在生成結(jié)點數(shù)與約束函數(shù)計算量之間的折衷。答案：正確34.一個遞歸定義必須是有確切含義的，必須一步比一步簡單，最后是有終結(jié)的，不能無限循環(huán)下去。答案：正確35.最優(yōu)子構(gòu)造性質(zhì)是應(yīng)用分治法的前提。答案：正確36.操作系統(tǒng)，它是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。答案：正確37.有些數(shù)據(jù)構(gòu)造如二叉樹等，由于其本身的遞歸特性、特別適合用遞歸的形式來描述。答案：正確38.概率算法的一個根本特征是，對所求問題的同一個實例用同一個算法求解兩次一定能得到完全一樣的效果。答案：錯誤39.問題可以分解為假設(shè)干個規(guī)模較小的一樣問題，即稱該問題具有最優(yōu)子構(gòu)造性質(zhì)。答案：錯誤40.遞推是從邊界條件出發(fā)，通過遞推式到達邊界條件。答案：正確41.所有的遞歸函數(shù)都能找到對應(yīng)的非遞歸定義。答案：正確42.定義遞歸函數(shù)時可以沒有初始值。答案：錯誤43.動態(tài)規(guī)劃算法的根本要素是最優(yōu)子構(gòu)造。答案：正確44.最優(yōu)子構(gòu)造性質(zhì)是指原問題的最優(yōu)解包含其子問題的最優(yōu)解。答案：正確45.動態(tài)規(guī)劃算法求解問題時，分解出來的子問題相互獨立。答案：錯誤46.滿足貪心選擇性質(zhì)必滿足最優(yōu)子構(gòu)造性質(zhì)。答案：錯誤47.回溯法中限界函數(shù)的目的是剪去得不到最優(yōu)解的子樹。答案：正確48.分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，兩者的搜索方式是一樣的。答案：錯誤49.任何遞歸算法都有遞歸出口。答案：正確50.遞歸算法的執(zhí)行效率比功能一樣的非遞歸算法的執(zhí)行效率高。答案：錯誤51.遞歸算法不能轉(zhuǎn)換成對應(yīng)的非遞歸算法。答案：錯誤52.數(shù)據(jù)元素是數(shù)據(jù)的最小單位答案：錯誤53.數(shù)據(jù)對象就是一組數(shù)據(jù)元素的集合答案：錯誤54.任何數(shù)據(jù)構(gòu)造都具備三個根本運算：插入、刪除和查找。答案：錯誤55.數(shù)據(jù)對象是由有限個類型一樣的數(shù)據(jù)元素構(gòu)成的。答案：正確56.數(shù)據(jù)的邏輯構(gòu)造與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。答案：錯誤57.如果數(shù)據(jù)元素值發(fā)生改變，那么數(shù)據(jù)的邏輯構(gòu)造也隨之改變。答案：錯誤58.邏輯構(gòu)造一樣的數(shù)據(jù)，可以采用多種不同的存儲方法。答案：正確59.邏輯構(gòu)造不一樣的數(shù)據(jù)，必須采用不同的存儲方法來存儲。答案：錯誤60.數(shù)據(jù)的邏輯構(gòu)造是指數(shù)據(jù)元素的各數(shù)據(jù)項之間的邏輯關(guān)系。答案：錯誤61.順序存儲方式只能用于存儲線性構(gòu)造。答案：錯誤62.算法可以用不同的語言來描述，如果用C語言或Pascal語言等高級語言來描述，那么算法就等同于程序。答案：錯誤63.數(shù)據(jù)的邏輯構(gòu)造是指各數(shù)據(jù)元素之間的邏輯關(guān)系。答案：正確64.數(shù)據(jù)構(gòu)造、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像〔或表示〕分別稱為存儲構(gòu)造、節(jié)點和數(shù)據(jù)域。答案：正確65.數(shù)據(jù)的物理構(gòu)造是指數(shù)據(jù)在計算機的實際存儲形式。答案：正確66.分配給單鏈表的存與地址必須是連續(xù)的。答案：錯誤67.從長度為n的順序表中刪除任何一個元素，時間復(fù)雜度都是O(n)。答案：錯誤68.向順序表中插入一個元素，平均要移動大約一半的元素。答案：正確69.但凡為空的單鏈表都是不含任何節(jié)點的。答案：錯誤70.如果單鏈表帶有頭節(jié)點，那么插入操作永遠不會改變頭節(jié)點指針的值。答案：正確71.在循環(huán)單鏈表中，任何一個節(jié)點的指針域都不可能為空。答案：正確72.順序存儲方式的特點是存儲密度大且插入、刪除運算效率高。答案：錯誤73.線性表的順序存儲構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?gòu)造。答案：錯誤74.順序存儲構(gòu)造屬于靜態(tài)構(gòu)造而鏈?zhǔn)酱鎯?gòu)造屬于動態(tài)構(gòu)造。答案：正確75.由于順序存儲構(gòu)造要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活。答案：正確76.對于單鏈表來說，只有從頭節(jié)點開場才能掃描表中全部節(jié)點。答案：正確77.對于循環(huán)單鏈表來說，從表中任一節(jié)點出發(fā)都能掃描表中全部節(jié)點。答案：正確78.雙鏈表的特點是很容易找任一節(jié)點的前趨和后繼。答案：正確79.線性表有兩種存儲構(gòu)造：一是順序表，二是鏈表。答案：正確80.如果有多個線性表同時共存，并且在處理過程中各表的長度會動態(tài)地發(fā)生變化，線性表的總數(shù)也會自動改變。在此情況下，應(yīng)選用鏈?zhǔn)酱鎯?gòu)造。答案：正確81.假設(shè)線性表的總數(shù)根本穩(wěn)定且很少進展插入和刪除操作，但要求以最快的速度存取線性表中的元素，那么應(yīng)該選用順序存儲構(gòu)造。答案：正確82.對于單鏈表和雙鏈表，均能從當(dāng)前節(jié)點出發(fā)訪問到任一節(jié)點。答案：錯誤83.循環(huán)單鏈表和循環(huán)雙鏈表從尾指針出發(fā)可以訪問到鏈表中的任意節(jié)點。答案：正確84.假設(shè)頻繁地對一個線性表進展插入和刪除操作，該線性表宜采用鏈?zhǔn)酱鎯?gòu)造。答案：正確85.棧底元素是不能刪除的元素。答案：錯誤86.順序棧中元素值的大小是有序的。答案：錯誤87.棧頂元素和棧底元素有可能是同一個元素。答案：正確88.假設(shè)用s[1…m]表示順序棧的存儲空間，那么對棧的進棧、出棧操作最多只能進展m次。答案：錯誤89.棧是一種對進棧、出棧操作總次數(shù)作了限制的線性表。答案：錯誤90.空棧沒有棧頂指針答案：錯誤91.環(huán)形隊列中有多少元素，可以根據(jù)隊首指針和隊尾指針的值來計算。答案：正確92.無論是順序隊列，還是鏈?zhǔn)疥犃?，插入、刪除運算的時間復(fù)雜度都是O(1)。答案：正確93.棧和隊列都是插入和刪除操作受限的線性表。答案：正確94.棧和隊列的存儲方式既可以是順序方式，也可以是鏈?zhǔn)椒绞酱鸢福赫_95.環(huán)形隊列也存在空間溢出的問題答案：正確96.消除遞歸不一定需要使用棧。答案：正確97.二分搜索算法是利用貪心法實現(xiàn)的算法。答案：錯誤98.動態(tài)規(guī)劃算法通常是以自底向上的方式求解最優(yōu)解。答案：正確99.貪心法不能解決0/1背包問題。答案：正確100.深度優(yōu)先不是分支限界法的搜索方式。答案：正確101.二分搜索算法是利用分治策略實現(xiàn)的算法。答案：正確102.背包問題不能使用貪心法解決。答案：錯誤103.單源最短路徑問題不能使用貪心法解決。答案：錯誤104.時間復(fù)雜度低是衡量一個算法好壞的標(biāo)準(zhǔn)。答案：正確105.歸并排序不可以使用分治法求解。答案：錯誤106.拉斯維加斯算法有時找不到問題的解。答案：正確107.舍伍德算法有時候找不到問題的解。答案：錯誤108.NP問題都是不可能解決的問題答案：錯誤109.P類問題包含在NP類問題中。答案：正確110.NP類問題包含在P類問題中。答案：錯誤111.NP完全問題是P類問題的子集答案：錯誤112.蒙特卡羅算法是概率算法的一種答案：正確113.蒙特卡羅算法是貪心算法的一種答案：錯誤114.蒙特卡羅算法是回溯算法的一種答案：錯誤115.動態(tài)規(guī)劃算法不是隨機化算法答案：正確116.最優(yōu)子構(gòu)造性質(zhì)是貪心算法與動態(tài)規(guī)劃算法的共同點答案：正確117.矩陣連乘問題的算法可由動態(tài)規(guī)劃算法來設(shè)計實現(xiàn)答案：正確118.Strassen矩陣乘法是利用分治策略實現(xiàn)的算法答案：正確119.Strassen矩陣乘法是利用貪心法實現(xiàn)的算法答案：錯誤120.貪心選擇性質(zhì)是貪心算法的根本要素答案：正確121.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯算法答案：正確122.算法分析的兩個主要方面是時間復(fù)雜度和空間復(fù)雜度分析答案：正確123.實現(xiàn)最大子段和利用的算法是動態(tài)規(guī)劃法答案：正確124.實現(xiàn)最大子段和利用的算法是貪心法答案：錯誤125.實現(xiàn)最大子段和利用的算法是回溯法答案：錯誤126.廣度優(yōu)先是分支限界算法的一種搜索方式答案：正確127.廣度優(yōu)先是回溯算法的一種搜索方式答案：錯誤128.廣度優(yōu)先是貪心算法的一種搜索方式答案：錯誤129.舍伍德算法是概率算法的一種答案：正確130.舍伍德算法是貪心算法的一種。答案：錯誤131.舍伍德算法是回溯算法的一種。答案：錯誤132.實現(xiàn)最長公共子序列利用的算法是動態(tài)規(guī)劃法。答案：正確133.計算機算法指的是解決問題的方法和過程。答案：正確134.根據(jù)排序元素所在位置的不同，排序分排序和外排序。答案：正確135.根據(jù)排序元素所在位置的不同，排序分首排序和尾排序。答案：錯誤136.算法必須具備輸入、輸出和有窮性、確定性和可行性等5個特性。答案：正確137.算法必須具備輸入、輸出和易讀性、穩(wěn)定性和平安性等5個特性。答案：錯誤138.與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題經(jīng)分解得到的子問題往往不是相互獨立的答案：正確139.與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題往往是相互獨立的答案：錯誤140.二分搜索算法的根本思想是將n個元素分成個數(shù)大致一樣的兩半，取a[n/2]與x進展比擬：如果x<a[n/2]，那么只要在數(shù)組a的左半部繼續(xù)搜索x答案：正確141.二分搜索算法的根本思想是將n個元素分成個數(shù)大致一樣的兩半，取a[n/2]與x進展比擬：如果x>a[n/2]，那么只要在數(shù)組a的左半部繼續(xù)搜索x答案：錯誤142.算法必須具備輸入、輸出和可執(zhí)行性、可移植性和可擴大性等5個特性。答案：錯誤143.適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。答案：正確144.適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和后效性。答案：錯誤145.二分查找只適用于順序存儲構(gòu)造。答案：正確146.二分查找只適用于鏈?zhǔn)酱鎯?gòu)造。答案：錯誤147.應(yīng)用分治法的兩個前提是問題的可分性和解的可歸并性。答案：正確148.應(yīng)用分治法的兩個前提是問題的可分性和解的復(fù)雜性。答案：錯誤149.對于n個元素的排序問題。n＝2時只要作1次比擬即可排好序。答案：正確150.對于n個元素的排序問題。n＝2時要作2次比擬即可排好序。答案：錯誤151.分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是利用該問題分解出的子問題的解可以合并為該問題的解。答案：正確152.分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是該問題的規(guī)?？s小到一定的程度就可以容易地解決。答案：錯誤153.直接或間接的調(diào)用自身的算法稱為遞歸算法。答案：正確154.直接或間接的調(diào)用自身的算法稱為動態(tài)規(guī)劃算法。答案：錯誤155.當(dāng)上下限表示相等時我們使用Θ表示法來描述算法代價。答案：正確156.當(dāng)上下限表示相等時我們使用大O表示法來描述算法代價。答案：錯誤157.遞歸通常用棧來實現(xiàn)。答案：正確158.遞歸通常用隊列來實現(xiàn)。答案：錯誤159.分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題的問題規(guī)模不同，問題性質(zhì)一樣。答案：正確160.0/1背包問題不能用貪心算法求解。答案：正確161.可以由多項式時間算法求解的問題是易處理的。答案：正確162.可以由多項式時間算法求解的問題是難處理的。答案：錯誤163.需要超過多項式時間算法求解的問題是不能處理的。答案：錯誤164.遞歸通常用數(shù)組來實現(xiàn)。答案：錯誤165.哈密爾頓回路問題是典型的NP完全問題。答案：正確166.排序問題是典型的NP完全問題。答案：錯誤167.算法分析需要對算法需要多少計算時間和存儲空間作定量分析。答案：正確168.用數(shù)量級形式表示算法的執(zhí)行時間稱為算法的時間復(fù)雜度。答案：正確169.用數(shù)量級形式表示算法的執(zhí)行時間稱為算法的空間復(fù)雜度。答案：錯誤170.最壞情況下，順序查找的時間復(fù)雜度為O(n)。答案：正確171.最壞情況下，折半查找的時間復(fù)雜度為O(log2n)。答案：正確172.合并排序的根本運算是把兩個或多個有序序列合并成一個有序序列答案：正確173.最優(yōu)子構(gòu)造是動態(tài)規(guī)劃算法的根本要素之一。答案：正確174.快速排序算法是基于分治策略的一種排序算法。答案：正確175.快速排序算法是基于回溯的一種排序算法。答案：錯誤176.快速排序算法是基于貪心法的一種排序算法。答案：錯誤177.貪心法通常以自頂向下的方式求解最優(yōu)解。答案：正確178.分治法通常以自頂向下的方式求解最優(yōu)解。答案：錯誤179.回溯法通常以自頂向下的方式求解最優(yōu)解。答案：錯誤180.不斷回頭尋找目標(biāo)的方法稱為回溯法。答案：正確181.不斷回頭尋找目標(biāo)的方法稱為概率算法。答案：錯誤182.不斷回頭尋找目標(biāo)的方法稱為貪心法。答案：錯誤183.拉斯維加斯算法找到的解一定是正確的。答案：正確184.拉斯維加斯算法找到的解正確與否不確定。答案：錯誤185.記號在算法復(fù)雜性的表示法中表示緊致界。答案：正確186.記號在算法復(fù)雜性的表示法中表示上界。答案：錯誤187.記號在算法復(fù)雜性的表示法中表示下界。答案：錯誤188.一個算法是對特定問題求解的一種描述，它是指令的有限序列。答案：正確189.一個遞歸算法必須包括終止條件和遞歸局部。答案：正確190.棧和隊列的共同點是只允許在端點處插入和刪除元素。答案：正確191.排序趟數(shù)與原始序列有關(guān)的排序方法是冒泡排序法。答案：正確192.棧和隊列的共同點都是先進先出。答案：錯誤193.棧和隊列的共同點都是先進后出。答案：錯誤194.排序趟數(shù)與原始序列有關(guān)的排序方法是選擇排序法。答案：錯誤195.在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實際價值的是最壞情況下的時間復(fù)雜度。答案：正確196.在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實際價值的是最好情況下的時間復(fù)雜度。答案：錯誤197.假設(shè)一個算法的時間復(fù)雜度用T(n)表示，其中n的含義是問題規(guī)模。答案：正確198.合并排序法的根本思想是：將待排序元素分成大小大致一樣的2個子集合，分別對每個子集合進展排序，最終將排好序的子集合合并成為所要求的排好序的集合。答案：正確選擇題：1.二分搜索算法是利用〔A〕實現(xiàn)的算法。選項A.分治策略選項B.動態(tài)規(guī)劃法選項C.貪心法選項D.回溯法答案：2.回溯法解旅行售貨員問題時的解空間樹是〔B〕。選項A.子集樹選項B.排列樹選項C.深度優(yōu)先生成樹選項D.廣度優(yōu)先生成樹答案：3.以下算法常以自底向上的方式求解最優(yōu)解的是〔B〕。選項A.備忘錄法選項B.動態(tài)規(guī)劃法選項C.貪心法選項D.回溯法答案：4.下面不是分支界限法搜索方式的是〔D〕。選項A.廣度優(yōu)先選項B.最小消耗優(yōu)先選項C.最大效益優(yōu)先選項D.深度優(yōu)先答案：5．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度〔B〕。A、O〔〕B、O〔〕C、O〔〕D、O〔〕6．分支限界法求解最大團問題時，活結(jié)點表的組織形式是〔B〕。A、最小堆B、最大堆C、棧D、數(shù)組7、下面問題〔B〕不能使用貪心法解決。A單源最短路徑問題BN皇后問題C最小花費生成樹問題D背包問題答案：8.以下算法中不能解決0/1背包問題的是〔A〕。A貪心法B動態(tài)規(guī)劃C回溯法D分支限界法答案：9.背包問題的貪心算法所需的計算時間為〔B〕。A、O〔n〕B、O〔nlogn〕C、O〔〕D、O〔n〕答案：10．二分搜索算法是利用〔A〕實現(xiàn)的算法。A.分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：11．以下不是動態(tài)規(guī)劃算法根本步驟的是〔B〕。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解答案：12．最大效益優(yōu)先是〔A〕的一種搜索方式。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：13、在以下算法中有時找不到問題解的是〔B〕。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：14．以下算法常以自底向上的方式求解最優(yōu)解的是〔B〕。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：14．以下算法常以自底向上的方式求解最優(yōu)解的是〔B〕。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：15、衡量一個算法好壞的標(biāo)準(zhǔn)是〔C〕。A運行速度快B占用空間少C時間復(fù)雜度低D代碼短答案：16、以下不可以使用分治法求解的是〔D〕。A、棋盤覆蓋問題B、選擇問題C、歸并排序D、0/1背包問題答案：17.實現(xiàn)循環(huán)賽日程表利用的算法是〔A〕A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：18、以下隨機算法中運行時有時候成功有時候失敗的是〔C〕A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法答案：19．下面不是分支界限法搜索方式的是〔D〕。A、廣度優(yōu)先B、最小消耗優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先答案：20．以下算法常以深度優(yōu)先方式系統(tǒng)搜索問題解的是〔D〕。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：21.備忘錄方法是那種算法的變形。〔B〕。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：22．哈弗曼編碼的貪心算法所需的計算時間為〔B〕。A、O〔n〕B、O〔nlogn〕C、O〔〕D、O〔n〕答案：23．最長公共子序列算法利用的算法是〔B〕A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：24．實現(xiàn)棋盤覆蓋算法利用的算法是〔A〕。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：25.下面是貪心算法的根本要素的是〔C〕。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解26.回溯法的效率不依賴于以下哪些因素〔D〕。A.滿足顯約束的值的個數(shù)C.計算限界函數(shù)的時間B.計算約束函數(shù)的時間D.確定解空間的時間27.下面哪種函數(shù)是回溯法中為防止無效搜索采取的策略〔B〕。A．遞歸函數(shù)B.剪枝函數(shù)C．隨機數(shù)函數(shù)D．搜索函數(shù)28、下面關(guān)于NP問題說確的是〔B〕。A．NP問題都是不可能解決的問題B．P類問題包含在NP類問題中C．NP完全問題是P類問題的子集D．NP類問題包含在P類問題中29、蒙特卡羅算法是〔B〕的一種。A.分支界限算法B.概率算法C.貪心算法D.回溯算法答案：30.以下哪一種算法不是隨機化算法〔C〕。A.蒙特卡羅算法B.拉斯維加斯算法C.動態(tài)規(guī)劃算法D.舍伍德算法答案：31.〔D〕是貪心算法與動態(tài)規(guī)劃算法的共同點。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子構(gòu)造性質(zhì)答案：32.矩陣連乘問題的算法可由〔B〕設(shè)計實現(xiàn)。A、分支界限算法B、動態(tài)規(guī)劃算法C、貪心算法D、回溯算法答案：33、Strassen矩陣乘法是利用〔A〕實現(xiàn)的算法。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：34、使用分治法求解不需要滿足的條件是〔A〕。A子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用一樣的方法求解答案：35、回溯法搜索狀態(tài)空間樹是按照〔C〕的順序。A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷答案：36、實現(xiàn)合并排序利用的算法是〔A〕A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：37、以下是動態(tài)規(guī)劃算法根本要素的是〔D〕A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子空間重疊性質(zhì)答案：38．采用廣度優(yōu)先策略搜索的算法是〔A〕A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：39、在以下算法中得到的解未必正確的選項是〔A〕A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：40．實現(xiàn)大整數(shù)的乘法是利用的算法〔C〕A、貪心法B、動態(tài)規(guī)劃法C、分治策略D、回溯法答案：41．0-1背包問題的回溯算法所需的計算時間為〔A〕A、O〔n〕B、O〔nlogn〕C、O〔〕D、O〔n〕答案：42．貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是〔B〕A、最優(yōu)子構(gòu)造B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解答案：43.實現(xiàn)最大子段和利用的算法是〔B〕。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法答案：44.優(yōu)先隊列式分支限界法選取擴展結(jié)點的原那么是〔C〕A、先進先出B、后進先出C、結(jié)點的優(yōu)先級D、隨機答案：45、廣度優(yōu)先是〔A〕的一種搜索方式。A、分支界限算法B、動態(tài)規(guī)劃法C、貪心算法D、回溯算法答案：46、舍伍德算法是〔B〕的一種A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：47、在以下算法中有時找不到問題解的是〔B〕A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：48以下哪一種算法是隨機化算法〔D〕。A.貪心算法B.回溯法C.動態(tài)規(guī)劃算法D.舍伍德算法答案：49.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的〔B〕。A、重疊子問題B、最優(yōu)子構(gòu)造性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：52.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為〔D〕。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：53.實現(xiàn)最長公共子序列利用的算法是〔B〕。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法54.算法分析的兩個主要方面是〔A〕。A.空間復(fù)雜度和時間復(fù)雜度B.正確性和簡單性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜度和程序復(fù)雜度55.計算機算法指的是〔C〕。A.計算方法B.排序方法C.解決問題的方法和過程D.調(diào)度方法56.多階段決策問題就是要在可以選擇的那些策略中間選取一個〔A〕策略使在預(yù)定的標(biāo)準(zhǔn)下到達最好的效果。A.最優(yōu)B.最差C.平衡D.任意57.根據(jù)排序元素所在位置的不同，排序分〔A〕。A.排序和外排序B.首排序和尾排序C.順序排序和逆序排序D.堆排序和棧排序58.算法必須具備輸入、輸出和〔B〕等5個特性。A.可執(zhí)行性、可移植性和可擴大性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和平安性59.與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題〔A〕。A.經(jīng)分解得到子問題往往不是互相獨立的B.經(jīng)分解得到子問題往往是互相獨立的C.經(jīng)分解得到子問題往往是互相穿插的D.經(jīng)分解得到子問題往往是任意的60.二分搜索算法的根本思想是將n個元素分成個數(shù)大致一樣的兩半，取a[n/2]與x進展比擬：如果〔A〕，那么只要在數(shù)組a的左半部繼續(xù)搜索x。A.x＜a[n/2]B.x=a[n/2]C.x>a[n/2]D.x>=a[n/2]61.活動安排問題就是在所給的活動集合中，選出〔C〕的相容活子集。A.最小B.任意C.最大D.一個62.在對問題的解空間樹進展搜索的方法中一個活結(jié)點最多有一次時機成為活結(jié)點的是〔B〕。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹問題63.適用動態(tài)規(guī)劃的問題必須滿足〔D〕。A.最優(yōu)化原理B.無前效性C.最優(yōu)化原理和后效性D.最優(yōu)化原理和無后效性64.算法的每種運算必須要有確切的定義不能有二義性，以下符合算法確定性運算的是〔B〕。A.5/0B.將6或7與x相加C.未賦值變量參與運算D.f(n)=f(n-1)+2，F(xiàn)(1)=10，n為自然數(shù)65.直接或間接的調(diào)用自身的算法稱為〔B〕。A.貪心算法B.遞歸算法C.迭代算法D.動態(tài)規(guī)劃算法66.二分查找只適用〔B〕存儲構(gòu)造。A.堆B.順序C.任意順序D.棧67.應(yīng)用分治法的兩個前提是〔A〕。A.問題的可分性和解的可歸并性B.問題的可分性和解的存在性C.問題的復(fù)雜性和解的可歸并性D.問題的可分性和解的復(fù)雜性68.優(yōu)先隊列的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的上下與p值大小相關(guān)，根據(jù)問題的不同情況，采用〔C〕來描述優(yōu)先隊列。A.先進先出隊列B.后進先出的棧C.最大堆或最小堆D.隨機序列69.階乘函數(shù)用遞歸定義Publicstaticintfactorial〔intn〕{if〔n==0〕return1；return〔B〕：}A.n*factorial(n)B.n*factorial(n-1)C.n*factorial(n-2)D.n*factorial(n+1)70.〔B〕能夠求得問題的解但卻無法有效地判定解的正確性。A.數(shù)值概率算法B.蒙特卡羅算法C.拉斯維加斯算法D.舍伍得算法71.對于n個元素的排序問題。n＝2時只要作〔C〕次比擬即可排好序。A.3B.2C.1D.472.一般地講，當(dāng)一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法和備忘錄算法相比：〔B〕。A.效果一樣B.動態(tài)規(guī)劃效果好C.備忘錄方法效果好D.無法判斷哪個效果好73.分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解，二者〔B〕。A.求解目標(biāo)不同搜索方式一樣B.求解目標(biāo)不同搜索方式也不同C.求解目標(biāo)一樣搜索方式不同D.求解目標(biāo)一樣搜索方式也一樣74.遞歸算法不能適用以下場合〔D〕。A.數(shù)據(jù)的定義形式按遞歸定義B.數(shù)據(jù)之間的關(guān)系即數(shù)據(jù)構(gòu)造按遞歸定義C.問題解法按遞歸算法實現(xiàn)D.概率問題75.假設(shè)當(dāng)子問題之間包含公共的子子問題時，那么分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時一般用〔A〕法較好。A.動態(tài)規(guī)劃B.分治C.貪心D.概率76.分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是〔C〕。A.該問題的規(guī)模縮小到一定的程度就可以容易地解決B.該問題可以分解為假設(shè)干個規(guī)模較小的一樣問題C.利用該問題分解出的子問題的解可以合并為該問題的解D.該問題所分解出的各個子問題是相互獨立的77.對于貨箱裝船問題根據(jù)貪心策略首先選擇〔A〕的貨箱然后選〔A〕的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。A.最輕次輕B.最重次重C.最輕次重D.最重次輕78.用回溯法解n后問題時，用完全n叉樹表示解空間?？尚行约s束place剪去不滿足行、列和斜線約束的子樹，place中的if判斷條件應(yīng)為〔A〕。A.(Math.abs(k-j)==Math.abs(x[j]-x[k]))||x[j]==x[k])B.(Math.abs(k-j)==Math.abs(x[j]-x[k]))C.(x[j]-x[k])D.以上都不正確79.分支限界法的搜索策略是：在擴展結(jié)點處，先生成其〔D〕兒子結(jié)點〔分支〕，然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值〔限界〕，并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。A.一個B.二個C.任意多個D.所有的80.能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征〔D〕這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。A.子問題的可求解性B.子問題的獨立性C.子問題的可合并性D.子問題的重疊性81.在任何一個的棋盤覆蓋中，用到的L型骨牌個數(shù)恰為〔A〕。A.B.C.D.82.以Bitonic旅行路線問題為例，動態(tài)規(guī)劃的時間復(fù)雜度為〔C〕。A.O(n)B.O(n!)C.O(n2)D.O(n3)一個算法應(yīng)該包含如下幾條性質(zhì)除了〔A〕。A．二義性B．有限性C．正確性可終止性解決一個問題通常有多種方法。假設(shè)說一個算法"有效〞是指〔D〕。A.這個算法能在一定的時間和空間資源限制將問題解決B．這個算法能在人的反響時間將問題解決C．這個算法比其他算法都更快地將問題解決A和C當(dāng)輸入規(guī)模為n時算法增長率最小的是〔B〕。A．B．C．D．86．漸進算法分析是指〔B〕。A.算法在最正確情況、最差情況和平均情況下的代價B.當(dāng)規(guī)模逐步往極限方向增大時對算法資源開銷"增長率〞上的簡化分析C.數(shù)據(jù)構(gòu)造所占用的空間D.在最小輸入規(guī)模下算法的資源代價87．當(dāng)上下限表達式相等時我們使用以下哪種表示法來描述算法代價"〔C〕A．大O表示法B．大Ω表示法C．Θ表示法小o表示法88.采用"順序搜索法〞從一個長度為N的隨機分布數(shù)組中搜尋值為K的元素，以下對順序搜索法分析正確的選項是〔B〕。A．最正確情況、最差情況和平均情況下順序搜索法的漸進代價都一樣B．最正確情況的漸進代價要好于最差情況和平均情況的漸進代價C．最正確情況和平均情況的漸進代價要好于最差情況的漸進代價D．最正確情況的漸進代價要好于平均情況的漸進代價而平均情況的漸進代價要好于最差情況的漸進代價89．遞歸通常用〔C〕來實現(xiàn)。A.有序的線性表B.隊列C.棧D.數(shù)組90.分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題〔C〕。A問題規(guī)模一樣，問題性質(zhì)一樣B問題規(guī)模一樣，問題性質(zhì)不同C問題規(guī)模不同，問題性質(zhì)一樣D問題規(guī)模不同，問題性質(zhì)不同91．在尋找n個元素中第k小元素問題中如快速排序算法思想運用分治算法對n個元素進展劃分如何選擇劃分基準(zhǔn)下面〔D〕答案解釋最合理。A．隨機選擇一個元素作為劃分基準(zhǔn)B．取子序列的第一個元素作為劃分基準(zhǔn)C．用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D．以上皆可行。但不同方法算法復(fù)雜度上界可能不同92.對于01背包問題和背包問題的解法下面〔C〕答案解釋正確。A．01背包問題和背包問題都可用貪心算法求解B．01背包問題可用貪心算法求解但背包問題那么不能用貪心算法求解C．01背包問題不能用貪心算法求解但可以使用動態(tài)規(guī)劃或搜索算法求解而背包問題那么可以用貪心算法求解D．因為01背包問題不具有最優(yōu)子構(gòu)造性質(zhì)所以不能用貪心算法求解93．關(guān)于回溯搜索法的介紹下面〔D〕是不正確描述。A．回溯法有"通用解題法〞之稱它可以系統(tǒng)地搜索一個問題的所有解或任意解B．回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C．回溯算法在生成解空間的任一結(jié)點時先判斷該結(jié)點是否可能包含問題的解如果肯定不包含那么跳過對該結(jié)點為根的子樹的搜索逐層向祖先結(jié)點回溯D．回溯算法需要借助隊列這種構(gòu)造來保存從根結(jié)點到當(dāng)前擴展結(jié)點的路徑94.關(guān)于回溯算法和分支限界法以下〔A〕是不正確描述。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é)點生成策略95.優(yōu)先隊列通常用以下〔B〕數(shù)據(jù)構(gòu)造來實現(xiàn)。A．棧B．堆C．隊列D．二叉查找樹96.在分支限界算法中根據(jù)從活結(jié)點表中選擇下一擴展結(jié)點的不同方式可有幾種常用分類，以下〔D〕描述最為準(zhǔn)確。A采用FIFO隊列的隊列式分支限界法B采用最小值堆的優(yōu)先隊列式分支限界法C采用最大值堆的優(yōu)先隊列式分支限界法D以上都常用針對具體問題可以選擇采用其中某種更為適宜的方式97.對布線問題以下〔C〕是不正確描述。A布線問題的解空間是一個圖B可以對方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡化對邊界的判定C采用廣度優(yōu)先的標(biāo)號法找到從起點到終點的布線方案這個方案如果存在的話不一定是最短的D采用先入先出的隊列作為活結(jié)點表以，終點b為擴展結(jié)點或活結(jié)點隊列為空作為算法完畢條件98.下述表達不正確的選項是〔D〕。A.的漸進表達式上界函數(shù)是B．的漸進表達式下界函數(shù)是C．的漸進表達式上界函數(shù)是D．的漸進表達式下界函數(shù)是99．當(dāng)輸入規(guī)模為n時，算法增長率最大的是〔A〕。A．B．C．D．100.T(n)表示當(dāng)輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是〔C〕。A．T(n)=T(n-1)+1，T(1)=1B．T(n)=2n2C.T(n)=T(n/2)+1，T(1)=1D.T(n)=3nlog2n101.有9個村莊，其坐標(biāo)位置如下表所示：i123456789x(i)123456789y(i)123456789現(xiàn)在要蓋一所郵局為這9個村莊效勞，請問郵局應(yīng)該蓋在〔C〕才能使郵局到9個村莊的距離和最短?！?.5，0〕〔4.5，4.5〕〔5，5〕〔5，0〕102.n個人拎著水桶在一個水龍頭前面排隊打水水桶有大有小水桶必須打滿水水流恒定。如下〔A〕說法不正確A．讓水桶大的人先打水可以使得每個人排隊時間之和最小B．讓水桶小的人先打水可以使得每個人排隊時間之和最小C．讓水桶小的人先打水在某個確定的時間t可以讓盡可能多的人打上水D．假設(shè)要在盡可能短的時間n個人都打完水按照什么順序其實都一樣103.對于含有n個元素的子集樹問題，最壞情況下其解空間的葉結(jié)點數(shù)目為〔B〕。104．以下關(guān)于判定問題難易處理的表達中正確的選項是〔C〕A.可以由多項式時間算法求解的問題是難處理的B.需要超過多項式時間算法求解的問題是易處理的C.可以由多項式時間算法求解的問題是易處理的D.需要超過多項式時間算法求解的問題是不能處理的105.回溯法在解空間樹T上的搜索方式是〔A〕深度優(yōu)先廣度優(yōu)先最小消耗優(yōu)先活結(jié)點優(yōu)先106.設(shè)f(N)，g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≤Cg(N)，那么稱函數(shù)f(N)當(dāng)N充分大時有上界g(N)，記作f(N)=O(g(N)),即f(N)的階〔A〕g(N)的階。不高于不低于C.等價于D.逼近107.以下〔C〕不能在線性時間完成排序A.計數(shù)排序B.基數(shù)排序C.堆排序D.桶排序108.以下〔A〕不一定得到問題的最優(yōu)解A.貪心算法B.回溯算法C.分支限界法D.動態(tài)規(guī)劃法109.以下不屬于一個好的算法應(yīng)具有的特性的是〔C〕。A.正確性B.簡明性C.無限性D.最優(yōu)性110.算法分析是〔C〕。A.將算法用某種程序設(shè)計語言恰當(dāng)?shù)乇硎境鰜鞡．在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會產(chǎn)生錯誤的結(jié)果C.對算法需要多少計算時間和存儲空間作定量分析D.證明算法對所有可能的合法輸入都能算出正確的答案111.學(xué)校要舉行運動會，請你設(shè)計一個能夠?qū)\發(fā)動分?jǐn)?shù)自動排序的軟件，如果要設(shè)計此軟件，以下最好的方法和步驟是〔C〕。A.分析問題，編寫程序，設(shè)計算法，調(diào)試程序B.設(shè)計算法，編寫程序，提出問題，調(diào)試程序C.提出問題，設(shè)計算法，編寫程序，調(diào)試程序D.設(shè)計算法，提出問題，編寫程序，調(diào)試程序112.考慮背包問題：n=6，M=10，V〔1:6〕=〔15，59，21，30，60，5〕，W〔1:6〕=〔1，5，2，3，6，1〕。該問題的最大效益值為〔C〕。A.101B.110C.115D.120113.考慮背包問題：n=6，M=10，V〔1:6〕=〔15，59，21，30，60，5〕，W〔1:6〕=〔1，5，2，3，6，1〕。假設(shè)把它看作是0/1背包問題，那么該問題的最大效益值為〔B〕。A.101B.110C.115D.120114.找最小生成樹的算法Kruskal的時間復(fù)雜度為〔D〕。A.O(n2)B.O(mlogn)C.O(nlogm)D.O(mlogm)115.算法與程序的區(qū)別在于算法具有〔C〕。A.能行性B.確定性C.有窮性D.輸入和輸出116.設(shè)A[1..60]={11,12,…,70}。算法折半查找在A上搜索x=33、7、70、77時執(zhí)行的元素比擬次數(shù)分別為a、b、c、d,那么〔C〕。A.a<b<c<dB.a>b=c=dC.a<b=c=dD.a<c<b=d117.算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上運行時執(zhí)行的元素比擬次數(shù)為〔D〕。A.14B.28C.7D.22118.voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的時間復(fù)雜度為〔A〕。A.O(2n)B.O(nlogn)C.D.119.當(dāng)一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差異時，可以使用〔B〕來消除或減少問題的好壞實例間的這種差異。A.數(shù)值概率算法B.舍伍德算法C.拉斯維加斯算法D.蒙特卡羅算法120.當(dāng)輸入規(guī)模為n時，算法增長率最快的是(C)。A.12nB.C.2n2D.121.關(guān)于0-1背包問題，以下描述正確的選項是〔D〕。A.可以使用貪心算法找到最優(yōu)解B.能找到多項式時間的有效算法C.使用教材介紹的動態(tài)規(guī)劃方法可求解任意0-1背包問題D.對于同一背包與一樣的物品，做背包問題取得的總價值一定大于等于做0-1背包問題。122.設(shè)有n項獨立的作業(yè){1,2,…,n},由m臺一樣的機器加工處理。作業(yè)i所需要的處理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但未完工前不準(zhǔn)中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機調(diào)度問題要求給出一種調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間由m臺機器處理完〔n>m〕。對于多級調(diào)度問題，使用哪種貪心策略比擬適宜〔B〕。A.作業(yè)從小到大依次分配給空閑的機器B.作業(yè)從大到小依次分配給空閑的機器C.每個機器分配一樣的作業(yè)數(shù)D.使用以上幾種貪心策略都能找到最優(yōu)解，所以都適宜123.使用二分搜索算法在1000個有序元素表中搜索一個特定元素，在最壞情況下，搜索總共需要比擬的次數(shù)為〔A〕。A.10B.11C.500D.1000124.用數(shù)量級形式表示算法的執(zhí)行時間稱為算法的〔A〕。A.時間復(fù)雜度B.空間復(fù)雜度C.處理器復(fù)雜度D.通信復(fù)雜度125.下面哪個問題不是典型的NP完全問題〔D〕。A.m-著色問題B.旅行商問題C.哈密爾頓回路問題D.排序問題126.順序查找的時間復(fù)雜度為〔A〕。A.O(n)B.O(logn)C.O(n2)D.O(nlogn)127.折半查找的時間復(fù)雜度為〔B〕。A.O(n)B.O(logn)C.O(n2)D.O(nlogn)128.算法的復(fù)雜性有時間復(fù)雜性和〔C〕復(fù)雜性之分。A.處理器復(fù)雜性B.通信復(fù)雜性C.空間復(fù)雜性D.存儲復(fù)雜性129.算法的復(fù)雜性有空間復(fù)雜性和〔C〕復(fù)雜性之分。A.處理器復(fù)雜性B.通信復(fù)雜性C.時間復(fù)雜性D.存儲復(fù)雜性130.算法是由假設(shè)干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。其中算法的"確定性〞是指組成算法的每條〔B〕是清晰的，無歧義的。A.程序B.指令C.語句D.語句塊131.(C)的根本運算是把兩個或多個有序序列合并成一個有序序列。A.快速排序B.希爾排序C.合并排序D.堆排序132.解決0/1背包問題可以使用動態(tài)規(guī)劃，回溯法，分支限界法。其中不需要排序的是〔A〕。A.動態(tài)規(guī)劃B.回溯法C.分支限界法D.以上3種方法都需要排序133.解決0/1背包問題時需要排序的方法是回溯法和〔B〕。A.動態(tài)規(guī)劃B.分支限界法C.貪心法D.線性規(guī)劃134.下面哪項是動態(tài)規(guī)劃算法根本要素之一〔D〕。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、最優(yōu)子構(gòu)造135.快速排序算法是基于〔A〕的一種排序算法。A.分治策略B.貪心C.回溯D.動態(tài)規(guī)劃136.〔C〕是貪心算法可行的第一個根本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。A、重疊子問題B、最優(yōu)子構(gòu)造C、貪心選擇性質(zhì)D、定義最優(yōu)解137.如果無向連通圖G中不包含任何關(guān)節(jié)點，那么稱該圖G為〔A〕。A.雙連通圖B.單連通圖C.強連通圖D.弱連通圖138.使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點的求解方法稱為〔D〕。A.動態(tài)規(guī)劃B.分支限界法C.貪心法D.回溯法139.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架和(A)算法框架。A.排列樹B.二叉樹C.B樹D.B+樹140.以下算法常以自頂向下的方式求解最優(yōu)解的是〔C〕。A.分治法B.動態(tài)規(guī)劃法C.貪心法D.回溯法141.哈夫曼編碼可利用〔C〕算法實現(xiàn)。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法142.在對問題的解空間樹進展搜索的方法中一個活結(jié)點有屢次時機成為活結(jié)點的是〔A〕。A.回溯法B.分支限界法C.回溯法和分支限界法D.動態(tài)規(guī)劃143、始皇吞并六國使用的遠交近攻逐個擊破的連橫策略采用了以下哪種算法思想(B)。A、遞歸B、分治C、迭代D、模擬。144、FIFO是〔A〕的一搜索方式。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法145、投點法是〔B〕的一種。A、分支界限算法B、概率算法C、貪心算法D、回溯算法146、假設(shè)線性規(guī)劃問題存在最優(yōu)解它一定不在〔C〕。A可行域的某個頂點上B可行域的某條邊上C可行域部D以上都不對147、在一般輸入數(shù)據(jù)的程序里輸入多多少少會影響到算法的計算復(fù)雜度，為了消除這種影響可用〔B〕對輸入進展預(yù)處理。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法148、假設(shè)L是一個NP完全問題L經(jīng)過多項式時間變換后得到問題l那么l是(A)。A、P類問題B、NP難問題C、NP完全問題D、P類語言149.不斷回頭尋找目標(biāo)的方法稱為〔C〕。A.動態(tài)規(guī)劃B.貪心法C.回溯法D.概率算法150.拉斯維加斯算法找到的解一定是〔B〕。A.不確定的B.正確的C.不正確的D.局部最優(yōu)的151.記號在算法復(fù)雜性的表示法中表示〔C〕。A.上界B.下界C.緊致界D.以上說法都不對152.一個無向連通圖不是雙向連通圖的充要條件是圖中存在〔B〕。A.回路B.關(guān)節(jié)點C.最大團D.最小團153.一個算法是對特定問題求解的一種描述，它是〔A〕。A.指令的有限序列B.程序的有限序列C.語句的有限序列D.代碼的有限序列154.矩陣乘法如下：for(i=0;i<n;i++)for(j=0;j<n;j++){C[i][j]=0;for(k=0;k<n;k++)C[i][j]+=a[i][k]*b[k][j];}它的漸近時間復(fù)雜度為〔B〕。A.O(n2)B.O(n3)C.O(n)D.O(n4)155.二分搜索過程的算法行為可以用一棵〔B〕來描述。A.二叉排序樹B.二叉判定樹C.子集樹D.排列樹156.用貪心法求解背包問題時，為了使收益最大化要選擇〔A〕的物品裝入背包。A.單位重量收益最大B.收益最大C.重量最大D.重量最小157.一個遞歸算法必須包括〔B〕。A.遞歸局部B.終止條件和遞歸局部C.迭代局部D.終止條件和迭代局部158.有六個元素6,5,4,3,2,1的順序進棧,那么以下哪一個不是合法的出棧序列〔C〕。A.543612B.453126C.346521D.234156159.棧和隊列的共同點是〔C〕。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點160.假設(shè)一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，那么度為0的結(jié)點個數(shù)是〔〕。A.9B.11C.15D.不確定161.排序趟數(shù)與原始序列有關(guān)的排序方法是〔C〕排序法。A.插入B.選擇C.冒泡D.快速162.如果給定權(quán)值總數(shù)有n個，那么其哈夫曼樹的結(jié)點總數(shù)為〔D〕。A.不確定B.2nC.2n+1D.2n-1163.一個棧的輸入序列為123…n，假設(shè)輸出序列的第一個元素是n,那么輸出第i〔〕個元素是〔B〕。A.不確定B.n-i+1C.iD.n-i164.以下序列中，〔C〕是執(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]165.以下哪個問題不能用貪心法求解？〔C〕A.哈夫曼編碼問題B.單源最短路徑問題C.0-1背包問題D.最小生成樹問題166.以下隨機算法一定有解但解不一定正確的選項是〔C〕。A.SherwoodB.LasVegasC.MonteCarloD.三者都不是167.在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實際價值的是〔B〕情況下的時間復(fù)雜度。A.最好B.最壞C.平均D.以上都不正確168.快速排序算法的性能取決于〔A〕。A.劃分的對稱性B.數(shù)據(jù)的原始序列C.隨機選擇策略D.以上都不正確169.回溯法在問題的解空間樹中，按〔B〕策略，從根節(jié)點出發(fā)搜索解空間樹。A.廣度優(yōu)先B.深度優(yōu)先C.隨機D.以上說法都不對170.大符號用來描述增長率的下限，這個下限的階越〔A〕，結(jié)果就越有價值。A.高B.低C.和具體問題有關(guān)D.以上都不正確171.設(shè)計動態(tài)規(guī)劃算法的步驟為：〔1〕找出最優(yōu)解的性質(zhì)，并刻畫其構(gòu)造特征?！?〕〔B〕?！?〕以自底向上的方式計算出最優(yōu)值。〔4〕計算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解。A.非遞歸的定義最優(yōu)值B.遞歸的定義最優(yōu)值C.迭代的定義最優(yōu)值D.遞推的定義最優(yōu)值172.設(shè)計動態(tài)規(guī)劃算法的步驟為：〔1〕找出最優(yōu)解的性質(zhì)，并刻畫其構(gòu)造特征。〔2〕遞歸的定義最優(yōu)值?！?〕〔A〕?！?〕計算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解。A.以自底向上的方式計算出最優(yōu)值B.以自頂向下的方式計算出最優(yōu)值C.迭代的方式計算出最優(yōu)值D.遞推的方式算出最優(yōu)值173.最優(yōu)二叉搜索樹即是〔A〕的二叉搜索樹。A.最小平均查找時間B.最小最壞查找時間C.最小平均存儲空間D.最小最壞存儲空間174.當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為〔C〕。A.24B.22C.20D.15175.9n2+10n的漸近表達式是〔A〕。A.O(n2)B.O(n3)C.O(n)D.O(n4)176.下面程序段的時間復(fù)雜度是〔C〕。for(i=0;i<n;i++)for(j=0;j<n;j++)A.O(n)B.O(n3)C.O(n2)D.O(n4)177.快速排序算法是基于分治策略的一個算法，其根本思想是，對于輸入的子數(shù)組a[p:r],按以下三個步驟進展排序：〔A〕。A.分解、遞歸求解、合并B.遞歸求解、分解、合并C.合并、遞歸求解、分解D.分解、合并、遞歸求解178.最優(yōu)裝載問題可用貪心算法求解，采用〔C〕先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。A.重量最重者B.單位重量收益大C.重量最輕者D.收益最大179.寫出以下f(n)的漸進性態(tài)，假設(shè)f(n)=C0，C0為常數(shù)，那么f(n)=〔A〕。A.O(1)B.O(n)C.O(n2)D.O(n3)180.寫出以下f(n)的漸進性態(tài)，假設(shè)f(n)=3n+2,那么f(n)=〔B〕。A.O(1)B.O(n)C.O(n2)D.O(n3)181.寫出以下f(n)的漸進性態(tài)，假設(shè)f(n)=6*2n+n,那么f(n)=〔B〕。A.O(1)B.O(2n)C.O(n2)D.O(n3)182.假設(shè)一個算法的時間復(fù)雜度用T(n)表示，其中n的含義是〔A〕。A.問題規(guī)模B.語句條數(shù)C.循環(huán)層數(shù)D.函數(shù)數(shù)量183.背包問題可獲得最優(yōu)解的輸入是按〔B〕。A.重量密度排序B.價值密度排序C.單位重量收益大小排序D.重量大小排序184.合并排序法的根本思想是：將待排序元素分成大小大致一樣的〔C〕個子集合，分別對每個子集合進展排序，最終將排好序的子集合合并成為所要求的排好序的集合。A.4B.3C.2D.5185.二分搜索算法的根本思想是將n個元素分成個數(shù)大致一樣的兩半，取a[n/2]與x進展比擬：如果〔C〕，那么只要在數(shù)組a的右半部繼續(xù)搜索x。A.x＜a[n/2]B.x=a[n/2]C.x>a[n/2]D.x>=a[n/2]186.當(dāng)問題規(guī)模n趨向于無窮大時，〔B〕的數(shù)量級〔階〕稱為算法的漸進時間復(fù)雜度。A.空間復(fù)雜度B.時間復(fù)雜度C.冗余度D.迭代次數(shù)187.通常用來表示時間算法的有以下六種多項式：O(1),O(n3),O(log2n),O(n2),O(n),O(nlog2n),按從小到大的順序排列是〔A〕。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)188.貪心方法是一種求〔C〕的方法。A.最小解B.最大解C.最優(yōu)解D.局部最優(yōu)解189.O(Pf(N))=O(f(N)),其中P是一個〔A〕。A.正的常數(shù)B.負(fù)的常數(shù)C.不確定D.以上說法都不對190.當(dāng)問題規(guī)模n趨向于無窮大時，時間復(fù)雜度的數(shù)量級〔階〕稱為算法的〔C〕。A.平均時間復(fù)雜度B.最壞時間復(fù)雜度C.漸進時間復(fù)雜度D.最優(yōu)時間復(fù)雜度191.f(n)=O(g(n))表示當(dāng)且僅當(dāng)存在正的常數(shù)C和N0，使得對于所有的n>=N0,有〔A〕。A.f(n)<=Cg(n)B.f(n)>=Cg(n)C.f(n)>Cg(n)D.f(n)=Cg(n)192.分支限界法與回溯法的一樣點是：都是一種在問題的〔D〕中搜索問題解的算法。A.子集樹TB.排列樹TC.二叉搜索樹TD.解空間樹T193.對于分支限界法與回溯法，下面