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

..第1章算法概述〔1算法的性質(zhì)包括輸入、輸出、確定性、有限性?！?算法復(fù)雜性：算法所運(yùn)行所需要的計(jì)算機(jī)資源的量,所需資源多,算法的復(fù)雜性高；反之則復(fù)雜性低。時(shí)間復(fù)雜性：需要時(shí)間資源的量<指令數(shù)>空間復(fù)雜性：需要空間資源的量<存儲(chǔ)器的大小>計(jì)算題第2章遞歸與分治策略〔1分治法主要思想：將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小子問(wèn)題,這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同,遞歸解決這些子問(wèn)題,然后將各子問(wèn)題的解合并得到原問(wèn)題解?！?使用分治算法找一組數(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á)式:分治法所能解決的問(wèn)題具有的特征.〔1該問(wèn)題規(guī)?？s小到一定的程度就可以容易地解決；因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加,因此大部分問(wèn)題滿足這個(gè)特征?！?該問(wèn)題可分解為若干個(gè)規(guī)模較小相同問(wèn)題,即該問(wèn)題具有"最優(yōu)子結(jié)構(gòu)性質(zhì)"。這條特征是應(yīng)用分治法前提,它也是大多數(shù)問(wèn)題可滿足的,反映了遞歸思想的應(yīng)用?！?利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。能否利用分治法完全取決于問(wèn)題是否具有這條特征,如果具備了前兩條特征,而不具備第三條特征,則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃?！?該問(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ù),寫出在數(shù)組A中查找x=17的二分查找過(guò)程〔寫出過(guò)程即可,不需要寫代碼?！?下面給出了非遞歸形式的二分搜索方法代碼,請(qǐng)補(bǔ)充下劃線處的代碼。template<classType>intBinarySearch<Typea[],constType&x,intn>{//在a[0]<=a[1]<=...<=a[n–1]中搜索x,找到x時(shí)返回其在數(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判斷下列遞歸算法〔計(jì)算n！是否正確,如果不正確,請(qǐng)說(shuō)明原因,并改正。intfactoral<inti>{if<n>0>return<n*factoral<n-1>>;}[分析]不正確,因?yàn)檫f歸函數(shù)沒(méi)有邊界值的判斷,無(wú)法得出正確的值。另外入口參數(shù)與下面的使用不一致。修改如下：intfactoral<intn>{if<n==0>return1;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)題,寫出動(dòng)態(tài)規(guī)劃法求解過(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．動(dòng)態(tài)規(guī)劃法〔5證明題。計(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,將字符串A轉(zhuǎn)換為字符串B的編輯距離值為〔。A．1B．2C．3D．4[分析]根據(jù)"編輯距離"的定義,可知答案為B。sot通過(guò)一個(gè)"增加"操作變?yōu)閟tot,然后通過(guò)一個(gè)"編輯"操作就可以變?yōu)閟top。注意答案C是錯(cuò)誤的?！?有一輛貨車,貨車有載重為D,有n件貨物,每個(gè)貨物有重量wi,價(jià)值pi。問(wèn)怎么裝能夠使裝上貨車的物品的總價(jià)值最大〔使用動(dòng)態(tài)規(guī)劃算法[分析]"0-1"背包問(wèn)題。第4章貪心算法簡(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)的路稱為從源到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ì),這是兩類算法的一個(gè)共同點(diǎn)?！?對(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ì)"?！?設(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?！?依次檢查后續(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)題C．0-1背包問(wèn)題D．多機(jī)調(diào)度問(wèn)題[分析]答案為C?！?設(shè)有n個(gè)程序{1,2,...,n}要存放在長(zhǎng)度為L(zhǎng)的磁帶上,程序i存放在磁帶上的長(zhǎng)度為li,1<=i<=n。確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案,使得能夠在磁帶上存儲(chǔ)盡可能多的程序。[分析]程序存儲(chǔ)問(wèn)題,類似"最優(yōu)裝載"問(wèn)題。先對(duì)程序長(zhǎng)度進(jìn)行排序,然后用循環(huán)累加排序后的程序長(zhǎng)度,并計(jì)數(shù)程序個(gè)數(shù)。解題時(shí)寫出解題思想和基本的算法〔代碼框架即可。第5章回溯法〔1回溯法解旅行商問(wèn)題時(shí)的解空間樹(shù)是〔B。A、子集樹(shù)B、排列樹(shù)C、深度優(yōu)先生成樹(shù)D、廣度優(yōu)先生成樹(shù)〔2下面〔剪枝函數(shù)是回溯法中避免無(wú)效搜索采取的策略〔3用回溯法搜索排列樹(shù)的算法是什么？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對(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寫出用回溯法求解如下0-1背包的求解過(guò)程〔使用約束函數(shù)和限界函數(shù)進(jìn)行剪枝,并畫出狀態(tài)空間搜索樹(shù)：有3個(gè)物品,它們的重量和價(jià)值如下表所示,背包容量C＝60?！?設(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)。分支限界法類似于回溯法,也是在問(wèn)題的解空間上搜索問(wèn)題解的算法。二者的不同之處在于：〔1回溯法的求解目標(biāo)往往是找出解空間樹(shù)中滿足約束條件的所有解,而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解,或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解；〔2回溯法以深度優(yōu)先的方式搜索解空間樹(shù),而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)〔最大效益優(yōu)先的方式搜索解空間樹(shù)。給定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)容的變化情況?！?布線問(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ī)模縮小到一定的程度就可以容易地解決；因?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)解的這樣一種類型的問(wèn)題而設(shè)計(jì)出來(lái)的算法。貪心算法的基本思想是找出整體當(dāng)中每個(gè)小的局部的最優(yōu)解,并且將所有的這些局部最優(yōu)解合起來(lái)形成整體上的一個(gè)最優(yōu)解。因此能夠使用