算法分析与设计综合练习

《算法设计与分析》综合练习二、简答题(每题5分，共25分)一、填空题(每题2分，共30分)算法的复杂性有复杂性和复杂性之分。算法是由若干条指令组成的有穷序列，且要满足输入、输出、性和确定性、能行性等性质。利用分治策略求解问题的一般可分为三个步骤，分别是分解子问题，求解子问题和子问题。0-1背包问题可以用回溯法或策略解决。5.活动安排问题的贪心算法所需的计算时间为。动态规划算法的两个基本要素是性质和重叠子问题性质。回溯法在问题的解空间树中，按策略，从根结点出发搜索解空间树。回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和。若序列X={B,C,A,D,B,C,A}，Y={A,C,C,A,B,D,A,D}，请给出序列X和Y的一个最长公共子序列。求解组合优化问题时，采用策略不一定能够得到问题的最优解。对下面的递归算法，调用f(3)的执行结果是。voidf(intk)(if(k>0)(printf(〃%d\n〃,k);f(k-1); }}f(n)=6n+n2,f(n)的渐进性态f(n)=0()。选择排序、插入排序和归并排序算法中，算法是分治算法。消除递归一般要用到的数据结构是。用回溯法解旅行商问题时，该问题的解空间结构为树。简述递归算法的要素。简述动态规划法的基本步骤。分析下面程序的算法复杂性。intBinarySearch(Typea[],constType&x,intn)(//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-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为起点)以下是背包问题的贪心算法，请把程序填写完整。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） 、给出快速排序算法的平均时间复杂度和最坏情况时间复杂度；3） 、序列A={9,11,6,3,23,12,42,1,7,53}，给出一趟划分之后的结果。写出动态规划法求解下图从起点到终点的最短路径问题的过程和结果。三、应用题（每题10分，共30分）分治法之快速排序：根据快速排序算法回答下列问题。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） 写出该问题的剪枝