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

第 1 章 算法概述（1）算法的性質(zhì)包括輸入、輸出、確定性 、有限性。（2）算法復(fù)雜性 ：算法所運(yùn)行所需要的計(jì)算機(jī)資源的量，所需資源多，算法的復(fù)雜性高；反之則復(fù)雜性低。 時(shí)間復(fù)雜性 ：需要時(shí)間資源的量(指令數(shù)) 空間復(fù)雜性：需要空間資源的量(存儲(chǔ)器的大小)（3） 計(jì)算題第 2 章 遞歸與分治策略（1）分治法主要思想：將一個(gè)規(guī)模為n 的問(wèn)題分解為k個(gè)規(guī)模較小子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同，遞歸解決這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題解。（2）使用分治算法找一組數(shù)的最大最小數(shù)。采用如下設(shè)計(jì)思想：將數(shù)據(jù)集 S 均分為 S1 和 S2；求解 S1 和 S2 中的最大和最小值；最終的最大和最小值可以計(jì)算得到：min( S1, S2 ), max( S1, S2 )；采用同樣的處理方法遞歸處理 S1 和 S2?？梢缘玫皆撍惴◤?fù)雜性的遞推公式如下根據(jù)遞推公式推導(dǎo)出該復(fù)雜性表達(dá)式:3） 分治法所能解決的問(wèn)題具有的特征.（1）該問(wèn)題規(guī)模縮小到一定的程度就可以容易地解決；因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。（2）該問(wèn)題可分解為若干個(gè)規(guī)模較小相同問(wèn)題，即該問(wèn)題具有“最優(yōu)子結(jié)構(gòu)性質(zhì)”。這條特征是應(yīng)用分治法前提，它也是大多數(shù)問(wèn)題可滿足的，反映了遞歸思想的應(yīng)用。（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。（4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。4）數(shù)組 A 含有 9 個(gè)元素，這些元素恰好是第 2 至第 10 個(gè) Fibonacci 數(shù)，寫(xiě)出在數(shù)組 A 中查找 x = 17 的二分查找過(guò)程（寫(xiě)出過(guò)程即可，不需要寫(xiě)代碼）。（5）下面給出了非遞歸形式的二分搜索方法代碼，請(qǐng)補(bǔ)充下劃線處的代碼。template 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 a middle ) left = middle + 1; else right = middle - 1; return -1; / 未找到 x （6）判斷下列遞歸算法（計(jì)算n?。┦欠裾_，如果不正確，請(qǐng)說(shuō)明原因，并改正。int factoral(int i) if ( n 0 ) return( n * factoral( n - 1 ) ); 【分析】不正確，因?yàn)檫f歸函數(shù)沒(méi)有邊界值的判斷，無(wú)法得出正確的值。另外入口參數(shù)與下面的使用不一致。修改如下：int factoral( int n ) if ( n = = 0 ) return 1; return( n * factoral( n 1 ) ); 第 3 章 動(dòng)態(tài)規(guī)劃（1）備忘錄法是那種算法的變形（ 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ù)問(wèn)題，寫(xiě)出動(dòng)態(tài)規(guī)劃法求解過(guò)程。A1：4025 A2：2525 A3：2515解：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=16000 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)，使箱子的剩余空間為最小。編寫(xiě)程序?qū)崿F(xiàn)，自定義輸入和輸出?！咎崾尽渴褂枚S數(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，將字符串 A 轉(zhuǎn)換為字符串 B 的編輯距離值為（ ）。A1 B2 C3 D4【分析】根據(jù)“編輯距離”的定義，可知答案為 B。sot 通過(guò)一個(gè)“增加”操作變?yōu)?stot，然后通過(guò)一個(gè)“編輯”操作就可以變?yōu)?stop。注意答案 C 是錯(cuò)誤的。（9）有一輛貨車(chē)，貨車(chē)有載重為 D，有 n 件貨物，每個(gè)貨物有重量 wi，價(jià)值 pi。問(wèn)怎么裝能夠使裝上貨車(chē)的物品的總價(jià)值最大（使用動(dòng)態(tài)規(guī)劃算法）【分析】“0-1”背包問(wèn)題。第 4 章 貪心算法（1） 簡(jiǎn)述貪心法的基本思想：設(shè)置頂點(diǎn)集合 S 并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合 S 當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S 中僅含有源。設(shè) u 是 G 的某一個(gè)頂點(diǎn)，把從源到 u 且中間只經(jīng)過(guò) S 中頂點(diǎn)的路稱(chēng)為從源到 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ī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類(lèi)算法的一個(gè)共同點(diǎn)。 （1）對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法？（2）是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解 ?（2）證明上述問(wèn)題具有“貪心選擇性質(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) 表示開(kāi)始租用時(shí)刻，f(i) 表示結(jié)束租用時(shí)刻。同一時(shí)刻該籃球球場(chǎng)只能租借給一位客戶。請(qǐng)使用貪心算法設(shè)計(jì)一個(gè)租用安排方案，在這 10 位客戶里面，使得體育館能盡可能滿足多位客戶的需求。并計(jì)算出針對(duì)上表的 10 個(gè)客戶申請(qǐng)，最多可以安排幾位客戶申請(qǐng)?！痉治觥窟@是一個(gè)活動(dòng)安排問(wèn)題。將這 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è)客戶申請(qǐng)。這是可以滿足的最大客戶人數(shù)。（5）下列哪個(gè)問(wèn)題不能用貪心法求解？（ ）A最優(yōu)裝載問(wèn)題 B活動(dòng)安排問(wèn)題 C0-1背包問(wèn)題 D多機(jī)調(diào)度問(wèn)題【分析】答案為 C。（6）設(shè)有 n 個(gè)程序 1,2,.,n 要存放在長(zhǎng)度為 L 的磁帶上，程序 i 存放在磁帶上的長(zhǎng)度為 li, 1=i 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í)行回溯搜索之前，先將變量數(shù)組x初始化為單位排列(1,2,n)（4）對(duì)批處理作業(yè)調(diào)度問(wèn)題：作業(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）寫(xiě)出用回溯法求解如下 0-1 背包 的求解過(guò)程（使用約束函數(shù)和限界函數(shù)進(jìn)行剪枝），并畫(huà)出狀態(tài)空間搜索樹(shù)：有 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ù)問(wèn)題描述，可得解題思路如下：由于每個(gè)人都必須分配到工作，可以建一個(gè)二維數(shù)組 c i j ，用以表示 i 號(hào)工人完成 j 號(hào)工作所需的費(fèi)用。給定一個(gè)循環(huán)，從第 1 個(gè)工人開(kāi)始循環(huán)分配工作，直到所有工人都分配到。為第 i 個(gè)工人分配工作時(shí)，再循環(huán)檢查每個(gè)工作是否已被分配，沒(méi)有則分配給 i 號(hào)工人，否則檢查下一個(gè)工作。可以用一個(gè)一維數(shù)組x j 來(lái)表示第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)。 分支限界法類(lèi)似于回溯法，也是在問(wèn)題的解空間上搜索問(wèn)題解的算法。二者的不同之處在于：（1）回溯法的求解目標(biāo)往往是找出解空間樹(shù)中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解；（2）回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索解空間樹(shù)。（2） 給定 0/1 背包問(wèn)題，參數(shù)為：n = 3, w = 16, 15, 15 , p = 45, 25, 25 , c = 30。用隊(duì)列式分支限界法求解此問(wèn)題。給出求解過(guò)程（包括在求解過(guò)程中隊(duì)列內(nèi)容的變化情況）。（3）布線問(wèn)題的解空間是圖.1:程序與算法的區(qū)別:算法是給人來(lái)讀的，直接給計(jì)算機(jī)是不能執(zhí)行的;程序可以不滿足算法的有限性2:簡(jiǎn)述分治法的主要思想。將一個(gè)問(wèn)題不斷分割成若干個(gè)小問(wèn)題，然后通過(guò)對(duì)小問(wèn)題的求解再生成大問(wèn)題的解。因此分治法可以分為兩個(gè)重要步驟：（1）自頂向下：將問(wèn)題不斷分割成小的問(wèn)題。（2）自底而上：將小問(wèn)題解決來(lái)構(gòu)建大問(wèn)題的解。3：分治法能解決問(wèn)題所具有的性質(zhì)（1）該問(wèn)題規(guī)?？s小到一定的程度就可以容易地解決；因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有“最優(yōu)子結(jié)構(gòu)性質(zhì)”。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用。（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。4：動(dòng)態(tài)規(guī)劃與分治法的相同點(diǎn)和不同點(diǎn)1共同點(diǎn)：將待求解的問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后再?gòu)倪@些子問(wèn)題的解得到原問(wèn)題的解。2.不同點(diǎn)：1、適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，分解得到的各子問(wèn)題往往不是相互獨(dú)立的；而分治法中子問(wèn)題相互獨(dú)立。2、動(dòng)態(tài)規(guī)劃法用表保存已求解過(guò)的子問(wèn)題的解，再次碰到同樣的子問(wèn)題時(shí)不必重新求解，而只需查詢答案，故可獲得多項(xiàng)式級(jí)時(shí)間復(fù)雜度，效率較高；而分治法中對(duì)于每次出現(xiàn)的子問(wèn)題均求解，導(dǎo)致同樣的子問(wèn)題被反復(fù)求解，故產(chǎn)生指數(shù)增長(zhǎng)的時(shí)間復(fù)雜度，效率較低5：簡(jiǎn)述貪心算法的基本思想所謂貪心算法指的是為了解決在不回溯的前提之下，找出整體最優(yōu)或者接近最優(yōu)解的這樣一種類(lèi)型的問(wèn)題而設(shè)計(jì)出來(lái)的算法。貪心算法的基本思想是找出整體當(dāng)中每個(gè)小的局部的最優(yōu)解，并且將所有的這些局部最優(yōu)解合起來(lái)形成整體上的一個(gè)最優(yōu)解。因此能夠使用貪心算法的問(wèn)題必須滿足下面的兩個(gè)性質(zhì)：1.整體的最優(yōu)解可以通過(guò)局部的最優(yōu)解來(lái)求出；2.一個(gè)整體能夠被分為多個(gè)局部，并且這些局部都能夠求出最優(yōu)解。使用貪心算法當(dāng)中的兩個(gè)典型問(wèn)題是活動(dòng)安排問(wèn)題和背包問(wèn)題。6：簡(jiǎn)述回溯法與分支限界打的異同相同點(diǎn)：二者都是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法。不同點(diǎn)：1.在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出T中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。2.回溯法與分支-限界法對(duì)解空間的搜索方式不同，回溯法通常采用嘗試優(yōu)先搜索，而分支限界法則通常采用廣度優(yōu)先搜索。3.對(duì)節(jié)點(diǎn)存儲(chǔ)的常用數(shù)據(jù)結(jié)構(gòu)以及節(jié)點(diǎn)存儲(chǔ)特性也各不相同，除