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

1、湖南科技學(xué)院二。年學(xué)期期末考試信息與計算科學(xué)專業(yè) 年級算法設(shè)計與分析 試題考試類型：開卷試卷類型：C卷考試時量：120分鐘題號一二三四五總分統(tǒng)分人得分閱卷人一、填空題(每小題3分，共計30分)1.用O、和。表示函數(shù) f與g之間的關(guān)系。f n nlogn g n logn1,n 12 .算法的時間復(fù)雜性為 f(n),則算法的時間復(fù)雜性的階8f (3n/7) n, n 2為。3 .快速排序算法的性能取決于 。4 .算法是。5 .在對問題的解空間樹進(jìn)行搜索的方法中，一個活結(jié)點最多有一次機會成為活結(jié)點的是。6 .在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實際價值的是 情況下的時間復(fù)雜性。7 .大

2、符號用來描述增長率的下限，這個下限的階越 ,結(jié)果就越有價值。8 .是問題能用動態(tài)規(guī)劃算法求解的前提。9 .貪心選擇性質(zhì)是指 10 .回溯法在問題的解空間樹中， 按 策略，從根結(jié)點出發(fā)搜索解空間樹。二、簡答題（每小題10分，共計30分）1 .試述回溯法的基本思想及用回溯法解題的步驟。2 .有8個作業(yè)1,2,8模在由2臺機器M1和M2組成的流水線上完成加工。 每個作業(yè) 加工的順序都是先在 M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為：M110281269414M2571151631113作業(yè)12345678給出一個最優(yōu)調(diào)度方案，使得從第一個作業(yè)在機器 M1上開始加工，到最后一

3、個作業(yè)在機器M2上加工完成所需的時間最少，并計算所需的最少時間。答:最優(yōu)調(diào)度方案為所需的最少時間為：3 .根據(jù)優(yōu)先隊列式分支限界法，求下圖中從v1點到v9點的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點用X標(biāo)記，獲得中間解的結(jié)點用單圓圈。框起（如&2）,最優(yōu)解用雙圓圈框起。三、算法填空(每空2分，共計10分)設(shè)R=r1,，rn是要進(jìn)行排列的n個元素，其中元素ri,.，rn可能相同，試設(shè)計一個 算法，列出R的所有不同排列，并給出不同排列的總數(shù)。算法如下，填寫缺失的語句。template<typename Type>void Swap(Type &a,

4、Type &b)Type t=b;., n要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是Li, iwiwn。程序存儲問題要求確定這 n個程序在磁帶上的一個存儲方案，使得能夠在磁帶上存儲盡可能多的程序，在保證存儲最多程序的前提下還要求磁帶的利用率達(dá)到最大。(1)給出求解存儲最多程序的算法，并證明算法的正確性；(2)給出求解使磁帶的利用率達(dá)到最大的方案的算法思路。五、算法設(shè)計（共計15 分）通過鍵盤輸入一個高精度的正整數(shù)n （n的有效位數(shù)w 240）,掉掉其中任意s個數(shù)字后,剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。對給定的n和s,尋找一種方案，使得剩下的數(shù)字組成的新最小。如輸入

5、n 為 178543， s 為 4，結(jié)果為13 簡述你的算法思路；給出算法（用C+苗述）。注：正整數(shù)n 存于字符串中，例：string n="178543"(0)f(n尸 Q (g(n)log7 82. n 33.劃分的對稱性4 .由若干條指令組成組成的有窮序列（解決問題的一種方法或一個過程）5 .分枝限界法 6.最壞 7.高 8.最優(yōu)子結(jié)構(gòu)9 .所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。10 .深度優(yōu)先、簡答題（每小題 10分，共計30分）1.回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判

6、斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。5分基本步驟：5分針對撥給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)； 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。2.最優(yōu)調(diào)度方案為（6分）27548163所需的最少時間為：73 （4分在前一問正確的前提下方可得分）3.651220錯一處扣1分三、算法填空（每空 2分，共計10分）1. b=a2. Rt=Ri3. sum+4. Ri5. R,k+1,n,sum四、算法設(shè)計（共計 15分）貪心策略：最短程序優(yōu)先。將程序從小到大排序，

7、依次選取盡可能多的程序，但總長度不超過磁盤容量，則可求得最多可以存儲的程序個數(shù)m。采用回溯法，從n個程序中選取總長度最大的 m個，算法同裝載問題。五、算法設(shè)計（共計 15分）1. 7分為了盡可能地逼近目標(biāo)，選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字，否則刪除第一個遞減區(qū)間的首字母。然后回到串首，按上述規(guī)則再刪除下一個數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是總是的解。2. 8分 string MinNum(string n,int s)while(s>0)unsigned int i=0; / 從串首開始找while(i<()&&(i