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

算法設(shè)計與分析期末試卷一.選擇題（15*2分）下列不屬于一個好的算法應(yīng)具有的特性的是（C）正確性B.簡明性C無限性D最優(yōu)性矩陣連乘問題的算法可由（B）設(shè)計實現(xiàn)。A、分支界限算法B、動態(tài)規(guī)劃算法”貪心算法D、回溯算法廣度優(yōu)先是（A）的一搜索方式。A、分支界限法B、動態(tài)規(guī)劃法”貪心法D、回溯法學(xué)校要舉行運(yùn)動會，請你設(shè)計一個能夠?qū)\(yùn)動員分?jǐn)?shù)自動排序的軟件，如果要設(shè)計此軟件，以下最好的方法和步驟是（C）分析問題，編寫程序，設(shè)計算法，調(diào)試程序設(shè)計算法，編寫程序，提出問題，調(diào)試程序提出問題，設(shè)計算法，編寫程序，調(diào)試程序設(shè)計算法，提出問題，編寫程序，調(diào)試程序用計算機(jī)程序解決實際問題的過程中，需要進(jìn)行算法設(shè)計，算法指的是（A）A、解決問題的方法和步驟B、數(shù)值計算的方法C、實際問題的描述D、最終結(jié)果算法分析是（C）。將算法用某種程序設(shè)計語言恰當(dāng)?shù)乇硎境鰜碓诔橄髷?shù)據(jù)集合上執(zhí)行程序，以確定是否會產(chǎn)生錯誤的結(jié)果對算法需要多少計算時間和存儲空間作定量分析證明算法對所有可能的合法輸入都能算出正確的答案用貪心法設(shè)計算法的關(guān)鍵是（B）。A.將問題分解為多個子問題來分別處理B.選好貪心準(zhǔn)則C.獲取各階段間的遞推關(guān)系式D.滿足最優(yōu)性原理考慮背包問題：n=6,M=10,V(1:6)二(15,59,21,30,60,5),W(1:6)=(1,5,2,3,6,1)。該問題的最大效益值為(C)。若把它看著是0/1背包問題，則最大效益值為(B)。A.101B.110C.115D.120每個歸并步恰包含k個文件的歸并模式被稱為k元?dú)w并模式?？紤]用貪心法求解文件序列的最優(yōu)2元?dú)w并問題。當(dāng)要對8個長度為L(1:8)=(3,7,8,9,14,18,25,28)文件進(jìn)行歸并時，記錄移動的總數(shù)是(D)。A.198B.112C.210D.310找最小生成樹的算法Kruskal的時間復(fù)雜度為(D)。A.O(n2)B.O(mlogn)C.O(nlogm)D.O(mlogm)算法確認(rèn)是(B)o將算法用某種程序設(shè)計語言恰當(dāng)?shù)乇硎境鰜碜C明算法對所有可能的合法輸入都能算出正確的答案對算法需要多少計算時間和存儲空間作定量分析。.在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會產(chǎn)生錯誤的結(jié)果算法與程序的區(qū)別在于算法具有(C)。A.能行性B.確定性C.有窮性。.輸入和輸出設(shè)A[1..60]={11,12,,70}。算法折半查找在A上搜索x=33、7、70、77時執(zhí)行的元素比較次數(shù)分別為a、b、c、山則(C)oA.a<b<c<dB.a>b=c=dC.a<b=c=dD.a<c<b=d算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上運(yùn)行時執(zhí)行的元素比較次數(shù)為(D)oA.14B.28C.7D.22二分搜索算法是利用(A)實現(xiàn)的算法。A.分治法B.動態(tài)規(guī)劃法C.貪心法D.回溯法二、填空題（每空2分，共15個空）算法一般分為：算法和算法。一個合法的遞歸定義包括兩部分：和一個算法的是指算法運(yùn)行所需要的時間。如果無向連通圖G中不包含任何關(guān)節(jié)點(diǎn)，則稱該圖G為的基本運(yùn)算是把兩個或多個有序序列合并成一個有序序列。和要求問題最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點(diǎn)的求解方法稱為下面程序段的所需要的計算時間為intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++)(thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指回溯法的算法框架按照問題的解空間一般分為算法框架與算法框架11..若序列A={xzyzzyx},B={zxyyzxz}，請給出序列A和B的一個最長公共子序列。填空題答案：1、精確啟發(fā)式。2、基礎(chǔ)情況遞歸部分。3、時間復(fù)雜度4、雙連通圖。5、合并排序6、貪心法動態(tài)規(guī)劃法7、回溯法。8、O（n2）9、問題的最優(yōu)解包含了其子問題的最優(yōu)解10、子集樹排列樹11、XYZZ二.算法設(shè)計用歐幾里德迭代算法求兩個數(shù)的最小公倍數(shù)#include<iostream>usingnamespacestd;intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;while(m%t||n%t)t--;returnt;}intmain(){inta,b;cout<<"Inputa&b(0<=a<b):〃；cin>>a>>b;intm=a*b/Gcd(a,b);cout<<"TheLeastCommonMultipleis:"<<m<<endl;return0;}用分治法求第K小元素#include<iostream>usingnamespacestd;voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}intPartition(intR[],intlow,inthigh){inti=low,j=high,pivot=R[low];while(i<j){while(i<j&&R[j]>=pivot){j--;}if(i<j){swap(R[i++],R[j]);}while(i<j&&R[i]〈=pivot){i++;}if(i<j){swap(R[i],R[j--]);}}returnj;}intSelect(inta[],intp,intr,intk){if(p==r)returna[p];inti=Partition(a,p,r),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}intmain(){intn,k;//n為數(shù)的總個數(shù)，k為第幾小cout<<"n=";cin>>n;int*a=newint[n];cout<<"Thenumberis：";for(inti=0;i<n;i++){cin>>a[i];}cout<<"k=";cin>>k;cout<<"第〃<<k<<〃小為：〃<<Select(a,0,nT,k);cout<<endl;return0;}四.算法應(yīng)用題假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M=150,使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹(10分)。物品ABCDEFG重3365412量5000005價1435343值0000500答：按照單位效益從大到小依次排列這7個物品為：FBGDECAo將它

們的序號分別記為1?7。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得：=177.5(1,1,1,1,0,1|,0)40+40+30+50+30=177.5(1,1,1,1,0,1|,0)40+40+30+50+30x150—11560b.c.d.e.f.g.h.40+40+30+50+10=17040+40+30+35+30x150一105=167.56040+40+50+35+30x150—130=1756040+40+50+35+10x150一130=170.713540+40+50+30=1603d'1'1'"/(1,1,0,1,13,0)(1,1,0,1,1,0,：)(1,1,0,1,0,1,0)150—140°4°+40+35+30+10x—35—=146.85(1,1,。,。,1,1,；)i.J.40+30+50+35+30x^50^=167.5(1,0,1』，啟⑵__150—145__i.J.40+30+50+35+30x-60-=157.5(。'1'1'1'1'*。)在Q1處獲得該問題的最優(yōu)解為（1，1，1，1，。，。，1）,背包效益為170。即在背包中裝入物品F、B、G、D、A時達(dá)到最大效益，為170,重量為150。已知Ak="))r,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=12,Jiri+1r5=5,r6=50,r7=6,求矩陣鏈積A1XA2XA3XA4XA5XA6的最佳求積順序。(要求：