【正文】 方式搜索問題解的算法稱為 分支限界法 。 貪心選擇 質和 最優(yōu)子結構 性質 。 1使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標準：約束條件和目標函數(shù)的界， N 皇后問題和 0/1 背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數(shù)的界進行裁剪的是 0/1 背包問題 ，只使用約束條件進行裁剪的是 N 皇后問題 。 數(shù)值概率算法常用于 數(shù)值問題 的求解。 算法是指解決問題的 一種方法 或 一個過程 。 程序是 算法 用某種程序設計語言的具體實現(xiàn)。 A、重疊子問題 B、 最優(yōu)子結構性質 C、 貪心選擇性質 D、定義最優(yōu)解 53．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從 小到大排序，故算法的時間復雜度為 ( B ) 。 A、 O（ n2n） B、 O（ nlogn） C、 O（ 2n） D、 O（ n） 4廣度優(yōu)先是（ A ）的一搜索方式。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 44．貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是 （ B ）。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 3合并排序算法是利用（ A ）實現(xiàn)的算法。 A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷 3下列隨機算法中運行時有時候成功有時候失敗的是（ C ） A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法 34． 實現(xiàn)合并排序利用的算法 是 （ A ）。 A、 最小堆 B、最大堆 C、棧 D、數(shù)組 2 Strassen 矩陣乘法是利用（ A ）實現(xiàn)的算法。 隨機數(shù)函數(shù) 2下面關于 NP問題說法正確的是（ B ） A NP 問題都是不可能解決的問題 B P類問題包含在 NP 類問題中 C NP 完全問題是 P 類問題的子集 D NP 類問題包含在 P類問題中 2蒙特卡羅算法是（ B ）的一種。 A、最小堆 B、最大堆 C、棧 D、數(shù)組 16．最長公共子序列算法利用的算 法是 （ B ）。 A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先 12 ．下 列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（ D ） 。 A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 衡量一個算法好壞的標準是（ C ）。 A、找出最優(yōu)解的性質 B、構造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解 最大效益優(yōu)先是（ A ）的一搜索方式。 一。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 在下列算法中有時找不到問題解的是（ B ）。 A 運行速度快 B 占用空間少 C 時間復雜度低 D 代碼短 以下不可以使用分治法求解的是（ D ）。 A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 17．實現(xiàn)棋盤覆蓋算法利用的算法是 （ A ）。 A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法 （ C ） A. 蒙特卡羅算法 B. 拉斯維加斯算法 24. （ D ）是貪心算法與動態(tài)規(guī)劃算法的共同點。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 2使用分治法求解不需要滿足的條件是（ A ）。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 35． 下列是動態(tài)規(guī)劃算法基本要素的是（ D ） 。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 3在下列算法中得到 的解未必正確的是（ B ）。 A、最優(yōu)子結構 B、 貪心選擇性質 C、 構造 最優(yōu)解 D、定義最優(yōu)解 45. 實現(xiàn)最大子段和利用的算法是 （ B ）。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 4舍伍德算法是（ B ）的一種。 A、 O（ n2n） B、 O（ nlogn） C、 O（ 2n） D、 O（ n） 54. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 ( D ) 。 算法的 “ 確定性 ” 指的是組成算法的每條 指令 是清晰的，無歧義的。 從分治法的一般設計模式可以看出，用它設計出的程序一般是 遞歸算法 。 1計算一個算法時間復雜度通常可以計算 循環(huán)次數(shù) 、 基本操作的頻率 或計算步。 1 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。 2舍伍德算法總能求得問題的 一個解 。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 規(guī)模 有關。 三、 算法填空 法 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w)。i++) x[i]=0。i++) { if (w[i]c) break。 } : 動態(tài)規(guī)劃算法 int MaxSum(int n, int a[]) { int sum=0, b=0； //sum 存儲當前最大的 b[j], b 存儲 b[j] for(int j=1； j=n； j++) { if (b0) b+= a[j] ； else b=a[i]。 //對左半段排序 QuickSort (a,q+1,r)。 coutendl。 perm(list,k+1。 據(jù)此容易設計出二分搜索算法： templateclass Type int BinarySearch(Type a[], const Typeamp。 else l = m+1。 Mergesort(a, i+1, right)。 y=( 1 )。 } 四 、問答題 ： 問題分析 數(shù)學模型建立 算法設計與選擇 算法指標 算法分析算法實現(xiàn) 程序調試 結果整理文檔編制 2. 算法定義： 算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理過程 操作 控制結構 數(shù)據(jù)結構 4. 算法具有以下 5 個屬性 ： 有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。 輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。一般這兩者與問題的規(guī)模有關。 2)、建立迭代關系式。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題。 是： 將一個規(guī)模為 n 的問題分解為 k 個規(guī)模較小的子問題，這些子問 題互相獨立且與原問題相同。 11. 動態(tài)規(guī)劃的基本思想 前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉移方程的動態(tài)規(guī)劃稱為 標準動態(tài)規(guī)劃 ，這種標準動態(tài)規(guī)劃是在研 究多階段決策問題時推導出來的，具有嚴格的數(shù)學形式，適合用于理論上的分析。 由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。 解決上述問題的辦法是利用動態(tài)規(guī)劃。 因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。 （ 2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關系來確定決策。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值 ，但是一般將其改為遞推計算。 （ 4）根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。 總結： 動態(tài)規(guī)劃實際上就是最優(yōu)化的問題，是指將原問題的大實例等價于同一最優(yōu)化問題的較小實例，自底向上的求解最小實例，并將所求解存放起來，存放的結果就是為了準備數(shù)據(jù)。而用分治法求解的問 題，經(jīng)分解得到的子問題往往是互相獨立的。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結構，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。每個活節(jié)點有且僅有一次機會變成 E節(jié)點。 有兩種常用的方法可用來選擇下一個 E節(jié)點 （雖然也可能存在其他的方法）： 1) 先進先出（ F I F O） 即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活 節(jié)點表的性質與 隊列相同。 17. 分治法所能解決的問題一般具有的幾個特征是 ： （ 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （ 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質 。 （ 2）優(yōu)先隊列式分支限界法： 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。 當所給的問題是確定 n 個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。為了有效地選擇下一擴展結點，加速搜索的進程，在每一個活結點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一