算法分析與設(shè)計(jì)A6卷答案

第=page3*2-15頁(yè)，共=sectionpages3*26頁(yè)第=page3*26頁(yè)，共=sectionpages3*26頁(yè)南陽(yáng)理工學(xué)院課程考試參考答案與評(píng)分標(biāo)準(zhǔn)考試課程：算法分析與設(shè)計(jì)學(xué)年學(xué)期：試卷類(lèi)型：考試時(shí)間：120分鐘一、單選題（每小題2分，共20分）1．某算法的計(jì)算時(shí)間T(n)滿足遞歸關(guān)系式：T(n)=2T(n/2)+1，n>1；T(1)=1。則Ｔ(n)=(A)。A．nlogn；B．logn；C．n2；D．nlgn；2．0-1背包問(wèn)題：n=6，W=10，v(1:6)=(15,59,21,30,60,5)，w(1:6)=(1,5,2,3,6,1）。該問(wèn)題的最大價(jià)值為（B）。A．101；B．110；C．115；D．120；3．給定一個(gè)無(wú)向圖G=（V,E），|V|=n，則圖的m可著色判定問(wèn)題的時(shí)間復(fù)雜度為（B）。A．O(mnm)；B．O(nmn)；C．O(2mn)；D．O(2nm)；4．以下關(guān)于P類(lèi)問(wèn)題的描述正確的是（B）A．存在多項(xiàng)式時(shí)間確定性算法的問(wèn)題是P類(lèi)問(wèn)題；B．存在多項(xiàng)式時(shí)間確定性算法的判定問(wèn)題是P類(lèi)問(wèn)題；C．存在多項(xiàng)式時(shí)間非確定性算法的問(wèn)題是P類(lèi)問(wèn)題；D．存在多項(xiàng)式時(shí)間非確定性算法的判定問(wèn)題是P類(lèi)問(wèn)題；5．以下關(guān)于判斷給定的一個(gè)正整數(shù)n是否為素?cái)?shù)的描述中正確的是（B）；A．如果(n-1)!modn=1-n，則n是素?cái)?shù)；B．如果(n-1)!modn=n-1，則n是素?cái)?shù)；C．如果對(duì)于區(qū)間（0，n）之間的任何一個(gè)整數(shù)a，an-1modn=1，則n一定是素?cái)?shù)。D．如果同余方程在區(qū)間（0，n）之間的解只有1和n-1，則n一定是素?cái)?shù)。6．隨機(jī)快速排序算法中，選取基準(zhǔn)元素的方法是（D）；A．選序列的第一個(gè)元素作為基準(zhǔn)元素；B．選序列的最后一個(gè)元素作為基準(zhǔn)元素；C．選序列的中間位置的元素作為基準(zhǔn)元素；D．隨機(jī)選擇序列中的一個(gè)元素作為基準(zhǔn)元素；7．在P不等于NP的前提下，以下關(guān)于P、NP和NP完全問(wèn)題的關(guān)系描述錯(cuò)誤的是（C）A．所有的P類(lèi)問(wèn)題都屬于NP類(lèi)問(wèn)題；B．所有的NP完全問(wèn)題都屬于NP類(lèi)問(wèn)題；C．P類(lèi)問(wèn)題和NP完全問(wèn)題有交集；D．NP完全問(wèn)題中哪怕一個(gè)問(wèn)題在多項(xiàng)式時(shí)間內(nèi)能夠解決，所有的NP類(lèi)問(wèn)題都能在多項(xiàng)式時(shí)間內(nèi)解決；8．給定隨機(jī)化算法A和任意小的正常數(shù)，算法A找到正確解的概率為p(0<p<1)，至少運(yùn)行（B）次算法A，使得算法得到正確解的概率不小于。A．；B．；C．；D．；9．將一般線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)線性規(guī)劃的過(guò)程中，以下描述正確的是（A）A．將最小化目標(biāo)轉(zhuǎn)化成最大化目標(biāo)時(shí)，需要將目標(biāo)函數(shù)兩邊同乘以（-1）；B．將小于等于的約束轉(zhuǎn)化為等于約束時(shí)，需要在小的一方添加一個(gè)大于0的松弛變量；C．將大于等于的約束轉(zhuǎn)化為等于約束時(shí)，需要在大的一方去掉一個(gè)大于等于0的人工變量；D．將小于等于的約束轉(zhuǎn)化為等于約束時(shí)，需要在小的一方添加一個(gè)大于等于0的人工變量；10．以下問(wèn)題中，不屬于NP完全問(wèn)題的是（B）A．最短路徑的判定問(wèn)題；B．漢諾塔問(wèn)題；C．哈密頓回路問(wèn)題；D．圖的m可著色判定問(wèn)題二、填空題（每空2分，共20分）1．貪心法的兩個(gè)基本要素是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。2．分治法的思想是將原問(wèn)題分成k（k>1）個(gè)子問(wèn)題，子問(wèn)題之間相互獨(dú)立且與原問(wèn)題相同，用遞歸方法求解子問(wèn)題，最后將子問(wèn)題的解合并成原問(wèn)題的解。3．最大團(tuán)問(wèn)題的解空間樹(shù)是子集樹(shù)，旅行商問(wèn)題的解空間樹(shù)是排列樹(shù)。4．回溯法是從根結(jié)點(diǎn)開(kāi)始，以深度優(yōu)先的方式進(jìn)行搜索解空間樹(shù)；分支限界法是從根結(jié)點(diǎn)開(kāi)始，以廣度（或最小費(fèi)用或最大效益）優(yōu)先的方式進(jìn)行搜索解空間樹(shù)。5．隨機(jī)化算法分為四類(lèi)，包括數(shù)值隨機(jī)化算法、蒙特卡羅算法、拉斯維加斯算法、舍伍德算法。三、問(wèn)答題（每題5分，共20分）1．簡(jiǎn)述算法的概念及特征。答：算法指的是對(duì)特定問(wèn)題求解步驟的一種描述，是若干條指令的有窮序列，（1分）并且具有以下特性：（1）輸入（零個(gè)或多個(gè)）（0.5分）（2）輸出（一個(gè)或多個(gè)）（0.5分）（3）確定性。組成算法的每條指令必須有確定的含義，無(wú)歧義。（1分）（4）有限性。算法中指令的條數(shù)是有限的，每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。（1分）（5）可行性。有待實(shí)現(xiàn)的運(yùn)算都是基本運(yùn)算。（1分）2．簡(jiǎn)述Prim算法構(gòu)造最小生成樹(shù)的基本思想答：首先，令U={u0}，u0V，TE={}。（1分）然后，只要U是V的真子集，就做如下貪心選擇：選取滿足條件iU，jV-U，且邊(i，j)是連接U和V-U的所有邊中的最短邊，即該邊的權(quán)值最小。（2分）將頂點(diǎn)j加入集合U，邊(i，j)加入集合TE。（1分）繼續(xù)上面的貪心選擇一直進(jìn)行到U=V為止。（1分）3．簡(jiǎn)述動(dòng)態(tài)規(guī)劃的求解步驟答：（1）分析最優(yōu)解的性質(zhì)，刻畫(huà)最優(yōu)解的結(jié)構(gòu)特征，即最優(yōu)子結(jié)構(gòu)性質(zhì)證明。（2分）（2）建立求最優(yōu)值的遞歸關(guān)系式（即建立遞歸式或動(dòng)態(tài)規(guī)劃方程）。（1分）（3）以自底向上的方式計(jì)算出最優(yōu)值，并記錄相關(guān)信息。（1分）（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造出最優(yōu)解。（1分）4．簡(jiǎn)述回溯法和分支限界法的異同答：相同點(diǎn)：（1）均需要先定義問(wèn)題的解空間，確定的解空間組織結(jié)構(gòu)一般都是樹(shù)或圖。（0.5分）（2）在問(wèn)題的解空間樹(shù)上搜索問(wèn)題解。（0.5分）（3）搜索前均需確定判斷條件，該判斷條件用于判斷擴(kuò)展生成的結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。（0.5分）（4）搜索過(guò)程中必須判斷擴(kuò)展生成的結(jié)點(diǎn)是否滿足判斷條件，如果滿足，則保留該擴(kuò)展生成的結(jié)點(diǎn)，否則舍棄。（0.5分）不同點(diǎn)（1）在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。（1分）（2）由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹(shù)上的搜索方式也不相同。（1分）（3）由于搜索方式不同，直接導(dǎo)致當(dāng)前擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式也不相同。（1分）四、綜合應(yīng)用題（每題10分，共20分）1．采用合并排序的思想將給定序列T[1:9]={5,3,8,2,1,9,23,12,6}由小到大排序。(要求：先描述合并排序的思想，然后寫(xiě)出首次分解得到兩個(gè)子問(wèn)題的過(guò)程、遞歸的結(jié)果、子問(wèn)題的解合并成原問(wèn)題的解的過(guò)程)解：合并排序的思想是將待排序序列平均分成兩個(gè)子序列，如果子序列的元素多于1個(gè)，則再將子序列平均分成兩個(gè)更小的子序列，直到子序列包含一個(gè)1個(gè)元素為止。（2分）然后將兩個(gè)有序的子序列合并成一個(gè)有序的子序列，最終將子序列合并成1個(gè)有序的子序列。（2分）按照合并排序的思想的排序過(guò)程如下：（1）(1+9)/2=5（1分）（2）兩個(gè)子問(wèn)題分別是：T[1:5]和T[6:9]（1分）（3）遞歸的結(jié)果T1:5]={1,2,3,5,8}T[6:9]={6,9,12,23}（1分）（4）將兩個(gè)子問(wèn)題的解合并得到原問(wèn)題的解，合并過(guò)程如下：a)根據(jù)合并算法，首先將1,2,3,5放到輔助數(shù)組中（0.5分）b)將6放到輔助數(shù)組中（0.5分）c)將8放到輔助數(shù)組中（0.5分）d)將9,12,23放到輔助數(shù)組中。這樣就得到一個(gè)有序的序列。（0.5分）（5）將輔助數(shù)組中的元素復(fù)制到數(shù)組T中，得到T[1:9]={1,2,3,5,6,8,9,12,23}平均分成兩個(gè)子序列。（1分）2．用動(dòng)態(tài)規(guī)劃的跳躍點(diǎn)算法求解0-1背包問(wèn)題的如下實(shí)例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先寫(xiě)出計(jì)算公式，再寫(xiě)具體的求解過(guò)程，指出最優(yōu)值和最優(yōu)解）解：p[n+1]={(0,0)}（1分）q[i+1]=p[i+1](wi,vi)（1分）p[i]=p[i+1]∪q[i+1]去掉受控點(diǎn)。(i=1,2,3,4,5)（2分）P[5]={(0,0)}（1分）P[4]={(0,0),(4,12)}（1分）P[3]={(0,0),(3,8),(4,12),(7,20)}（1分）P[2]={(0,0),(2,15),(5,23),(6,27),(9,35)}（1分）P[1]={(0,0),(2,15),(5,23),(6,27),(9,35)}（1分）最優(yōu)值為35，最優(yōu)解為（0,1,1,1）（1分）五、算法分析題（每題10分，共20分）1.用回溯法設(shè)計(jì)一算法解決0-1背包問(wèn)題。（要求：先給出算法框架及思想，然后指出選用的數(shù)據(jù)結(jié)構(gòu)，最后用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)算法并分析算法的時(shí)間復(fù)雜性）解：算法框架及思想（1）定義問(wèn)題的解空間：（x1,x2,…,xn），其中xi=0或1，(i=1,2,……,n)（1分）（2）確定解空間的組織結(jié)構(gòu)：子集樹(shù)，深度為問(wèn)題的規(guī)模。（1分）（3）搜索解空間：約束條件：（1分）限界條件：cp+rp>bestp，其中cp表示當(dāng)前已裝入背包的物品的總價(jià)值，rp表示剩余物品的總價(jià)值，bestp表示當(dāng)前找到的最優(yōu)價(jià)值。（1分）（4）搜索過(guò)程：從根結(jié)點(diǎn)開(kāi)始，以深度優(yōu)先的方式進(jìn)行搜索。在搜索的過(guò)程中，左孩子判斷約束條件，若滿足，則深一步搜索，否則剪枝；右孩子判斷限界條件，若滿足，則深一步搜索，否則剪枝搜索過(guò)程直到所有活結(jié)點(diǎn)變成死結(jié)點(diǎn)為止。（1分）選用的數(shù)據(jù)結(jié)一維數(shù)組。其中用一維數(shù)組x[]存放當(dāng)前解，一維數(shù)組bestx[]存放當(dāng)前最優(yōu)解，一維數(shù)組v[]存放n個(gè)物品的價(jià)值，一維數(shù)組w[]存放n個(gè)物品的重量。（1分）算法描述：Bound(inti){//計(jì)算上界 intcleft=c-cw;//剩余容量 intb=cp; //以物品單位重量?jī)r(jià)值遞減序裝入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //裝滿背包 if(i<=n) b+=p[i]/w[i]*cleft; returnb;}（1.5分）Backtrack(intt){if(t>n){ for(intj=1;j<=n;j++) bestx[j]=x[j]; bestp=cp; return;}if(cw+w[t]<=W)//搜索左子樹(shù){x[t]=1; cw+=w[t]; cp+=p[t]; Backtrack(t+1); cw-=w[t]; cp-=p[t];} if(Bound(t+1)>bestp)//搜索右子樹(shù) { x[t]=0; Backtrack(t+1); }}（2分）時(shí)間復(fù)雜性為：O（n2n）（0.5分）2.設(shè)G=（V,E）是一個(gè)二分圖，設(shè)計(jì)一算法，求二分圖G的最大匹配。（任選一種算法描述方式來(lái)描述算法）解：首先構(gòu)建一個(gè)網(wǎng)絡(luò)：給定一個(gè)二分圖G和將圖G的頂點(diǎn)集合V分成互不相交的兩部分的頂點(diǎn)了集X和Y如下構(gòu)造與之相應(yīng)的網(wǎng)絡(luò)W：（1）增加一個(gè)源s’利—個(gè)匯t’。（1分）（2）從s’向X的每一個(gè)頂點(diǎn)都增加一條有向邊；從Y的每一個(gè)頂點(diǎn)都增加一條到t’的有向邊。（1分）（3）原圖G中的每—條都改為相應(yīng)的由X指向Y的有向邊；（1分）（4）置所有邊的容量為1。（1分）然后用增廣路算法求網(wǎng)絡(luò)W的最大網(wǎng)絡(luò)流。增廣路算法步驟如下：（1）置初始可行流（如零流）；對(duì)節(jié)點(diǎn)標(biāo)號(hào)，即令=任意正值（如5）。（0.5分）（2）若，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。（0.5分）（3）取消所有節(jié)點(diǎn)的標(biāo)號(hào)，即令，；令LIST={}，對(duì)節(jié)點(diǎn)標(biāo)號(hào)，即令充分大的正值。（1分）（4）如果