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

1、2021 年算法分析與設(shè)計(jì)期末考試試卷 B 卷西南交通大學(xué) 20212021 學(xué)年第 一 學(xué)期考試試卷課程代碼 3244152課程名稱算法分析與設(shè)計(jì)考試時(shí)間120 分鐘閱卷教師簽字：填空題每空 1 分，共 15 分1 、 2、 3、 4、 5、程序是 1 用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。矩陣連乘問題的算法可由 2設(shè)計(jì)實(shí)現(xiàn)。從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是3。 大整數(shù)乘積算法是用 4來設(shè)計(jì)的。貪心算法總是做出在當(dāng)前看來 5 的選擇。也就是說貪心算法并不從整體最優(yōu)考慮， 它所做出的選擇只是在某種意義上的6 。 6 、 7 、 8 、回溯法是一種既帶有 7 又帶有 8 的搜索算法

2、。平衡二叉樹對(duì)于查找算法而言是一種變治策略，屬于變治思想中的9 類型。 在忽略常數(shù)因子的情況下，0、Q和提供了算法運(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。班 級(jí)學(xué) 號(hào)姓 名選擇題每題 2 分，共 20分1 、二分搜索算法是利用 實(shí)現(xiàn)的算法。A 、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法2、衡量一個(gè)算法

3、好壞的標(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ì) 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)賽日程表利用的算法是 。 A 、分治策略 C 、貪心法 6 、B 、動(dòng)態(tài)規(guī)劃法D 、回溯法回溯法的效率

4、不依賴于以下哪些因素 A. 滿足顯約束的值的個(gè)數(shù) C. 計(jì)算限界 函數(shù)的時(shí)間B. 計(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 、分支界限法 B 、動(dòng)態(tài)規(guī)劃法 C 、貪心法 D 、回溯法三、算法及程序

5、分析共 25 分。1 閱讀下面的程序，按要求答復(fù)以下問題：共 10 分 #include#includeint 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;i scanf("%d",&mapij); max = 0;for (i=0;i memset(visi,-1,sizeof (visi); for (j=0;j ans = dp(i,j);if

6、 (ans>max) max = ans; printf("%dn",max); return 0; int dp(int i , int j ) int max = 0;if (visi j >0)return visi j ; if (i -1>=0) if (mapi -1j max = dp(i -1, j );if (i +1if (mapi +1j max = dp(i +1,j );if (j -1>=0)if (mapi j -1 max = dp(i , j -1);if (j +1if (mapi j +1 max = dp(i

7、, j +1);return visi j = max+1; (1) 該程序采用什么算法？( 2 分)123(2) 設(shè) R=5,C=5,map 的值如下所示時(shí)程序執(zhí)行結(jié)束之后 max 的值是多少？106574205 301115 2512231314 20141816191530(2)上述程序的時(shí)間復(fù)雜度是多少？(共 3 分)5 分)閱讀下面的程序，按要求答復(fù)以下問題。(共 15 分) typedef struct SqListint *r; int Length; SqList;void HeapSort(SqList *H) int i; int rc;for(i=H->Length

8、/2;i>0;-i)HeapAdjust(H,i,H->Length); for(i=H->Length;i>1;-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;jif(jrjrj+1) +j;if(rc>=H->rj) break; rm=H->rs;H->rs=H->rj; H-

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