1、湖南科技學(xué)院二 年 學(xué)期期末考試信息與計(jì)算科學(xué)專業(yè) 年級(jí)算法設(shè)計(jì)與分析 試題題 號(hào)一二三四五總分統(tǒng)分人得 分閱卷人復(fù)查人考試類型：開(kāi)卷 試卷類型：C卷 考試時(shí)量：120 分鐘一、填空題（每小題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à)值。

2、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í)間

3、。答：最優(yōu)調(diào)度方案為所需的最少時(shí)間為：_3. 根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫出求得最優(yōu)解的解空間樹(shù)。要求中間被舍棄的結(jié)點(diǎn)用標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈框起（如），最優(yōu)解用雙圓圈框起。三、算法填空（每空2分，共計(jì)10分）設(shè)R=r1, r2, ., rn是要進(jìn)行排列的n個(gè)元素，其中元素r1, r2, ., rn可能相同，試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列，并給出不同排列的總數(shù)。算法如下，填寫缺失的語(yǔ)句。templatevoid Swap(Type &a,Type &b) Type t=b; _; /1 a=t;templatebool ok(Type R,int k,int i) if(ik) for(int t=k;ti;t+) if( _) /2 return false; return true;templatevoid Perm(Type R,int k,int n,int &sum) /n為元素個(gè)數(shù)，sum記錄不同排列的總數(shù) if(k=n) _; /3 for(int i=1;i=n;i+) cout_; /4 coutendl; else for(int i=k;i0) unsigned int i=0; /從串首開(kāi)始找 while(in.length