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

第14頁(yè)湖南科技學(xué)院二○年學(xué)期期末考試信息與計(jì)算科學(xué)專業(yè)年級(jí)《算法設(shè)計(jì)與分析》試題題號(hào)一題號(hào)一二三四五總分統(tǒng)分人得分閱卷人復(fù)查人一、填空題（每小題3分，共計(jì)30分）1.用O、Ω和θ表示函數(shù)f與g之間的關(guān)系______________________________。2.算法的時(shí)間復(fù)雜性為，則算法的時(shí)間復(fù)雜性的階為_(kāi)_________________________。3.快速排序算法的性能取決于______________________________。4.算法是_______________________________________________________。5.在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是_________________________。6.在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實(shí)際價(jià)值的是_____情況下的時(shí)間復(fù)雜性。7.大Ω符號(hào)用來(lái)描述增長(zhǎng)率的下限，這個(gè)下限的階越___________，結(jié)果就越有價(jià)值。。8.____________________________是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。9.貪心選擇性質(zhì)是指____________________________________________________________________________________________________________________。10.回溯法在問(wèn)題的解空間樹(shù)中，按______________策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。二、簡(jiǎn)答題（每小題10分，共計(jì)30分）1.試述回溯法的基本思想及用回溯法解題的步驟。2.有8個(gè)作業(yè){1,2,…,8}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為：M110281269414M2571151631113作業(yè)12345678給出一個(gè)最優(yōu)調(diào)度方案，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少，并計(jì)算所需的最少時(shí)間。答：最優(yōu)調(diào)度方案為所需的最少時(shí)間為：_______________________3.根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫(huà)出求得最優(yōu)解的解空間樹(shù)。要求中間被舍棄的結(jié)點(diǎn)用×標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈○框起（如eq\o\ac(○,v2)），最優(yōu)解用雙圓圈◎框起。三、算法填空（每空2分，共計(jì)10分）設(shè)R={r1,r2,...,rn}是要進(jìn)行排列的n個(gè)元素，其中元素r1,r2,...,rn可能相同，試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列，并給出不同排列的總數(shù)。算法如下，填寫(xiě)缺失的語(yǔ)句。template<typenameType>voidSwap(Type&a,Type&b){Typet=b;________________;//1a=t;}template<typenameType>boolok(TypeR[],intk,inti){if(i>k)for(intt=k;t<i;t++)if(__________________)//2returnfalse;returntrue;}template<typenameType>voidPerm(TypeR[],intk,intn,int&sum){//n為元素個(gè)數(shù)，sum記錄不同排列的總數(shù)if(k==n){______________________;//3for(inti=1;i<=n;i++)cout<<___________________;//4cout<<endl;}else{for(inti=k;i<=n;i++)if(ok(R,k,i)){Swap(R[k],R[i]);Perm(_________________________);//5Swap(R[k],R[i]);}}}四、算法設(shè)計(jì)（共計(jì)15分）設(shè)有n個(gè)程序{1,2,3...,n}要存放在長(zhǎng)度為L(zhǎng)的磁帶上。程序i存放在磁帶上的長(zhǎng)度是Li，1≤i≤n。程序存儲(chǔ)問(wèn)題要求確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶上存儲(chǔ)盡可能多的程序，在保證存儲(chǔ)最多程序的前提下還要求磁帶的利用率達(dá)到最大。（1）給出求解存儲(chǔ)最多程序的算法，并證明算法的正確性；（2）給出求解使磁帶的利用率達(dá)到最大的方案的算法思路。。五、算法設(shè)計(jì)（共計(jì)15分）通過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n（n的有效位數(shù)≤240），去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。對(duì)給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新最小。如輸入n為178543，s為4，結(jié)果為13⑴簡(jiǎn)述你的算法思路；⑵給出算法（用C++描述）。注：正整數(shù)n存于字符串中，例：stringn="178543";n.at(0)//返回字符串n的第1個(gè)字符n.erase(2,3)//刪除n中索引為2開(kāi)始的3個(gè)字符解：⑴算法思路⑵算法stringMinNum(stringn,ints){湖南科技學(xué)院二○年學(xué)期期末考試《算法設(shè)計(jì)與分析》試題C答案一、填空題（每小題3分，共計(jì)30分）1.f(n)=Ω(g(n))2.3.劃分的對(duì)稱性4.由若干條指令組成組成的有窮序列（解決問(wèn)題的一種方法或一個(gè)過(guò)程）5.分枝限界法6.最壞7.高8.最優(yōu)子結(jié)構(gòu)9.所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。10.深度優(yōu)先二、簡(jiǎn)答題（每小題10分，共計(jì)30分）1.回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。5分基本步驟：5分①針對(duì)撥給問(wèn)題，定義問(wèn)題的解空間；②確定易于搜索的解空間結(jié)構(gòu)；③以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。2.最優(yōu)調(diào)度方案為（6分）27548163所需的最少時(shí)間為：73（4分在前一問(wèn)正確的前提下方可得分）3.錯(cuò)一處扣1分三、算法填空（每空2分，共計(jì)10分）1.b=a2.R[t]==R[i]3.sum++4.R[i]5.R,k+1,n,sum四、算法設(shè)計(jì)（共計(jì)15分）貪心策略：最短程序優(yōu)先。將程序從小到大排序，依次選取盡可能多的程序，但總長(zhǎng)度不超過(guò)磁盤(pán)容量，則可求得最多可以存儲(chǔ)的程序個(gè)數(shù)m。采用回溯法，從n個(gè)程序中選取總長(zhǎng)度最大的m個(gè)，算法同裝載問(wèn)題。五、算法設(shè)計(jì)（共計(jì)15分）1.7分 為了盡可能地逼近目標(biāo)，選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪除第一個(gè)遞減區(qū)間的首字母。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過(guò)程s次，剩下的數(shù)字串便是總是的解。2.8分stringMinNum(stringn,ints){while(s>0){unsignedinti=0;//從串首開(kāi)始找while(i<n.length()&&(