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

《算法設(shè)計(jì)與分析》綜合練習(xí)二、簡(jiǎn)答題(每題5分，共25分)一、填空題(每題2分，共30分)算法的復(fù)雜性有復(fù)雜性和復(fù)雜性之分。算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、性和確定性、能行性等性質(zhì)。利用分治策略求解問題的一般可分為三個(gè)步驟，分別是分解子問題，求解子問題和子問題。0-1背包問題可以用回溯法或策略解決。5.活動(dòng)安排問題的貪心算法所需的計(jì)算時(shí)間為。動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是性質(zhì)和重疊子問題性質(zhì)?；厮莘ㄔ趩栴}的解空間樹中，按策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ㄋ阉鹘饪臻g樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和。若序列X={B,C,A,D,B,C,A}，Y={A,C,C,A,B,D,A,D}，請(qǐng)給出序列X和Y的一個(gè)最長(zhǎng)公共子序列。求解組合優(yōu)化問題時(shí)，采用策略不一定能夠得到問題的最優(yōu)解。對(duì)下面的遞歸算法，調(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)是。用回溯法解旅行商問題時(shí)，該問題的解空間結(jié)構(gòu)為樹。簡(jiǎn)述遞歸算法的要素。簡(jiǎn)述動(dòng)態(tài)規(guī)劃法的基本步驟。分析下面程序的算法復(fù)雜性。intBinarySearch(Typea[],constType&x,intn)(//在a[0:n]中搜索x，找到x時(shí)返回其在數(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;}請(qǐng)分別寫出下圖的DFS和BFS序列。(以V1為起點(diǎn))以下是背包問題的貪心算法，請(qǐng)把程序填寫完整。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） 、給出快速排序算法的平均時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度；3） 、序列A={9,11,6,3,23,12,42,1,7,53}，給出一趟劃分之后的結(jié)果。寫出動(dòng)態(tài)規(guī)劃法求解下圖從起點(diǎn)到終點(diǎn)的最短路徑問題的過程和結(jié)果。三、應(yīng)用題（每題10分，共30分）分治法之快速排序：根據(jù)快速排序算法回答下列問題。1）、程序填空；VOidquicksort（A,low,high）{//對(duì)A[low..high]中的元素按非降序排序。iflow<highthen{w=PARTITION（A,low,high）〃算法PARTITION以A[low]為劃分元素將A[low..high]劃分成兩部分，并返回劃分元素的新位置。A有3個(gè)物品，其重量分別是{2,5,4},價(jià)值分別為{3,5,6},背包的容量為8,用回溯法解該問題。1） 畫出該問題的解空間樹；2） 寫出該問題的剪枝