算法分析與設(shè)計綜合練習(xí)

《算法設(shè)計與分析》綜合練習(xí)二、簡答題(每題5分，共25分)一、填空題(每題2分，共30分)算法的復(fù)雜性有復(fù)雜性和復(fù)雜性之分。算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、性和確定性、能行性等性質(zhì)。利用分治策略求解問題的一般可分為三個步驟，分別是分解子問題，求解子問題和子問題。0-1背包問題可以用回溯法或策略解決。5.活動安排問題的貪心算法所需的計算時間為。動態(tài)規(guī)劃算法的兩個基本要素是性質(zhì)和重疊子問題性質(zhì)?；厮莘ㄔ趩栴}的解空間樹中，按策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為約束函數(shù)和。若序列X={B,C,A,D,B,C,A}，Y={A,C,C,A,B,D,A,D}，請給出序列X和Y的一個最長公共子序列。求解組合優(yōu)化問題時，采用策略不一定能夠得到問題的最優(yōu)解。對下面的遞歸算法，調(diào)用f(3)的執(zhí)行結(jié)果是。voidf(intk)(if(k>0)(printf(〃%d\n〃,k);f(k-1); }}f(n)=6n+n2,f(n)的漸進(jìn)性態(tài)f(n)=0()。選擇排序、插入排序和歸并排序算法中，算法是分治算法。消除遞歸一般要用到的數(shù)據(jù)結(jié)構(gòu)是。用回溯法解旅行商問題時，該問題的解空間結(jié)構(gòu)為樹。簡述遞歸算法的要素。簡述動態(tài)規(guī)劃法的基本步驟。分析下面程序的算法復(fù)雜性。intBinarySearch(Typea[],constType&x,intn)(//在a[0:n]中搜索x，找到x時返回其在數(shù)組中的位置，否則返回-1Intleft=0;intright二n-1;While(left<=right)(intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}Return-1;}請分別寫出下圖的DFS和BFS序列。(以V1為起點(diǎn))以下是背包問題的貪心算法，請把程序填寫完整。voidKnapsack（intn,floatc,floatv[],floatw[],floatx[]）(Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;for(i=1;i<=n;i++)(if(w[i]>c)break;x[i]=1;⑴ ；}if(i<=n) (2) ;}

quicksort(A,w+1,high)}}2） 、給出快速排序算法的平均時間復(fù)雜度和最壞情況時間復(fù)雜度；3） 、序列A={9,11,6,3,23,12,42,1,7,53}，給出一趟劃分之后的結(jié)果。寫出動態(tài)規(guī)劃法求解下圖從起點(diǎn)到終點(diǎn)的最短路徑問題的過程和結(jié)果。三、應(yīng)用題（每題10分，共30分）分治法之快速排序：根據(jù)快速排序算法回答下列問題。1）、程序填空；VOidquicksort（A,low,high）{//對A[low..high]中的元素按非降序排序。iflow<highthen{w=PARTITION（A,low,high）〃算法PARTITION以A[low]為劃分元素將A[low..high]劃分成兩部分，并返回劃分元素的新位置。A有3個物品，其重量分別是{2,5,4},價值分別為{3,5,6},背包的容量為8,用回溯法解該問題。1） 畫出該問題的解空間樹；2） 寫出該問題的剪枝