西安郵電大學算法考試

..第1章算法概述〔1算法的性質(zhì)包括輸入、輸出、確定性、有限性?！?算法復雜性：算法所運行所需要的計算機資源的量,所需資源多,算法的復雜性高；反之則復雜性低。時間復雜性：需要時間資源的量<指令數(shù)>空間復雜性：需要空間資源的量<存儲器的大小>計算題第2章遞歸與分治策略〔1分治法主要思想：將一個規(guī)模為n的問題分解為k個規(guī)模較小子問題,這些子問題互相獨立且與原問題相同,遞歸解決這些子問題,然后將各子問題的解合并得到原問題解?！?使用分治算法找一組數(shù)的最大最小數(shù)。采用如下設計思想：將數(shù)據(jù)集S均分為S1和S2；求解S1和S2中的最大和最小值；最終的最大和最小值可以計算得到：min<S1,S2>,max<S1,S2>；采用同樣的處理方法遞歸處理S1和S2?？梢缘玫皆撍惴◤碗s性的遞推公式如下根據(jù)遞推公式推導出該復雜性表達式:分治法所能解決的問題具有的特征.〔1該問題規(guī)?？s小到一定的程度就可以容易地解決；因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加,因此大部分問題滿足這個特征。〔2該問題可分解為若干個規(guī)模較小相同問題,即該問題具有"最優(yōu)子結(jié)構(gòu)性質(zhì)"。這條特征是應用分治法前提,它也是大多數(shù)問題可滿足的,反映了遞歸思想的應用?！?利用該問題分解出的子問題的解可以合并為該問題的解。能否利用分治法完全取決于問題是否具有這條特征,如果具備了前兩條特征,而不具備第三條特征,則可以考慮貪心算法或動態(tài)規(guī)劃?！?該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子問題。這條特征涉及到分治法的效率,如果各子問題是不獨立的,則分治法要做許多不必要的工作,重復地解公共的子問題,此時雖然也可用分治法,但一般用動態(tài)規(guī)劃較好。4數(shù)組A含有9個元素,這些元素恰好是第2至第10個Fibonacci數(shù),寫出在數(shù)組A中查找x=17的二分查找過程〔寫出過程即可,不需要寫代碼?！?下面給出了非遞歸形式的二分搜索方法代碼,請補充下劃線處的代碼。template<classType>intBinarySearch<Typea[],constType&x,intn>{//在a[0]<=a[1]<=...<=a[n–1]中搜索x,找到x時返回其在數(shù)組中的位置,否則返回-1intleft=0;intright=n-1;while<left<=right>{intmiddle=<left+right>/2;if<x==a[middle]>returnmiddle;if<x>a[middle]>left=middle+1;elseright=middle-1;}return-1;//未找到x}〔6判斷下列遞歸算法〔計算n！是否正確,如果不正確,請說明原因,并改正。intfactoral<inti>{if<n>0>return<n*factoral<n-1>>;}[分析]不正確,因為遞歸函數(shù)沒有邊界值的判斷,無法得出正確的值。另外入口參數(shù)與下面的使用不一致。修改如下：intfactoral<intn>{if<n==0>return1;return<n*factoral<n–1>>;}第3章動態(tài)規(guī)劃〔1備忘錄法是那種算法的變形〔B。A、分治算法B、動態(tài)規(guī)劃算法C、貪心算法D、回溯法〔2分治法與動態(tài)規(guī)劃算法的相同點和不同點是什么？〔3利用動態(tài)規(guī)劃法設計如下的矩陣連乘最小次數(shù)問題,寫出動態(tài)規(guī)劃法求解過程。A1：40×25A2：25×25A3：25×15解：m[0][0]=m[1][1]=m[2][2]=m[3][3]=0r=2i=1j=2m[1][2]=40*25*10=10000i=2j=3m[2][3]=25*10*15=3750r=3i=1j=3m[1][3]=m[1][1]+m[2][3]+40*25*15=18750k=2t=m[1][2]+m[3][3]+40*10*15=16000m[1][3]=t=16000〔4具有最優(yōu)子結(jié)構(gòu)的算法有〔D。A．概率算法B．回溯法C．分支限界法D．動態(tài)規(guī)劃法〔5證明題。計算題〔7有一個箱子容量為V〔正整數(shù),同時有n個物品,每個物品有一個體積〔正整數(shù)。要求n個物品中,任取若干個裝入箱內(nèi),使箱子的剩余空間為最小。編寫程序?qū)崿F(xiàn),自定義輸入和輸出。[提示]使用二維數(shù)組f[i][j],表示前i個物品裝入容量為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的編輯距離值為〔。A．1B．2C．3D．4[分析]根據(jù)"編輯距離"的定義,可知答案為B。sot通過一個"增加"操作變?yōu)閟tot,然后通過一個"編輯"操作就可以變?yōu)閟top。注意答案C是錯誤的?！?有一輛貨車,貨車有載重為D,有n件貨物,每個貨物有重量wi,價值pi。問怎么裝能夠使裝上貨車的物品的總價值最大〔使用動態(tài)規(guī)劃算法[分析]"0-1"背包問題。第4章貪心算法簡述貪心法的基本思想：設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時,S中僅含有源。設u是G的某一個頂點,把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑,并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S〔頂點集合V"減去"集合S中取出具有最短特殊路長度的頂點u,將u添加到S中,同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點,dist就記錄了從源到所有其它頂點之間的最短路徑長度。貪心算法的兩個重要性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì),這是兩類算法的一個共同點?！?對于具有最優(yōu)子結(jié)構(gòu)的問題應該選用貪心算法？〔2是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?〔2證明上述問題具有"貪心選擇性質(zhì)"和"最優(yōu)子結(jié)構(gòu)性質(zhì)"?！?設7個獨立作業(yè){1,2,3,4,5,6,7}由3臺相同機器M1,M2,M3加工處理。各作業(yè)所需的處理時間分別{2,14,4,16,6,5,3}。任何作業(yè)可以在任何一臺機器上加工處理,但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。按貪心算法產(chǎn)生作業(yè)調(diào)度,所需加工時間為多少？〔4某體育館有一籃球球場出租,共有10位客戶申請租用。每個客戶申請租用的時間單元如下表所示,其中i表示客戶編號,s<i>表示開始租用時刻,f<i>表示結(jié)束租用時刻。同一時刻該籃球球場只能租借給一位客戶。請使用貪心算法設計一個租用安排方案,在這10位客戶里面,使得體育館能盡可能滿足多位客戶的需求。并計算出針對上表的10個客戶申請,最多可以安排幾位客戶申請。[分析]這是一個活動安排問題。將這10位客戶的申請按照結(jié)束時間f<i>遞增排序,如下表：〔1選擇申請1〔1,4?！?依次檢查后續(xù)客戶申請,只要與已選擇的申請相容不沖突,則選擇該申請。直到所有申請檢查完畢。申請4〔5,7、申請8〔8,11、申請10〔11,13?！?最后可以滿足：申請1〔1,4、申請4〔5,7、申請8〔8,11、申請10〔11,13共4個客戶申請。這是可以滿足的最大客戶人數(shù)?！?下列哪個問題不能用貪心法求解？〔A．最優(yōu)裝載問題B．活動安排問題C．0-1背包問題D．多機調(diào)度問題[分析]答案為C?！?設有n個程序{1,2,...,n}要存放在長度為L的磁帶上,程序i存放在磁帶上的長度為li,1<=i<=n。確定這n個程序在磁帶上的一個存儲方案,使得能夠在磁帶上存儲盡可能多的程序。[分析]程序存儲問題,類似"最優(yōu)裝載"問題。先對程序長度進行排序,然后用循環(huán)累加排序后的程序長度,并計數(shù)程序個數(shù)。解題時寫出解題思想和基本的算法〔代碼框架即可。第5章回溯法〔1回溯法解旅行商問題時的解空間樹是〔B。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹〔2下面〔剪枝函數(shù)是回溯法中避免無效搜索采取的策略〔3用回溯法搜索排列樹的算法是什么？voidBacktrack<intt>{if<t>n>output<x>;{elsefor<inti=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對批處理作業(yè)調(diào)度問題：作業(yè)需要機器處理時間的表如下,如果調(diào)度方案為：1,2,3,計算完成時間和。作業(yè)調(diào)度方案：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背包的求解過程〔使用約束函數(shù)和限界函數(shù)進行剪枝,并畫出狀態(tài)空間搜索樹：有3個物品,它們的重量和價值如下表所示,背包容量C＝60?！?設有n件工作分配給n個人。將工作i分配給第j個人所需的費用為cij。采用回溯法設計一個算法,為每一個人都分配1件不同的工作,并使總費用達到最小。[分析]根據(jù)問題描述,可得解題思路如下：由于每個人都必須分配到工作,可以建一個二維數(shù)組c[i][j],用以表示i號工人完成j號工作所需的費用。給定一個循環(huán),從第1個工人開始循環(huán)分配工作,直到所有工人都分配到。為第i個工人分配工作時,再循環(huán)檢查每個工作是否已被分配,沒有則分配給i號工人,否則檢查下一個工作。可以用一個一維數(shù)組x[j]來表示第j號工作是否被分配,未分配則x[j]=0,否則x[j]=1。利用回溯法在工人循環(huán)結(jié)束后回到上一工人,取消此次分配的工作,而去分配下一工作直到可以分配為止。這樣,一直回溯到第1個工人后,就能得到所有的可行解。在檢查工作分配時,其實就是判斷取得可行解時的二維數(shù)組的下標一都不相同,下標二同樣不相同。第6章分支限界法〔1簡述回溯法和分支限界法的異同點。分支限界法類似于回溯法,也是在問題的解空間上搜索問題解的算法。二者的不同之處在于：〔1回溯法的求解目標往往是找出解空間樹中滿足約束條件的所有解,而分支限界法的求解目標則是找出滿足約束條件的一個解,或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解；〔2回溯法以深度優(yōu)先的方式搜索解空間樹,而分支限界法則以廣度優(yōu)先或以最小耗費〔最大效益優(yōu)先的方式搜索解空間樹。給定0/1背包問題,參數(shù)為：n=3,w=[16,15,15],p=[45,25,25],c=30。用隊列式分支限界法求解此問題。給出求解過程〔包括在求解過程中隊列內(nèi)容的變化情況?！?布線問題的解空間是圖.1:程序與算法的區(qū)別:

算法是給人來讀的,直接給計算機是不能執(zhí)行的;程序可以不滿足算法的有限性

2:簡述分治法的主要思想。

將一個問題不斷分割成若干個小問題,然后通過對小問題的求解再生成大問題的解。

因此分治法可以分為兩個重要步驟：

〔1自頂向下：將問題不斷分割成小的問題。

〔2自底而上：將小問題解決來構(gòu)建大問題的解。

3：分治法能解決問題所具有的性質(zhì)

〔1該問題規(guī)模縮小到一定的程度就可以容易地解決；因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加,因此大部分問題滿足這個特征。

〔2該問題可以分解為若干個規(guī)模較小的相同問題,即該問題具有"最優(yōu)子結(jié)構(gòu)性質(zhì)"。這條特征是應用分治法的前提,它也是大多數(shù)問題可以滿足的,此特征反映了遞歸思想的應用。

〔3利用該問題分解出的子問題的解可以合并為該問題的解。。

4：動態(tài)規(guī)劃與分治法的相同點和不同點

1．共同點：

將待求解的問題分解成若干子問題,先求解子問題,然后再從這些子問題的

解得到原問題的解。

2.

不同點：

○1、適合于用動態(tài)規(guī)劃法求解的問題,分解得到的各子問題往往不是相互獨立的；

而分治法中子問題相互獨立。

○2、動態(tài)規(guī)劃法用表保存已求解過的子問題的解,再次碰到同樣的子問題時不必

重新求解,而只需查詢答案,故可獲得多項式級時間復雜度,效率較高；而分治法中對于每次出現(xiàn)的子問題均求解,導致同樣的子問題被反復求解,故產(chǎn)生指數(shù)增長的時間復雜度,效率較低

5：簡述貪心算法的基本思想

所謂貪心算法指的是為了解決在不回溯的前提之下,找出整體最優(yōu)或者接近最優(yōu)解的這樣一種類型的問題而設計出來的算法。貪心算法的基本思想是找出整體當中每個小的局部的最優(yōu)解,并且將所有的這些局部最優(yōu)解合起來形成整體上的一個最優(yōu)解。因此能夠使用