程序算法設(shè)計與分析A答案

2009~2010學(xué)年第1學(xué)期《算法分析與設(shè)計》課程試卷（A）參考答案及評分標(biāo)準(zhǔn)開課二級學(xué)院：理學(xué)院，學(xué)生班級：06信算1，2，教師：一、名詞解釋：（每題5分，共20分）1、遞歸算法直接或間接地調(diào)用自身的算法稱為遞歸算法。使用遞歸技術(shù)往往使算法的描述簡捷且易于理解。(5分)2、二分搜索：二分搜索算法的基本思想是將n個排序好的元素分成個數(shù)大致相等的兩半，取與作比較，如果，則算法終止，如果，則在數(shù)組的左半部查找，否則在右半部查找。（5分）3、合并排序：合并排序算法是用分治策略實現(xiàn)對個元素的進行排序的算法，其基本思想是將待排序的元素分成兩個大小致相等的兩面?zhèn)€子集合，分別對兩面?zhèn)€子集合進行排序。最終將排好序的子集合合并成要求的排序好的集合。（5分）4、分治法基本思想分治法的基本思想是將一個規(guī)模為的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立，分別對這些子問題求解，再把所得到的問題的解合并起來，從而得到整個問題的解的方法。（5分）二、簡答題：1、背包問題與0-1背包問題的比較答：0-1背包問題是給定n種物品和一個背包，物品的重量是，其價值為，背包的容量為，問如何選擇裝入背包的物品，使得背包中物品總價值最大。（3分）背包問題：與0-1背包問題不同的是裝入某一物品可以裝入其一部分。（5分）兩個問題差別不大，但解決問題的方法是不同的，背包問題可以用貪心算法來實現(xiàn)，而0-1背包問題不能用貪心法來實現(xiàn)，一般采用動態(tài)規(guī)劃的方法來實現(xiàn)。（10分）2、寫出動態(tài)規(guī)劃算法的基本思想、解題步驟及基本要素。答：動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。（4分）通常按以下步驟設(shè)計：找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。（8分）基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。（10分）3、寫出回溯法的基本思想和解題步驟。答：回溯法是從開始結(jié)點出發(fā)，以深度優(yōu)先的方式搜索整個解空間，這個開始結(jié)成為活結(jié)點，同時也成擴展結(jié)點，在當(dāng)前的擴展結(jié)點處，按深度優(yōu)先的方式，進行搜索，直到找到所要求的解，或是沒有活結(jié)點為止。(4分)通常分以下3個步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)；以深度優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。（10分）4、RAM指令中的操作數(shù)有哪幾種形式？寫出這幾種形式的名稱、符合及表示的意義。答：RAM指令中的操作數(shù)有3種形式：（1）=i（直接數(shù)型），操作數(shù)是整數(shù)i本身。（3分）(2)i（直接地址型），i是一非負(fù)整數(shù)，操作數(shù)是寄存器ri的內(nèi)容。（6分）(3)*i(間接地址型)，i為非負(fù)整數(shù)，若寄存器ri的內(nèi)容為整數(shù)j，則操作數(shù)為寄存器rj中的內(nèi)容。當(dāng)j為負(fù)整數(shù)時操作數(shù)無定義。（10分）三．設(shè)計與分析(每小題20分，共40分)1、用快速排序法對數(shù)組a[p:r]進行排列。寫出快速排序法的基本思想及算法描述。答：快速排序法的基本思想是對于輸入的子數(shù)組a[p:r]，按以下三個步驟進行排序。（1）分解：以a[p]為基準(zhǔn)元素將a[p:r]劃分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一個元素小于等于a[q]，而a[q+1:r]中任何一個元素大于等于a[q]。下標(biāo)q在劃分過程中確定。（5分）（2）遞歸求解：通過遞歸調(diào)用快速排序算法分別對a[p:q-1]和a[q+1:r]進行排序。（9分）（3）合并：由于對a[p:q-1]和a[q+1:r]的排序是就地進行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要執(zhí)行任何計算，a[p:r]就已排好序。（14分）算法描述：Template<classType>VoidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序QuickSort(a,q+1,r);//對右半段排序}}Template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];While(true){While(a[++i]<x&&i<r);While(a[--j]>x);If(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}（20分）2、Dijkstra算法（1）描述該算法的基本思想Dijkstra算法是解決單源最短路徑的一個貪心算法，其基本思想是，設(shè)置頂集合S并不斷的做貪心選擇來擴充這個集合。一個頂點屬于S當(dāng)且公當(dāng)從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一頂點，反從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用Dist記錄當(dāng)前每一個頂點所對應(yīng)的最短特殊路徑長度。（5分）（2）用圖表的形式表求出有向（圖1）從頂點1到其它頂點的最短路徑的Dijkstra算法的迭代過程。迭代suDist[2]Dist[3]Dis