西安郵電大學(xué)算法考試

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

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

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

4、ype > int BinarySearch( Type a, const Type& x, int n ) / 在 a 0 <= a 1 <= . <= a n 1 中搜索 x，找到 x 時(shí)返回其在數(shù)組中的位置，否則返回 -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）判斷下列遞歸算法（計(jì)算n！）是否正確，如果不正確，請(qǐng)說明原因，并改正。int factoral(int i) if ( n > 0 ) return( n * factoral( n - 1 ) ); 【分析】不正確，因?yàn)檫f歸函數(shù)沒有邊界值的判斷，無法得出正確的值。另外入口參數(shù)與下面的使用不一致。修改如下：int factoral( int n ) if ( n = = 0 ) return 1; return( n * factoral( n 1 ) ); 第 3 章 動(dòng)態(tài)規(guī)劃（1）備忘

6、錄法是那種算法的變形（ B ）。A、分治算法 B、動(dòng)態(tài)規(guī)劃算法 C、貪心算法 D、回溯法（2）分治法與動(dòng)態(tài)規(guī)劃算法的相同點(diǎn)和不同點(diǎn)是什么？（3）利用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)如下的矩陣連乘最小次數(shù)問題，寫出動(dòng)態(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)子結(jié)構(gòu)的算法有（ D ）。A概率算法 B回溯法 C分支限界法 D動(dòng)態(tài)規(guī)劃法（5）證明題。（6） 計(jì)算題（7）有一個(gè)箱子容量為 V（正整數(shù)），同時(shí)有 n 個(gè)物品，每個(gè)物品有一個(gè)體積（正整數(shù)）。要求 n 個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。編寫程序?qū)崿F(xiàn)，自定義輸入和輸出。【提示】使用二維數(shù)組 f i j , 表示前 i 個(gè)物品裝入容量為 j 的箱子能獲得的最大體積，則狀態(tài)轉(zhuǎn)移方程：f i j = max( f i - 1 j , f i -1 j - a i + a i );（8）已知字符串 A 的值是 sot，字符串 B 的值是 stop

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

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

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

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

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

13、 ）。A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹（2）下面（剪枝函數(shù)）是回溯法中避免無效搜索采取的策略（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 ); 在調(diào)用Backtrack(1)執(zhí)行回溯搜索之前，先

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

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

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

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

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

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