2015年算法分析與設(shè)計(jì)期末考試試卷B卷

1、班 級(jí) 學(xué) 號(hào) 姓 名 密封裝訂線 密封裝訂線 密封裝訂線西南交通大學(xué)20152016學(xué)年第(一)學(xué)期考試試卷課程代碼 課程名稱 算法分析與設(shè)計(jì) 考試時(shí)間 120 分鐘 題號(hào)一二三四五總成績(jī)得分閱卷教師簽字： 一、 填空題（每空1分，共15分）1、 程序是 （1）用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。2、 矩陣連乘問題的算法可由 （2） 設(shè)計(jì)實(shí)現(xiàn)。3、 從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 （3） 。4、 大整數(shù)乘積算法是用 （4） 來設(shè)計(jì)的。5、 貪心算法總是做出在當(dāng)前看來 （5） 的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 （6） 。6、 回溯法

2、是一種既帶有 （7） 又帶有 （8） 的搜索算法。 7、 平衡二叉樹對(duì)于查找算法而言是一種變治策略，屬于變治思想中的 （9） 類型。8、 在忽略常數(shù)因子的情況下，O、和三個(gè)符號(hào)中， （10） 提供了算法運(yùn)行時(shí)間的一個(gè)上界。9、 算法的“確定性”指的是組成算法的每條 (11) 是清晰的，無歧義的。10、 問題的 (12) 是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。11、 算法就是一組有窮 (13) ，它們規(guī)定了解決某一特定類型問題的 (14) 。12、 變治思想有三種主要的類型：實(shí)例化簡(jiǎn)，改變表現(xiàn)， (15) 。二、 選擇題（每題2分，共20分）1、 二分搜索算法是利用（ ）實(shí)現(xiàn)的算法。

3、A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法2、 衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（ ）。A、運(yùn)行速度快 B、占用空間少 C、 時(shí)間復(fù)雜度低 D、代碼短3、 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（ ）A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) 4、 D. 預(yù)排序與遞歸調(diào)用4、 常見的兩種分支限界法為（ ）A、 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B、 隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法；C、 排列樹法與子集樹法；D、 隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法；5、 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（

4、）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法6、 回溯法的效率不依賴于下列哪些因素（ ）A.滿足顯約束的值的個(gè)數(shù) B. 計(jì)算約束函數(shù)的時(shí)間 C. 計(jì)算限界函數(shù)的時(shí)間 D. 確定解空間的時(shí)間7、 使用分治法求解不需要滿足的條件是（ ）。A、 子問題必須是一樣的 B、 子問題不能夠重復(fù)C、 子問題的解可以合并 D、 原問題和子問題使用相同的方法解8、 實(shí)現(xiàn)合并排序利用的算法是（ ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法9、 背包問題的貪心算法所需的計(jì)算時(shí)間為（ ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）10、 廣度優(yōu)先是（ ）的一搜索方式。A、分支界

5、限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法三、 算法及程序分析（共25分）。1 閱讀下面的程序，按要求回答問題：（共10分） #include #include int vis101101; int map101101;int R,C;int dp(int i,int j)；int main() int i,j,ans,max; scanf(%d%d,&R,&C); for(i=0;iR;i+) for(j=0;jC;j+) scanf(%d,&mapij); max = 0; for(i=0;iR;i+) memset(visi,-1,sizeof(visi); for(j=0;jmax)

6、 max = ans; printf(%dn,max); return 0;int dp(int i,int j) int max = 0;if(visij0) return visij;if(i-1=0) if(mapi-1jmapij) if(maxdp(i-1,j) max = dp(i-1,j); if(i+1R) if(mapi+1jmapij) if(max=0) if(mapij-1mapij) if(maxdp(i,j-1) max = dp(i,j-1); if(j+1C) if(mapij+1mapij) if(maxLength/2;i0;-i) HeapAdjust(H

7、,i,H-Length);for(i=H-Length;i1;-i) rc=H-r1; H-r1=H-ri; H-ri=rc; HeapAdjust(H,1,i-1); return;void HeapAdjust(SqList *H,int s, int m) int rc,rm; int j; rc=H-rs;for(j=2*s;j=m;j*=2) if(jrjrj+1) +j; if(rc=H-rj) break; rm=H-rs; H-rs=H-rj; H-rj=rm; s=j; H-rs=rc; return;（1） 該程序采用什么算法? （2分）（2） 設(shè)傳遞給函數(shù)void Hea

8、pAdjust(SqList *H,int s, int m)的參數(shù)如下：H-Length: 8H-r: 15, 18,16,32,14,45,78,30,43s=1m=8請(qǐng)問程序函數(shù)執(zhí)行后H-r的值。 （共5分） （3）該程序的時(shí)間復(fù)雜度是多少，寫出求解過程。（共8分）四、 算法描述題（共20分）。1、已知某倉(cāng)庫(kù)有若干件商品，每件商品的重量為Wi,價(jià)值為Vi。某貨車能裝載的最大重量為W，請(qǐng)將倉(cāng)庫(kù)中的部分商品裝載到貨車中，使其總價(jià)值最大。要求每件商品只能裝載1件，且所有貨物的總重量不能超過貨車的總裝載量。（1）用文字描述采用動(dòng)態(tài)規(guī)劃算法求解上述問題的步驟。（6分）（2）用文字描述采用回溯法求解上述問題的步驟。（6分）（3）若倉(cāng)庫(kù)中有8件商品，貨車能裝載的最大重量為5000公斤，每件商品的重量及價(jià)值如下表所示，請(qǐng)用圖的形式描述采用分支限界法求解該問題時(shí)堆的變化過程。（共8分）商品編號(hào)12345678商品重量（公斤）1000800 1500 4000 600 4002000 3200商品價(jià)值（元）2000160032002800180080032004000五、 算法設(shè)計(jì)及實(shí)現(xiàn)(共20分) 1、設(shè)某校最多有200門可選課程，而每個(gè)學(xué)生每學(xué)期最多可以選2門課程。在期末考試時(shí)，每天考試可安排在上午1次，下午1次，請(qǐng)編寫程序求所有學(xué)生考試完所選課程需要安排的