西安郵電大學算法考試

1、第 1 章 算法概述（1）算法的性質包括輸入、輸出、確定性 、有限性。（2）算法復雜性 ：算法所運行所需要的計算機資源的量，所需資源多，算法的復雜性高；反之則復雜性低。 時間復雜性 ：需要時間資源的量(指令數) 空間復雜性：需要空間資源的量(存儲器的大小)（3） 計算題第 2 章 遞歸與分治策略（1）分治法主要思想：將一個規(guī)模為n 的問題分解為k個規(guī)模較小子問題，這些子問題互相獨立且與原問題相同，遞歸解決這些子問題，然后將各子問題的解合并得到原問題解。（2）使用分治算法找一組數的最大最小數。采用如下設計思想：將數據集 S 均分為 S1 和 S2；求解 S1 和 S2 中的最大和最小值；最終的最

2、大和最小值可以計算得到：min( S1, S2 ), max( S1, S2 )；采用同樣的處理方法遞歸處理 S1 和 S2。可以得到該算法復雜性的遞推公式如下根據遞推公式推導出該復雜性表達式:3） 分治法所能解決的問題具有的特征.（1）該問題規(guī)?？s小到一定的程度就可以容易地解決；因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。（2）該問題可分解為若干個規(guī)模較小相同問題，即該問題具有“最優(yōu)子結構性質”。這條特征是應用分治法前提，它也是大多數問題可滿足的，反映了遞歸思想的應用。（3）利用該問題分解出的子問題的解可以合并為該問題的解。能否利用分治法完全取決于問題是否

3、具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。4）數組 A 含有 9 個元素，這些元素恰好是第 2 至第 10 個 Fibonacci 數，寫出在數組 A 中查找 x = 17 的二分查找過程（寫出過程即可，不需要寫代碼）。（5）下面給出了非遞歸形式的二分搜索方法代碼，請補充下劃線處的代碼。template < class T

4、ype > int BinarySearch( Type a, const Type& x, int n ) / 在 a 0 <= a 1 <= . <= a n 1 中搜索 x，找到 x 時返回其在數組中的位置，否則返回 -1 int left = 0; int right = n - 1; while ( left <= right ) int middle = ( left + right ) / 2; if ( x = a middle ) return middle; if ( x > a middle ) left = middle +

5、1; else right = middle - 1; return -1; / 未找到 x （6）判斷下列遞歸算法（計算n?。┦欠裾_，如果不正確，請說明原因，并改正。int factoral(int i) if ( n > 0 ) return( n * factoral( n - 1 ) ); 【分析】不正確，因為遞歸函數沒有邊界值的判斷，無法得出正確的值。另外入口參數與下面的使用不一致。修改如下：int factoral( int n ) if ( n = = 0 ) return 1; return( n * factoral( n 1 ) ); 第 3 章 動態(tài)規(guī)劃（1）備忘

6、錄法是那種算法的變形（ B ）。A、分治算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯法（2）分治法與動態(tài)規(guī)劃算法的相同點和不同點是什么？（3）利用動態(tài)規(guī)劃法設計如下的矩陣連乘最小次數問題，寫出動態(tài)規(guī)劃法求解過程。A1：40×25 A2：25×25 A3：25×15解：m00=m11 =m22 =m33=0 r=2 i=1 j=2 m12=40*25*10=10000 i=2 j=3 m23= 25*10*15=3750 r=3 i=1 j=3 m13= m11+ m23+ 40*25*15=18750 k=2 t= m12+ m33+ 40*10*15=1600

7、0 m13=t=16000（4）具有最優(yōu)子結構的算法有（ D ）。A概率算法 B回溯法 C分支限界法 D動態(tài)規(guī)劃法（5）證明題。（6） 計算題（7）有一個箱子容量為 V（正整數），同時有 n 個物品，每個物品有一個體積（正整數）。要求 n 個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。編寫程序實現，自定義輸入和輸出?！咎崾尽渴褂枚S數組 f i j , 表示前 i 個物品裝入容量為 j 的箱子能獲得的最大體積，則狀態(tài)轉移方程：f i j = max( f i - 1 j , f i -1 j - a i + a i );（8）已知字符串 A 的值是 sot，字符串 B 的值是 stop

8、，將字符串 A 轉換為字符串 B 的編輯距離值為（ ）。A1 B2 C3 D4【分析】根據“編輯距離”的定義，可知答案為 B。sot 通過一個“增加”操作變?yōu)?stot，然后通過一個“編輯”操作就可以變?yōu)?stop。注意答案 C 是錯誤的。（9）有一輛貨車，貨車有載重為 D，有 n 件貨物，每個貨物有重量 wi，價值 pi。問怎么裝能夠使裝上貨車的物品的總價值最大（使用動態(tài)規(guī)劃算法）【分析】“0-1”背包問題。第 4 章 貪心算法（1） 簡述貪心法的基本思想：設置頂點集合 S 并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合 S 當且僅當從源到該頂點的最短路徑長度已知。初始時，S 中僅含有源

9、。設 u 是 G 的某一個頂點，把從源到 u 且中間只經過 S 中頂點的路稱為從源到 u 的特殊路徑，并用數組 dist 記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra 算法每次從 V-S（頂點集合 V“減去”集合 S） 中取出具有最短特殊路長度的頂點 u，將 u 添加到 S 中，同時對數組dist 作必要的修改。一旦 S 包含了所有 V 中頂點，dist 就記錄了從源到所有其它頂點之間的最短路徑長度。貪心算法的兩個重要性質：貪心選擇性質和最優(yōu)子結構性質貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是兩類算法的一個共同點。 （1）對于具有最優(yōu)子結構的問題應該選用貪心算法？（

10、2）是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解 ?（2）證明上述問題具有“貪心選擇性質”和“最優(yōu)子結構性質”。（3）設 7 個獨立作業(yè) 1，2，3，4，5，6，7 由 3 臺相同機器 M1，M2，M3 加工處理。各作業(yè)所需的處理時間分別 2，14，4，16，6，5，3 。任何作業(yè)可以在任何一臺機器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。按貪心算法產生作業(yè)調度，所需加工時間為多少？（4）某體育館有一籃球球場出租，共有 10 位客戶申請租用。每個客戶申請租用的時間單元如下表所示，其中 i 表示客戶編號，s(i) 表示開始租用時刻，f(i) 表示結束租用時刻。同一

11、時刻該籃球球場只能租借給一位客戶。請使用貪心算法設計一個租用安排方案，在這 10 位客戶里面，使得體育館能盡可能滿足多位客戶的需求。并計算出針對上表的 10 個客戶申請，最多可以安排幾位客戶申請?！痉治觥窟@是一個活動安排問題。將這 10 位客戶的申請按照結束時間 f(i)遞增排序，如下表：（1）選擇申請 1（1,4）。（2）依次檢查后續(xù)客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請 4（5,7）、申請 8（8,11）、申請 10（11,13）。（3）最后可以滿足：申請 1（1,4）、申請 4（5,7）、申請 8（8,11）、申請 10（11,13）共4 個客戶

12、申請。這是可以滿足的最大客戶人數。（5）下列哪個問題不能用貪心法求解？（ ）A最優(yōu)裝載問題 B活動安排問題 C0-1背包問題 D多機調度問題【分析】答案為 C。（6）設有 n 個程序 1,2,.,n 要存放在長度為 L 的磁帶上，程序 i 存放在磁帶上的長度為 li, 1<=i<=n。確定這 n 個程序在磁帶上的一個存儲方案，使得能夠在磁帶上存儲盡可能多的程序。【分析】程序存儲問題，類似“最優(yōu)裝載”問題。先對程序長度進行排序，然后用循環(huán)累加排序后的程序長度，并計數程序個數。解題時寫出解題思想和基本的算法（代碼）框架即可。第 5 章 回溯法（1）回溯法解旅行商問題時的解空間樹是（ B

13、 ）。A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹（2）下面（剪枝函數）是回溯法中避免無效搜索采取的策略（3）用回溯法搜索排列樹的算法是什么？void Backtrack ( int t ) if ( t > n ) output( x ); else for ( int i = t; i <= n; i+ ) swap( x t , x i ); if ( Constraint( t ) && Bound( t ) ) Backtrack( t + 1 ); swap( x t , x i ); 在調用Backtrack(1)執(zhí)行回溯搜索之前，先

14、將變量數組x初始化為單位排列(1,2,n)（4）對批處理作業(yè)調度問題：作業(yè)需要機器處理時間的表如下，如果調度方案為：1，2，3，計算完成時間和。作業(yè)調度方案：1，2，3（必須考慮機器的空閑時間）：作業(yè) 1 在機器 1 上完成的時間為 2，在機器 2 上完成的時間為 3（2 + 1）作業(yè) 2 在機器 1 上完成的時間為 5（2 + 3），在機器 2 上完成的時間為 6（5 + 1）作業(yè) 3 在機器 1 上完成的時間為 7（2 + 3 + 2），在機器 2 上完成的時間為 10（7 + 3）完成時間和：3 + 6 + 10 = 19（5）寫出用回溯法求解如下 0-1 背包 的求解過程（使用約束函數

15、和限界函數進行剪枝），并畫出狀態(tài)空間搜索樹：有 3 個物品，它們的重量和價值如下表所示，背包容量 C 60。（6）設有 n 件工作分配給 n 個人。將工作 i 分配給第 j 個人所需的費用為 cij。采用回溯法設計一個算法，為每一個人都分配 1 件不同的工作，并使總費用達到最小?！痉治觥扛鶕栴}描述，可得解題思路如下：由于每個人都必須分配到工作，可以建一個二維數組 c i j ，用以表示 i 號工人完成 j 號工作所需的費用。給定一個循環(huán)，從第 1 個工人開始循環(huán)分配工作，直到所有工人都分配到。為第 i 個工人分配工作時，再循環(huán)檢查每個工作是否已被分配，沒有則分配給 i 號工人，否則檢查下一個

16、工作?？梢杂靡粋€一維數組x j 來表示第j號工作是否被分配，未分配則x j = 0，否則x j = 1。利用回溯法在工人循環(huán)結束后回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配為止。這樣，一直回溯到第1個工人后，就能得到所有的可行解。在檢查工作分配時，其實就是判斷取得可行解時的二維數組的下標一都不相同，下標二同樣不相同。第 6 章 分支限界法（1）簡述回溯法和分支限界法的異同點。 分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。二者的不同之處在于：（1）回溯法的求解目標往往是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或

17、是在滿足約束條件的解中找出在某種意義下的最優(yōu)解；（2）回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索解空間樹。（2） 給定 0/1 背包問題，參數為：n = 3, w = 16, 15, 15 , p = 45, 25, 25 , c = 30。用隊列式分支限界法求解此問題。給出求解過程（包括在求解過程中隊列內容的變化情況）。（3）布線問題的解空間是圖.1:程序與算法的區(qū)別:算法是給人來讀的，直接給計算機是不能執(zhí)行的;程序可以不滿足算法的有限性2:簡述分治法的主要思想。將一個問題不斷分割成若干個小問題，然后通過對小問題的求解再生成大問題的解。

18、因此分治法可以分為兩個重要步驟：（1）自頂向下：將問題不斷分割成小的問題。（2）自底而上：將小問題解決來構建大問題的解。3：分治法能解決問題所具有的性質（1）該問題規(guī)?？s小到一定的程度就可以容易地解決；因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有“最優(yōu)子結構性質”。這條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用。（3）利用該問題分解出的子問題的解可以合并為該問題的解。4：動態(tài)規(guī)劃與分治法的相同點和不同點 1共同點：  將待求解的問題分

19、解成若干子問題，先求解子問題，然后再從這些子問題的解得到原問題的解。 2. 不同點： 1、適合于用動態(tài)規(guī)劃法求解的問題，分解得到的各子問題往往不是相互獨立的；而分治法中子問題相互獨立。 2、動態(tài)規(guī)劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高；而分治法中對于每次出現的子問題均求解，導致同樣的子問題被反復求解，故產生指數增長的時間復雜度，效率較低 5：簡述貪心算法的基本思想所謂貪心算法指的是為了解決在不回溯的前提之下，找出整體最優(yōu)或者接近最優(yōu)解的這樣一種類型的問題而設計出來的算法。貪心算法的基本思想是找出整體當中每個小的局部的最優(yōu)解，并且將所有的這些局部最優(yōu)解合起來形成整體上的一個最優(yōu)解。因此能夠使用貪心算法的問題必須滿足下面的兩個性質：1.整體的最優(yōu)解可以通過局部的最優(yōu)解來求出；2.一個整