算法分析與設計復習題判斷題1選擇題：15判斷題算法就是一組有窮的規則。答案：正確概率算法中蒙特卡羅算法得到的解必是正確的。答案：錯誤程序和算法一樣，都是某種程序設計語言的具體實現。答案：錯誤合并排序算法是漸近最優算法。答案：正確遞歸定義必須是有確切含義是指必須一步比一步簡單，最后是有終結的，決不能無限循環下去。答案：正確二分搜索方法在最壞的情況下用0（10。n）時間完成搜索任務。答案：正確能否利用分治法完全取決于問題是否具有如下特征：利用該問題分解出的子問題的解可以合并為該問題的解。答案：正確分治法的基本思想是將一個規模較大的問題分解成若干個規模較小的子問題，這些子問題之間并不一定相互獨立。答案：錯誤遞歸算法的效率往往很低，費時和費存空間。答案：正確當一個問題具有最優子結構性質時只能用動態規劃方法求解。答案：錯誤如果一類活動過程一個階段的決策確定以后，常影響到下一個階段的決策，則稱它為多階段決策問題。答案：正確反復應用分治手段，不能使子問題與原問題類型一致而其規模卻不斷縮小。答案：錯誤裴波那契數列的定義：￡（口）=￡（口-1）+￡（口-2”（0）=廿（1）=2,其數據的定義形式不是按遞歸定義。答案：錯誤0-1背包問題與背包問題這兩類問題都可以用貪心算法求解。答案：錯誤證明貪心選擇后的問題簡化為規模更小的類似子問題的關鍵在于利用該問題的最優子結構性質。答案：錯誤子問題之間不包含公共的子問題，這個條件涉及到分治法的效率。答案：正確概率算法允許在執行過程中隨機地選擇下一個計算步驟。答案：正確二分搜索法的二分查找只適用于順序存儲結構。答案：正確要想在電腦上擴大所處理問題的規模，有效的途徑是降低算法的計算復雜度。答案：正確用回溯法解題一個顯著特征是在搜索過程中動態產生問題的解空間。答案：錯誤從分治法的一般設計模式可以看出，用它設計出的程序一般是一個遞歸過程。因此，分治法的計算效率通?？梢杂眠f歸方程來進行分析。答案：正確多階段決策問題中，每一個階段可能有若干個決策可供選擇答案：正確拉斯維加斯算法不會得到不正確的解，但有時找不到解。答案：正確在通往邊界條件的遞歸調用過程中，系統用堆棧保存的每次調用的中間結果是局部變量和返回地址值。答案：正確要想在電腦上擴大所處理問題的規模，有效的途徑是提高算法的計算復雜度。答案：錯誤程序必須滿足算法具有數據輸出的性質。答案：正確反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小答案：正確一個算法產生一個或多個輸出，它們是同輸入有某種特定關系的量答案：正確最優子結構性質特征反映了遞歸思想的應用答案：正確遞歸邊界本身并不使用遞歸的定義答案：正確用分治法求解一個問題，所需的時間是由子問題的個數、大小以及把這個問題分解為子問題所需的工作總量來確定的。答案：正確應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應至少包含問題的一個（最優）解。答案：正確好的約束函數能顯著地減少所生成的結點數，但這樣的約束函數往往計算量較大。因此，在選擇約束函數時通常存在生成結點數與約束函數計算量之間的折衷。答案：正確一個遞歸定義必須是有確切含義的，必須一步比一步簡單，最后是有終結的，不能無限循環下去。答案：正確最優子結構性質是應用分治法的前提。答案：正確操作系統，它是一個在無限循環中執行的程序，因而不是一個算法。答案：正確有些數據結構如二叉樹等，由于其本身的遞歸特性、特別適合用遞歸的形式來描述。答案：正確概率算法的一個基本特征是，對所求問題的同一個實例用同一個算法求解兩次一定能得到完全相同的效果。答案：錯誤問題可以分解為若干個規模較小的相同問題，即稱該問題具有最優子結構性質。答案：錯誤遞推是從邊界條件出發，通過遞推式達到邊界條件。答案：正確所有的遞歸函數都能找到對應的非遞歸定義。答案：正確定義遞歸函數時可以沒有初始值。答案：錯誤動態規劃算法的基本要素是最優子結構。答案：正確最優子結構性質是指原問題的最優解包含其子問題的最優解。答案：正確動態規劃算法求解問題時，分解出來的子問題相互獨立。答案：錯誤滿足貪心選擇性質必滿足最優子結構性質。答案：錯誤回溯法中限界函數的目的是剪去得不到最優解的子樹。答案：正確分支限界法類似于回溯法，也是一種在問題的解空間樹丁上搜索問題解的算法，兩者的搜索方式是相同的。答案：錯誤任何遞歸算法都有遞歸出口。答案：正確遞歸算法的執行效率比功能相同的非遞歸算法的執行效率高。答案：錯誤遞歸算法不能轉換成對應的非遞歸算法。答案：錯誤數據元素是數據的最小單位答案：錯誤數據對象就是一組數據元素的集合答案：錯誤任何數據結構都具備三個基本運算：插入、刪除和查找。答案：錯誤數據對象是由有限個類型相同的數據元素構成的。答案：正確數據的邏輯結構與各數據元素在計算機中如何存儲有關。答案：錯誤如果數據元素值發生改變，則數據的邏輯結構也隨之改變。答案：錯誤邏輯結構相同的數據，可以采用多種不同的存儲方法。答案：正確邏輯結構不相同的數據，必須采用不同的存儲方法來存儲。答案：錯誤數據的邏輯結構是指數據元素的各數據項之間的邏輯關系。答案：錯誤順序存儲方式只能用于存儲線性結構。答案：錯誤算法可以用不同的語言來描述，如果用C語言或Pascal語言等高級語言來描述，則算法就等同于程序。答案：錯誤數據的邏輯結構是指各數據元素之間的邏輯關系。答案：正確數據結構、數據元素、數據項在計算機中的映像（或表示）分別稱為存儲結構、節點和數據域。答案：正確數據的物理結構是指數據在計算機的實際存儲形式。答案：正確分配給單鏈表的存與地址必須是連續的。答案：錯誤從長度為n的順序表中刪除任何一個元素，時間復雜度都是0（口）。答案：錯誤向順序表中插入一個元素，平均要移動大約一半的元素。答案：正確凡是為空的單鏈表都是不含任何節點的。答案：錯誤如果單鏈表帶有頭節點，則插入操作永遠不會改變頭節點指針的值。答案：正確在循環單鏈表中，任何一個節點的指針域都不可能為空。答案：正確順序存儲方式的特點是存儲密度大且插入、刪除運算效率高。答案：錯誤線性表的順序存儲結構優于鏈式存儲結構。答案：錯誤順序存儲結構屬于靜態結構而鏈式存儲結構屬于動態結構。答案：正確由于順序存儲結構要求連續的存儲區域，所以在存儲管理上不夠靈活。答案：正確對于單鏈表來說，只有從頭節點開始才能掃描表中全部節點。答案：正確對于循環單鏈表來說，從表中任一節點出發都能掃描表中全部節點。答案：正確雙鏈表的特點是很容易找任一節點的前趨和后繼。答案：正確線性表有兩種存儲結構：一是順序表，二是鏈表。答案：正確如果有多個線性表同時共存，并且在處理過程中各表的長度會動態地發生變化，線性表的總數也會自動改變。在此情況下，應選用鏈式存儲結構。答案：正確若線性表的總數基本穩定且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，那么應該選用順序存儲結構。答案：正確對于單鏈表和雙鏈表，均能從當前節點出發訪問到任一節點。答案：錯誤循環單鏈表和循環雙鏈表從尾指針出發可以訪問到鏈表中的任意節點。答案：正確若頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用鏈式存儲結構。答案：正確棧底元素是不能刪除的元素。答案：錯誤順序棧中元素值的大小是有序的。答案：錯誤棧頂元素和棧底元素有可能是同一個元素。答案：正確若用$[1…團]表示順序棧的存儲空間，則對棧的進棧、出棧操作最多只能進行團次。答案：錯誤棧是一種對進棧、出棧操作總次數作了限制的線性表。答案：錯誤空棧沒有棧頂指針答案：錯誤環形隊列中有多少元素，可以根據隊首指針和隊尾指針的值來計算。答案：正確無論是順序隊列，還是鏈式隊列，插入、刪除運算的時間復雜度都是0(1)。答案：正確棧和隊列都是插入和刪除操作受限的線性表。答案：正確棧和隊列的存儲方式既可以是順序方式，也可以是鏈式方式答案：正確環形隊列也存在空間溢出的問題答案：正確消除遞歸不一定需要使用棧。答案：正確二分搜索算法是利用貪心法實現的算法。答案：錯誤動態規劃算法通常是以自底向上的方式求解最優解。答案：正確貪心法不能解決0/1背包問題。答案：正確深度優先不是分支限界法的搜索方式。答案：正確二分搜索算法是利用分治策略實現的算法。答案：正確背包問題不能使用貪心法解決。答案：錯誤單源最短路徑問題不能使用貪心法解決。答案：錯誤時間復雜度低是衡量一個算法好壞的標準。答案：正確歸并排序不可以使用分治法求解。答案：錯誤拉斯維加斯算法有時找不到問題的解。答案：正確舍伍德算法有時候找不到問題的解。答案：錯誤NP問題都是不可能解決的問題答案：錯誤P類問題包含在NP類問題中。答案：正確NP類問題包含在P類問題中。答案：錯誤NP完全問題是P類問題的子集答案：錯誤112.蒙特卡羅算法是概率算法的一種答案：正確113.蒙特卡羅算法是貪心算法的一種答案：錯誤114.蒙特卡羅算法是回溯算法的一種答案：錯誤115.動態規劃算法不是隨機化算法答案：正確116.最優子結構性質是貪心算法與動態規劃算法的共同點答案：正確117.矩陣連乘問題的算法可由動態規劃算法來設計實現答案：正確Strassen矩陣乘法是利用分治策略實現的算法答案：正確Strassen矩陣乘法是利用貪心法實現的算法答案：錯誤120.貪心選擇性質是貪心算法的基本要素答案：正確121.以深度優先方式系統搜索問題解的算法稱為回溯算法答案：正確122.算法分析的兩個主要方面是時間復雜度和空間復雜度分析答案：正確123.實現最大子段和利用的算法是動態規劃法答案：正確124.實現最大子段和利用的算法是貪心法答案：錯誤125.實現最大子段和利用的算法是回溯法答案：錯誤126.廣度優先是分支限界算法的一種搜索方式答案：正確127.廣度優先是回溯算法的一種搜索方式答案：錯誤128.廣度優先是貪心算法的一種搜索方式答案：錯誤129.舍伍德算法是概率算法的一種答案：正確130.舍伍德算法是貪心算法的一種。答案：錯誤131.舍伍德算法是回溯算法的一種。答案：錯誤132.實現最長公共子序列利用的算法是動態規劃法。答案：正確133.計算機算法指的是解決問題的方法和過程。答案：正確134.根據排序元素所在位置的不同，排序分排序和外排序。答案：正確135.根據排序元素所在位置的不同，排序分首排序和尾排序。答案：錯誤136.算法必須具備輸入、輸出和有窮性、確定性和可行性等5個特性。答案：正確137.算法必須具備輸入、輸出和易讀性、穩定性和安全性等5個特性。答案：錯誤138.與分治法不同的是，適合于用動態規劃求解的問題經分解得到的子問題往往不是相互獨立的139.與分治法不同的是，適合于用動態規劃求解的問題往往是相互獨立的答案：錯誤140.二分搜索算法的基本思想是將n個元素分成個數大致相同的兩半，取2巾/2]與x進行比較：如果*<2巾/2],則只要在數組a的左半部繼續搜索x答案：正確141.二分搜索算法的基本思想是將n個元素分成個數大致相同的兩半，取2巾/2]與x進行比較：如果*>2巾/2],則只要在數組a的左半部繼續搜索x答案：錯誤142.算法必須具備輸入、輸出和可執行性、可移植性和可擴充性等5個特性。答案：錯誤143.適用動態規劃的問題必須滿足最優化原理和無后效性。答案：正確144.適用動態規劃的問題必須滿足最優化原理和后效性。答案：錯誤145.二分查找只適用于順序存儲結構。答案：正確146.二分查找只適用于鏈式存儲結構。答案：錯誤147.應用分治法的兩個前提是問題的可分性和解的可歸并性。答案：正確148.應用分治法的兩個前提是問題的可分性和解的復雜性。答案：錯誤.對于口個元素的排序問題。n=2時只要作1次比較即可排好序。答案：正確.對于口個元素的排序問題。n=2時要作2次比較即可排好序。答案：錯誤.分治法所能解決的問題應具有的關鍵特征是利用該問題分解出的子問題的解可以合并為該問題的解。答案：正確.分治法所能解決的問題應具有的關鍵特征是該問題的規?？s小到一定的程度就可以容易地解決。答案：錯誤153.直接或間接的調用自身的算法稱為遞歸算法。答案：正確154.直接或間接的調用自身的算法稱為動態規劃算法。答案：錯誤.當上下限表示相等時我們使用0表示法來描述算法代價。答案：正確.當上下限表示相等時我們使用大0表示法來描述算法代價。答案：錯誤.遞歸通常用棧來實現。答案：正確.遞歸通常用隊列來實現。答案：錯誤.分治法的設計思想是將一個難以直接解決的大問題分割成規模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題的問題規模不同，問題性質相同。答案：正確.0/1背包問題不能用貪心算法求解。答案：正確.可以由多項式時間算法求解的問題是易處理的。答案：正確.可以由多項式時間算法求解的問題是難處理的。答案：錯誤.需要超過多項式時間算法求解的問題是不能處理的。答案：錯誤.遞歸通常用數組來實現。答案：錯誤.哈密爾頓回路問題是典型的NP完全問題。答案：正確166.排序問題是典型的NP完全問題。答案：錯誤167.算法分析需要對算法需要多少計算時間和存儲空間作定量分析。答案：正確168.用數量級形式表示算法的執行時間稱為算法的時間復雜度。答案：正確169.用數量級形式表示算法的執行時間稱為算法的空間復雜度。答案：錯誤170.最壞情況下，順序查找的時間復雜度為。（口）。答案：正確171.最壞情況下，折半查找的時間復雜度為0（10。加。答案：正確172.合并排序的基本運算是把兩個或多個有序序列合并成一個有序序列答案：正確173.最優子結構是動態規劃算法的基本要素之一。答案：正確174.快速排序算法是基于分治策略的一種排序算法。答案：正確175.快速排序算法是基于回溯的一種排序算法。答案：錯誤176.快速排序算法是基于貪心法的一種排序算法。答案：錯誤177.貪心法通常以自頂向下的方式求解最優解。答案：正確178.分治法通常以自頂向下的方式求解最優解。答案：錯誤179.回溯法通常以自頂向下的方式求解最優解。答案：錯誤180.不斷回頭尋找目標的方法稱為回溯法。181.不斷回頭尋找目標的方法稱為概率算法。答案：錯誤182.不斷回頭尋找目標的方法稱為貪心法。答案：錯誤183.拉斯維加斯算法找到的解一定是正確的。答案：正確184.拉斯維加斯算法找到的解正確與否不確定。答案：錯誤0記號在算法復雜性的表示法中表示緊致界。答案：正確0記號在算法復雜性的表示法中表示上界。答案：錯誤0記號在算法復雜性的表示法中表示下界。答案：錯誤188.一個算法是對特定問題求解的一種描述，它是指令的有限序列。答案：正確189.一個遞歸算法必須包括終止條件和遞歸部分。答案：正確190.棧和隊列的共同點是只允許在端點處插入和刪除元素。答案：正確191.排序趟數與原始序列有關的排序方法是冒泡排序法。答案：正確192.棧和隊列的共同點都是先進先出。答案：錯誤193.棧和隊列的共同點都是先進后出。答案：錯誤194.排序趟數與原始序列有關的排序方法是選擇排序法。答案：錯誤在算法的三種情況下的復雜性中，可操作性最好且最有實際價值的是最壞情況下的時間復雜度。答案：正確在算法的三種情況下的復雜性中，可操作性最好且最有實際價值的是最好情況下的時間復雜度。答案：錯誤若一個算法的時間復雜度用?。冢┍硎荆渲锌诘暮x是問題規模。答案：正確198.合并排序法的基本思想是：將待排序元素分成大小大致相同的2個子集合，分別對每個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。答案：正確選擇題：.二分搜索算法是利用（A）實現的算法。選項A.分治策略選項B.動態規劃法選項C.貪心法選項D.回溯法答案：.回溯法解旅行售貨員問題時的解空間樹是（B）。選項A.子集樹選項B.排列樹選項C.深度優先生成樹選項D.廣度優先生成樹答案：.下列算法常以自底向上的方式求解最優解的是（B）。選項A.備忘錄法選項B.動態規劃法選項C.貪心法選項D.回溯法答案：.下面不是分支界限法搜索方式的是（D）。選項A.廣度優先選項B.最小耗費優先選項C.最大效益優先選項D.深度優先5．采用貪心算法的最優裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復雜度（B）。A、O（）B、O（nlogn）C、O（）D、O（n）.分支限界法求解最大團問題時，活結點表的組織形式是（B）。人、最小堆8、最大堆C、?？凇到M7、下面問題（B）不能使用貪心法解決。A單源最短路徑問題BN皇后問題C最小花費生成樹問題D背包問題答案：.下列算法中不能解決0/1背包問題的是（A）。A貪心法B動態規劃C回溯法D分支限界法答案：.背包問題的貪心算法所需的計算時間為（B）。A、O（n）B、O（nlogn）C、O（）D、O（n）答案：.二分搜索算法是利用（A）實現的算法。A.分治策略B、動態規劃法5貪心法口、回溯法答案：.下列不是動態規劃算法基本步驟的是（B）。人、找出最優解的性質8、構造最優解^算出最優解□、定義最優解答案：12．最大效益優先是（A）的一種搜索方式。人、分支界限法B、動態規劃法5貪心法D.回溯法答案：13、在下列算法中有時找不到問題解的是（B）。人、蒙特卡羅算法8、拉斯維加斯算法5舍伍德算法口、數值概率算法答案：.下列算法常以自底向上的方式求解最優解的是（B）。A、備忘錄法B、動態規劃法5貪心法口、回溯法答案：.下列算法常以自底向上的方式求解最優解的是（B）。A、備忘錄法B、動態規劃法5貪心法口、回溯法答案：15、衡量一個算法好壞的標準是（C）。A運行速度快B占用空間少C時間復雜度低D代碼短答案：16、以下不可以使用分治法求解的是（D）。人、棋盤覆蓋問題B、選擇問題C、歸并排序D、0/1背包問題答案：17.實現循環賽日程表利用的算法是（A）人、分治策略B、動態規劃法5貪心法D.回溯法答案：18、下列隨機算法中運行時有時候成功有時候失敗的是（C）A數值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法答案：19．下面不是分支界限法搜索方式的是（D）。A、廣度優先8、最小耗費優先5最大效益優先口、深度優先答案：.下列算法常以深度優先方式系統搜索問題解的是（D）。A、備忘錄法B、動態規劃法5貪心法口、回溯法答案：.備忘錄方法是那種算法的變形。（B）。人、分治法B、動態規劃法5貪心法口、回溯法答案：22．哈弗曼編碼的貪心算法所需的計算時間為（B）。A、O（n）B、O（nlogn）C、O（）D、O（n）答案：23．最長公共子序列算法利用的算法是（B）人、分支界限法B、動態規劃法5貪心法D.回溯法答案：24．實現棋盤覆蓋算法利用的算法是（A）。八、分治法B、動態規劃法5貪心法D.回溯法答案：.下面是貪心算法的基本要素的是（C）。A、重疊子問題8、構造最優解5貪心選擇性質□、定義最優解.回溯法的效率不依賴于下列哪些因素（D）。滿足顯約束的值的個數C.計算限界函數的時間計算約束函數的時間D.確定解空間的時間27.下面哪種函數是回溯法中為避免無效搜索采取的策略（B）。A遞歸函數B.剪枝函數^隨機數函數口.搜索函數28、下面關于NP問題說確的是（B）。A.NP問題都是不可能解決的問題B.P類問題包含在NP類問題中CNP完全問題是P類問題的子集D.NP類問題包含在P類問題中29、蒙特卡羅算法是（B）的一種。分支界限算法概率算法貪心算法回溯算法答案：.下列哪一種算法不是隨機化算法（C）。蒙特卡羅算法拉斯維加斯算法動態規劃算法口舍伍德算法答案：.（D）是貪心算法與動態規劃算法的共同點。A、重疊子問題8、構造最優解5貪心選擇性質口、最優子結構性質答案：32.矩陣連乘問題的算法可由（B）設計實現。人、分支界限算法B、動態規劃算法C、貪心算法口、回溯算法答案：33、Strassen矩陣乘法是利用（A）實現的算法。人、分治策略B、動態規劃法5貪心法口、回溯法答案：34、使用分治法求解不需要滿足的條件是（A）。A子問題必須是一樣的B子問題不能夠重復C子問題的解可以合并D原問題和子問題使用相同的方法求解35、回溯法搜索狀態空間樹是按照（0的順序。A中序遍歷B廣度優先遍歷C深度優先遍歷D層次優先遍歷答案：36、實現合并排序利用的算法是（A）人、分治策略B、動態規劃法5貪心法D.回溯法答案：37、下列是動態規劃算法基本要素的是（D）人、定義最優解8、構造最優解^算出最優解口、子空間重疊性質答案：38.采用廣度優先策略搜索的算法是（A）人、分支界限法B、動態規劃法5貪心法口、回溯法答案：39、在下列算法中得到的解未必正確的是（A）人、蒙特卡羅算法8、拉斯維加斯算法5舍伍德算法口、數值概率算法答案：40．實現大整數的乘法是利用的算法（C）人、貪心法B、動態規劃法^分治策略口、回溯法答案：.0-1背包問題的回溯算法所需的計算時間為（A）A、O（n）B、O（nlogn）C、O（）D、O（n）答案：.貪心算法與動態規劃算法的主要區別是（B）人、最優子結構8、貪心選擇性質^構造最優解□、定義最優解答案：.實現最大子段和利用的算法是（B）。人、分治策略B、動態規劃法5貪心法口、回溯法答案：.優先隊列式分支限界法選取擴展結點的原則是（C人、先進先出8、后進先出^結點的優先級口、隨機答案：45、廣度優先是（A）的一種搜索方式。人、分支界限算法B、動態規劃法C、貪心算法口、回溯算法答案：46、舍伍德算法是（B）的一種人、分支界限算法8、概率算法C、貪心算法口、回溯算法答案：47、在下列算法中有時找不到問題解的是（B）人、蒙特卡羅算法8、拉斯維加斯算法5舍伍德算法口、數值概率算法答案：48下列哪一種算法是隨機化算法（D）。貪心算法回溯法動態規劃算法舍伍德算法答案：49.一個問題可用動態規劃算法或貪心算法求解的關鍵特征是問題的（B）。A、重疊子問題8、最優子結構性質5貪心選擇性質□、定義最優解答案：.以深度優先方式系統搜索問題解的算法稱為（D）。人、分支界限算法8、概率算法C、貪心算法口、回溯算法答案：.實現最長公共子序列利用的算法是（B）。人、分治策略B、動態規劃法5貪心法口、回溯法.算法分析的兩個主要方面是（A）。空間復雜度和時間復雜度正確性和簡單性可讀性和文檔性數據復雜度和程序復雜度.計算機算法指的是（C）。計算方法排序方法解決問題的方法和過程調度方法56.多階段決策問題就是要在可以選擇的那些策略中間選取一個（A）策略使在預定的標準下達到最好的效果。最優最差平衡任意.根據排序元素所在位置的不同，排序分（A）。排序和外排序首排序和尾排序順序排序和逆序排序堆排序和棧排序.算法必須具備輸入、輸出和（B）等5個特性。可執行性、可移植性和可擴充性可行性、確定性和有窮性確定性、有窮性和穩定性易讀性、穩定性和安全性.與分治法不同的是，適合于用動態規劃求解的問題（A）。經分解得到子問題往往不是互相獨立的經分解得到子問題往往是互相獨立的^經分解得到子問題往往是互相交叉的D.經分解得到子問題往往是任意的.二分搜索算法的基本思想是將n個元素分成個數大致相同的兩半，取2巾/2]與x進行比較：如果（A），則只要在數組a的左半部繼續搜索x。x<a[n/2]x=a[n/2]x>a[n/2]x>=a[n/2].活動安排問題就是在所給的活動集合中，選出（C）的相容活子集。最小任意最大一個.在對問題的解空間樹進行搜索的方法中一個活結點最多有一次機會成為活結點的是（B）?；厮莘ǚ种藿绶ɑ厮莘ê头种藿绶ɑ厮莘ㄇ蠼庾蛹瘶鋯栴}.適用動態規劃的問題必須滿足(D)。最優化原理無前效性最優化原理和后效性最優化原理和無后效性.算法的每種運算必須要有確切的定義不能有二義性，以下符合算法確定性運算的是(B)。A.5/08.將6成7與*相加^未賦值變量參與運算D.f(n)=f(n-1)+2,F(1)=10,n為自然數.直接或間接的調用自身的算法稱為(B)。貪心算法遞歸算法迭代算法動態規劃算法.二分查找只適用(B)存儲結構。堆順序任意順序棧.應用分治法的兩個前提是(A)。問題的可分性和解的可歸并性問題的可分性和解的存在性問題的復雜性和解的可歸并性問題的可分性和解的復雜性68.優先隊列的分支限界法將活結點表組織成一個優先隊列，并按優先隊列中規定的結點優先級選取優先級最高的下一個結點成為當前擴展結點。優先隊列中規定的結點優先級常用一個與該結點相關的數值口來表示。結點優先級的高低與口值大小相關，根據問題的不同情況，采用(C)來描述優先隊列。先進先出隊列后進先出的棧最大堆或最小堆隨機序列69.階乘函數用遞歸定義Publicstaticintfactorial(intn){if(n==0)return1；return(B)：}A.n*factorial(n)n*factorial(n-1)n*factorial(n-2)n*factorial(n+1).(B)能夠求得問題的解但卻無法有效地判定解的正確性。數值概率算法蒙特卡羅算法拉斯維加斯算法舍伍得算法.對于口個元素的排序問題?？?2時只要作(C)次比較即可排好序。3214.一般地講，當一個問題的所有子問題都至少要解一次時，用動態規劃算法和備忘錄算法相比：(B)。效果一樣動態規劃效果好備忘錄方法效果好無法判斷哪個效果好.分支限界法與回溯法都是在問題的解空間樹丁上搜索問題的解，二者(B)。求解目標不同搜索方式相同求解目標不同搜索方式也不同求解目標相同搜索方式不同求解目標相同搜索方式也相同.遞歸算法不能適用以下場合(D)。數據的定義形式按遞歸定義數據之間的關系即數據結構按遞歸定義問題解法按遞歸算法實現概率問題.若當子問題之間包含公共的子子問題時，則分治法要做許多不必要的工作，重復地解公共的子問題，此時一般用(A)法較好。動態規劃分治貪心概率.分治法所能解決的問題應具有的關鍵特征是(C)。該問題的規模縮小到一定的程度就可以容易地解決該問題可以分解為若干個規模較小的相同問題利用該問題分解出的子問題的解可以合并為該問題的解該問題所分解出的各個子問題是相互獨立的.對于貨箱裝船問題根據貪心策略首先選擇(A)的貨箱然后選(A)的貨箱如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。最輕次輕最重次重最輕次重口.最重次輕.用回溯法解口后問題時，用完全口叉樹表示解空間?？尚行约s束口蹌6剪去不滿足行、列和斜線約束的子樹，口蹌0中的if判斷條件應為(A)。(Math.abs(k-j)==Math.abs(x[j]-x[k]))||x[j]==x[k])(Math.abs(k-j)==Math.abs(x[j]-x[k]))(x[j]-x[k])以上都不正確79.分支限界法的搜索策略是：在擴展結點處，先生成其(D)兒子結點(分支)，然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數值(限界)，并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。一個二個任意多個所有的.能夠用動態規劃解決的問題還有一個顯著特征(D)這個性質并不是動態規劃適用的必要條件，但是如果該性質無法滿足，動態規劃算法同其他算法相比就不具備優勢。子問題的可求解性子問題的獨立性子問題的可合并性子問題的重疊性.在任何一個2k*2k的棋盤覆蓋中，用到的1型骨牌個數恰為(A)。(4k—1)/3(4k—1)/2(2k—1)/3(2k—1)/2.以8計^匕旅行路線問題為例，動態規劃的時間復雜度為（C）。O（n）O（n!）O（n2）O（n3）.一個算法應該包含如下幾條性質除了（A）。人二義性8.有限性^正確性D.可終止性.解決一個問題通常有多種方法。若說一個算法“有效”是指（D）。A.這個算法能在一定的時間和空間資源限制將問題解決B.這個算法能在人的反應時間將問題解決C.這個算法比其他已知算法都更快地將問題解決D.A和C.當輸入規模為n時算法增長率最小的是（B）。5n20log2n2n23nlog3n.漸進算法分析是指（B）。算法在最佳情況、最差情況和平均情況下的代價當規模逐步往極限方向增大時對算法資源開銷“增長率”上的簡化分析數據結構所占用的空間在最小輸入規模下算法的資源代價.當上下限表達式相等時我們使用下列哪種表示法來描述算法代價?（C人大0表示法B.大Q表示法C.一表示法D.小。表示法88.采用“順序搜索法”從一個長度為N的隨機分布數組中搜尋值為K的元素，以下對順序搜索法分析正確的是（B）。人最佳情況、最差情況和平均情況下順序搜索法的漸進代價都相同8.最佳情況的漸進代價要好于最差情況和平均情況的漸進代價C最佳情況和平均情況的漸進代價要好于最差情況的漸進代價口.最佳情況的漸進代價要好于平均情況的漸進代價而平均情況的漸進代價要好于最差情況的漸進代價.遞歸通常用（C）來實現。有序的線性表隊列棧數組.分治法的設計思想是將一個難以直接解決的大問題分割成規模較小的子問題分別解決子問題最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（C）。A問題規模相同，問題性質相同B問題規模相同，問題性質不同C問題規模不同，問題性質相同D問題規模不同，問題性質不同.在尋找n個元素中第卜小元素問題中如快速排序算法思想運用分治算法對口個元素進行劃分如何選擇劃分基準下面（D）答案解釋最合理。人隨機選擇一個元素作為劃分基準8.取子序列的第一個元素作為劃分基準C.用中位數的中位數方法尋找劃分基準口.以上皆可行。但不同方法算法復雜度上界可能不同92.對于01背包問題和背包問題的解法下面（C）答案解釋正確。人01背包問題和背包問題都可用貪心算法求解01背包問題可用貪心算法求解但背包問題則不能用貪心算法求解01背包問題不能用貪心算法求解但可以使用動態規劃或搜索算法求解而背包問題則可以用貪心算法求解口.因為01背包問題不具有最優子結構性質所以不能用貪心算法求解93.關于回溯搜索法的介紹下面（D）是不正確描述。人回溯法有“通用解題法”之稱它可以系統地搜索一個問題的所有解或任意解8.回溯法是一種既帶系統性又帶有跳躍性的搜索算法C.回溯算法在生成解空間的任一結點時先判斷該結點是否可能包含問題的解如果肯定不包含則跳過對該結點為根的子樹的搜索逐層向祖先結點回溯口.回溯算法需要借助隊列這種結構來保存從根結點到當前擴展結點的路徑.關于回溯算法和分支限界法以下（A）是不正確描述。人回溯法中每個活結點只有一次機會成為擴展結點B分支限界法中活結點一旦成為擴展結點就一次性產生其所有兒子結點在這些兒子結點中那些導致不可行解或導致非最優解的兒子結點被舍棄其余兒子加入活結點表中C回溯法采用深度優先的結點生成策略口分支限界法采用廣度優先或最小耗費優先最大效益優先的結點生成策略.優先隊列通常用以下（B）數據結構來實現。A棧BT^隊列口.二叉查找樹.在分支限界算法中根據從活結點表中選擇下一擴展結點的不同方式可有幾種常用分類，以下（D）描述最為準確。A采用FIFO隊列的隊列式分支限界法8采用最小值堆的優先隊列式分支限界法C采用最大值堆的優先隊列式分支限界法口以上都常用針對具體問題可以選擇采用其中某種更為合適的方式.對布線問題以下（C）是不正確描述。A布線問題的解空間是一個圖B可以對方格陣列四周設置圍墻，即增設標記的附加方格的預處理，使得算法簡化對邊界的判定C采用廣度優先的標號法找到從起點到終點的布線方案這個方案如果存在的話不一定是最短的口采用先人先出的隊列作為活結點表以，終點匕為擴展結點或活結點隊列為空作為算法結束條件.下述表達不正確的是（D）。n2/2+2n的漸進表達式上界函數是。（2n）n2/2+2n的漸進表達式下界函數是Q（2n）Clogn3的漸進表達式上界函數是^（logn）D.logn3的漸進表達式下界函數是0（n3）99.當輸入規模為n時，算法增長率最大的是（A）。A．5nB．20log2nC．2n2D．3nlogn100.?。冢┍硎井斴斎胍幠榭跁r的算法效率，以下算法效率最優的是（C）。A．T（n）=T（n-1）+1，T（1）=1B．T（n）=2n2T（n）=T（n/2）+1，T（1）=1T（n）=3nlog2n101.有9個村莊，其坐標位置如下表所示：i123456789x(i)123456789y(i)123456789現在要蓋一所郵局為這9個村莊服務，請問郵局應該蓋在（C）才能使郵局到9個村莊的距離和最短。A.（4.5，0）B.（4.5，4.5）C.（5，5）D.（5，0）.n個人拎著水桶在一個水龍頭前面排隊打水水桶有大有小水桶必須打滿水水流恒定。如下（A）說法不正確A讓水桶大的人先打水可以使得每個人排隊時間之和最小B.讓水桶小的人先打水可以使得每個人排隊時間之和最小^讓水桶小的人先打水在某個確定的時間t可以讓盡可能多的人打上水口.若要在盡可能短的時間n個人都打完水按照什么順序其實都一樣.對于含有n個元素的子集樹問題，最壞情況下其解空間的葉結點數目為（B）。n!2n2n+i—1D.工n!/i!i=1104.以下關于判定問題難易處理的敘述中正確的是(C)人可以由多項式時間算法求解的問題是難處理的8.需要超過多項式時間算法求解的問題是易處理的^可以由多項式時間算法求解的問題是易處理的口.需要超過多項式時間算法求解的問題是不能處理的.回溯法在解空間樹丁上的搜索方式是(A)深度優先廣度優先最小耗費優先活結點優先.設￡3),。3)是定義在正數集上的正函數，如果存在正的常數C和自然數N0,使得當N>N0時有f(N)<Cg(N)，則稱函數f(N)當N充分大時有上界。3),記作f(N)=O(g(N)),即f(N)的階(A)。3)的階。不高于不低于等價于逼近.以下(C)不能在線性時間完成排序A.計數排序8.基數排序0堆排序口.桶排序.以下(A)不一定得到問題的最優解A.貪心算法8.回溯算法^分支限界法D.動態規劃法.下列不屬于一個好的算法應具有的特性的是（C）。正確性簡明性無限性最優性.算法分析是（C）。A.將算法用某種程序設計語言恰當地表示出來8.在抽象數據集合上執行程序，以確定是否會產生錯誤的結果對算法需要多少計算時間和存儲空間作定量分析證明算法對所有可能的合法輸入都能算出正確的答案111.學校要舉行運動會，請你設計一個能夠對運動員分數自動排序的軟件，如果要設計此軟件，以下最好的方法和步驟是（C）。分析問題，編寫程序，設計算法，調試程序設計算法，編寫程序，提出問題，調試程序提出問題，設計算法，編寫程序，調試程序設計算法，提出問題，編寫程序，調試程序112.考慮背包問題：n=6,M=10,V(1:6)=(15,59,21,30,60,5),W(1:6)=(1,5,2,3,6,1)。該問題的最大效益值為(C)。101110115D.120113.考慮背包問題：n=6,M=10,V(1:6)=(15,59,21,30,60,5),W(1:6)=(1,5,2,3,6,1)。若把它看作是0/1背包問題，則該問題的最大效益值為(B)。101110115D.120114.我最小生成樹的算法Kruskal的時間復雜度為（D）。O（n2）O（mlogn）C.O(nlogm)D.O(mlogm).算法與程序的區別在于算法具有（C）。能行性確定性有窮性輸入和輸出.設A[1..60]={11,12，…,70}。算法折半查找在人上搜索*=33、7、70、77時執行的元素比較次數分別為a、b、c、d,則（C）。a<b<c<da>b=c=da<b=c=da<c<b=d算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上運行時執行的元素比較次數為（D）。1428722voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的時間復雜度為(A)。O(2n)O(nlogn)9(n!)9(nn)當一個確定性算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以使用（B）來消除或減少問題的好壞實例間的這種差別。數值概率算法舍伍德算法拉斯維加斯算法蒙特卡羅算法120.當輸入規模為n時，算法增長率最快的是（C）。A.12nB.100log2n2n23nlog3n121.關于0-1背包問題，以下描述正確的是（D）。可以使用貪心算法找到最優解能找到多項式時間的有效算法使用教材介紹的動態規劃方法可求解任意0-1背包問題對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做0-1背包問題。122.設有口項獨立的作業{1,2,…,n},由m臺相同的機器加工處理。作業》所需要的處理時間為八約定：任何一項作業可在任何一臺機器上處理，但未完工前不準中斷處理；任何作業不能拆分更小的子作業。多機調度問題要求給出一種調度方案，使所給的口個作業在盡可能短的時間由m臺機器處理完（口＞團）。對于多級調度問題，使用哪種貪心策略比較合適（B）。作業從小到大依次分配給空閑的機器作業從大到小依次分配給空閑的機器每個機器分配一樣的作業數使用以上幾種貪心策略都能找到最優解，所以都合適123.使用二分搜索算法在1000個有序元素表中搜索一個特定元素，在最壞情況下，搜索總共需要比較的次數為（A）。10115001000124.用數量級形式表示算法的執行時間稱為算法的（A）。時間復雜度空間復雜度處理器復雜度D.通信復雜度.下面哪個問題不是典型的NP完全問題(D)。m-著色問題旅行商問題哈密爾頓回路問題排序問題.順序查找的時間復雜度為(A)。O(n)O(logn)O(n2)D.O(nlogn).折半查找的時間復雜度為(B)。O(n)O(logn)O(n2)D.O(nlogn).算法的復雜性有時間復雜性和(C)復雜性之分。處理器復雜性通信復雜性空間復雜性存儲復雜性.算法的復雜性有空間復雜性和(C)復雜性之分。處理器復雜性通信復雜性時間復雜性存儲復雜性.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質。其中算法的“確定性”是指組成算法的每條(B)是清晰的，無歧義的。程序指令語句語句塊.(C)的基本運算是把兩個或多個有序序列合并成一個有序序列?？焖倥判蛳柵判蚝喜⑴判駾.堆排序.解決0/1背包問題可以使用動態規劃，回溯法，分支限界法。其中不需要排序的是（A）。動態規劃回溯法分支限界法以上3種方法都需要排序.解決0/1背包問題時需要排序的方法是回溯法和（B）。動態規劃分支限界法貪心法線性規劃.下面哪項是動態規劃算法基本要素之一（D）。人、定義最優解8、構造最優解^算出最優解口、最優子結構.快速排序算法是基于（A）的一種排序算法。分治策略貪心回溯動態規劃.（C）是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。A、重疊子問題8、最優子結構5貪心選擇性質□、定義最優解.如果無向連通圖6中不包含任何關節點，則稱該圖6為（A）。雙連通圖單連通圖強連通圖弱連通圖138.使用剪枝函數的深度優先生成狀態空間樹中結點的求解方法稱為（D）。動態規劃分支限界法貪心法回溯法.回溯法的算法框架按照問題的解空間一般分為子集樹算法框架和（A）算法框架。人排列樹8二叉樹C.B樹D.B+樹.下列算法常以自頂向下的方式求解最優解的是（C）。分治法動態規劃法貪心法回溯法.哈夫曼編碼可利用（C）算法實現。人、分治策略B、動態規劃法5貪心法D.回溯法.在對問題的解空間樹進行搜索的方法中一個活結點有多次機會成為活結點的是（A）。回溯法分支限界法回溯法和分支限界法動態規劃143、始皇吞并六國使用的遠交近攻逐個擊破的連橫策略采用了以下哪種算法思想（B）。A、遞歸8、分治5迭代D、模擬。144、FIFO是（A）的一搜索方式。人、分支界限法B、動態規劃法5貪心法D.回溯法145、投點法是（B）的一種。人、分支界限算法8、概率算法C、貪心算法口、回溯算法146、若線性規劃問題存在最優解它一定不在（C）。人可行域的某個頂點上8可行域的某條邊上C可行域部口以上都不對147、在一般輸入數據的程序里輸入多多少少會影響到算法的計算復雜度，為了消除這種影響可用（B）對輸入進行預處理。人、蒙特卡羅算法8、拉斯維加斯算法5舍伍德算法口、數值概率算法148、若1是一個NP完全問題L經過多項式時間變換后得到問題l則1是（A）。A、P類問題B、NP難問題C、NP完全問題D、P類語言.不斷回頭尋找目標的方法稱為（C）。動態規劃貪心法回溯法概率算法.拉斯維加斯算法找到的解一定是（B）。不確定的正確的C.不正確的口.局部最優的.記號在算法復雜性的表示法中表示（C）。上界下界緊致界以上說法都不對.一個無向連通圖不是雙向連通圖的充要條件是圖中存在（B）?；芈逢P節點最大團最小團153.一個算法是對特定問題求解的一種描述，它是(A)。指令的有限序列程序的有限序列語句的有限序列代碼的有限序列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];}它的漸近時間復雜度為(B)。O(n2)O(n3)O(n)O(n4).二分搜索過程的算法行為可以用一棵(B)來描述。二叉排序樹二叉判定樹子集樹排列樹.用貪心法求解背包問題時，為了使收益最大化要選擇(A)的物品裝入背包。單位重量收益最大收益最大重量最大重量最小.一個遞歸算法必須包括(B)。遞歸部分終止條件和遞歸部分迭代部分終止條件和迭代部分.有六個元素6,5,4,3,2,1的順序進棧，則下列哪一個不是合法的出棧序列(C)。543612453126346521234156.棧和隊列的共同點是（C）。都是先進先出都是先進后出只允許在端點處插入和刪除元素沒有共同點160.若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）。91115不確定.排序趟數與原始序列有關的排序方法是（C）排序法。A.插入B.選擇C.冒泡D.快速.如果給定權值總數有口個，則其哈夫曼樹的結點總數為（D）。不確定2n2n+12n-13.一個棧的輸入序列為123…口，若輸出序列的第一個元素是"則輸出第》（1<i<n）個元素是（B）。不確定n-i+1in-i164.下列序列中，（C）是執行第一趟快速排序后所得的序列。A.[68，11，18，69][23，93，73][68，11，69，23][18，93，73][93，73][68，11，69，23，18][68，11，69，23，18][93，73]165.下列哪個問題不能用貪心法求解？（C）人哈夫曼編碼問題8.單源最短路徑問題C.0-1背包問題口.最小生成樹問題.下列隨機算法一定有解但解不一定正確的是（C）。SherwoodLasVegasMonteCarlo口.三者都不是.在算法的三種情況下的復雜性中，可操作性最好且最有實際價值的是（B）情況下的時間復雜度。最好最壞平均以上都不正確.快速排序算法的性能取決于（A）。劃分的對稱性數據的原始序列隨機選擇策略以上都不正確.回溯法在問題的解空間樹中，按（B）策略，從根節點出發搜索解空間樹。廣度優先深度優先隨機以上說法都不對.大符號用來描述增長率的下限，這個下限的階越（A），結果就越有價值。高低和具體問題有關以上都不正確.設計動態規劃算法的步驟為：（1）找出最優解的性質，并刻畫其結構特征。（2）（B）。（3）以自底向上的方式計算出最優值。（4）計算最優值得到的信息，構造最優解。非遞歸的定義最優值遞歸的定義最優值迭代的定義最優值遞推的定義最優值172.設計動態規劃算法的步驟為：(1)找出最優解的性質，并刻畫其結構特征。(2)遞歸的定義最優值。(3)(A)。(4)計算最優值得到的信息，構造最優解。以自底向上的方式計算出最優值以自頂向下的方式計算出最優值迭代的方式計算出最優值遞推的方式算出最優值.最優二叉搜索樹即是(A)的二叉搜索樹。最小平均查找時間最小最壞查找時間最小平均存儲空間最小最壞存儲空間.當(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為(C)。242220D.15.9n2+10n的漸近表達式是(A)。O(n2)O(n3)O(n)O(n4).下面程序段的時間復雜度是(C)。for(i=0;i<n;i++)for(j=0;j<n;j++)O(n)O(n3)O(n2)O(n4)177.快速排序算法是基于分治策略的一個算法，其基本思想是，對于輸入的子數組a[p:r],按以下三個步驟進行排序：(A)。分解、遞歸求解、合并遞歸求解、分解、合并合并、遞歸求解、分解分解、合并、遞歸求解178.最優裝載問題可用貪心算法求解，采用(C)先裝的貪心選擇策略，可產生最優裝載問題的最優解。重量最重者單位重量收益大重量最輕者收益最大.寫出下列爐)的漸進性態，若^)=勺，C0為常數，則f(n)=(A)。O(1)O(n)O(n2)O(n3).寫出下列改口)的漸進性態，若f(n)=3n+2,則f(n)=(B)。O(1)O(n)O(n2)O(n3).寫出下列改口)的漸進性態，若f(n)=6*2n+n,則f(n)=(B)。O(1)O(2n)O(n2)O(n3).若一個算法的時間復雜度用?、吮硎?，其中口的含義是(A)。問題規模語句條數循環層數函數數量.背包問題可獲得最優解的輸入是按(B)。重量密度排序價值密度排序單位重量收益大小排序重量大小排序4.合并排序法的基本思想是：將待排序元素分成大小大致相同的(C)個子集合，分別對每個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。4325.二分搜索算法的基本思想是將n個元素分成個數大致相同的兩半，取2巾/2］與x進行比較：如果（C ），則只要在數組a的右半部繼續搜索X。x<a[n/2]X=a[n/2]x>a[n/2]x>=a[n/2].當問題規模n趨向于無窮大時，（B）的數量級（階）稱為算法的漸進時間復雜度?？臻g復雜度時間復雜度冗余度迭代次數.通常用來表示時間算法的有以下六種多項式：0(1),0(m),O(log2n),O(n*O(n),O(nlog2n),按從小到大的順序排列是(A)。O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)22O(1)<O(n)<O(logn)<O(nlogn)<O(n2)<O(n3)22O(1)<O(log2n)<O(n)<O(n2)<O(nlog2n)<O(n3)O(1)<O(n)<O(log2n)<O(nlog2n)<O(n2)<O(n3).貪心方法是一種求(C)的方法。最小解最大解最優解局部最優解.0干%））=0（即））其中P是一個（A）。正的常數負的常數不確定以上說法都不對.當問題規模n趨向于無