《算法分析与设计》 样卷一、选择题（20分，每题2分）1. 0-1背包问题用（ ）实现算法最好A、分治策略 B、动态规划法 C、贪心法 D、穷举法2. 下列动态规划的最基本的要素是（ ）A、算出最优解 B、贪心选择性质 C、重叠子问题 D、定义最优解 3. 下列算法中通常以广度优先方式系统搜索问题解的是（ ）A、分支限界法 B、动态规划法 C、贪心法 D、回溯法4. 自底向上方法是（ ）的计算最优值的方法中的一种A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法5. 一般(部分)背包问题的贪心算法所需的计算时间为（ ）A、O（n） B、O（nlogn）C、O（2n） D、O（n2）6. 大整数乘法可以利用（ ）的算法来实现。
A、分治策略 B、动态规划法C、贪心法 D、回溯法7..下列程序段的频度是（ ）for(i=0;i
有限性是指（ ）2． 矩阵连乘问题可以用（ ）设计3． 所谓贪心选择性质是指所求问题的（ ）以通过( )，即贪心选择来达到这是贪心算法可行的第一个基本要素，也是贪心算法与（ ）主要区别4． 可以用（ ）来描述回溯法和分支限界法的解空间树5． 在回溯法中常用剪枝函数有( )和（ ）6． 矩阵连乘问题的最优子结构性质建立子问题最优值的递归关系用m [i][j]记录需要的最少数乘次数，则m [i][j]递归定义为：（ ）三、简答题（20分，每小题5分） 1. 写出动态规划的基本要素2. 说明贪心算法与动态规划算法的的主要差别。
3. 写出用回溯法搜索排列树的一般算法4. 简述利用分冶法来解决大整数乘法的基本思想四、算法设计题（40分）1.给定数组a[0:n-1]，试设计一个分治算法，在最坏情况下用 n+[logn]-2次比较找出a[0:n-1]中元素的最大值和次最大值要求写出算法的思想，算法步骤，并说明时间复杂性20分）2. 给定由n 个整数组成的序列a[0:n-1]序列a 的递增子序列定义为，存在下标序列i1
（1）最优子结构性质（2）重叠子问题性质利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解最优子结构是问题能用动态规划算法求解的前提递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次这种性质称为子问题的重叠性质6. 说明贪心算法与动态规划算法的的主要差别对于贪心算法，所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别7. 写出用回溯法搜索子集树的一般算法遍历排列树需要O(n!)计算时间 void backtrack (int t){ if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } }8. 简述利用分冶法来解决大整数乘法的基本思想分治法: X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd复杂度分析 T(n)=O(n2) û没有改进为了降低时间复杂度，必须减少乘法的次数。
为此，我们把XY写成另外的形式：(1)XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd 或(2)XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd复杂性：这两个算式看起来更复杂一些，但它们仅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是 T(n)=O(nlog3) =O(n1.59) ü较大的改进J细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第(2)种方案四、算法设计题（40分）1.● 算法思想8分1)采用分治法将数组A[0:n]分成两部分，A[0:n/2-1]和A[n/2:n-1]2) 对从i=0到n/2-1 A[i]>A[i+n/2] 将A[i]和A[i+n/2]交换3） 数组A[n/2:n-1]的大小>2, 则递归地进行分治法求出最大值和次最大值数组A[n/2:n-1]的大小<=2，则直接求出最大值和次最大值假设最大值为A[p]，次最大值A[q]4) 原问题的最大值为A[p] 原问题的次最大值为A[p-n/2]和A[q]的较大者● 代码8分void Search(int a[],int *pmax,int *psecond,int left,int right){ if(left==right) { *pmax=*psecond=left; } else if(left==right-1) { if(a[left]>a[right]) { *pmax=left; *psecond=right; } else { *pmax=right; *psecond=left; } } else { int m=(right-left+1)/2; for(int i=left;ia[i+m]) { int temp=a[i]; a[i]=a[i+m]; a[i+m]=temp; } } Search(a,pmax,psecond,left+m,right); if(a[*pmax-m]>a[*psecond]) *psecond=*pmax-m; } }● 时间复杂性4分当n是2的幂时(n=2k),有，T(n)=T(n/2) +n/2+1 n>2 =1 n=2 =0 n=1 上式展开： T(n)=T(n/2) +n/2+1 =T(n/4) + n/4 + n/2+2 =T(n/8) + n/8 +n/4 + n/2+3 =…= T(2)+2+ 22 +…+22 + 2k-1+k-1 =1+2+ 22 +…+22 + 2k-1+k-1 =2k-1+k-1 =n+logn-22.（1）将序列 a进行递增排序得到序列b（2）序列 a和b的最长公共子序列就是a的最长递增子序列。
3）设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则§ 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列§ 若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列§ 若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列Ø 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列因此，最长公共子序列问题具有最优子结构性质 (4)由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系用c[i][j]记录序列和的最长公共子序列的长度其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}当i=0或j=0时，空序列是Xi和Yj的最长公共子序列故此时C[i][j]=0其它情况下，由最优子结构性质可建立递归关系如下： Ø 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率 void LCSLength(int m，int n，char *x，char *y，int **c，int **b){ int i，j;for (i = 1; i <= m; i++) c[i][0] = 0;for (i = 1; i <= n; i++) c[0][i] = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n; j++) {if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}else if (c[i-1][j]>=c[i][j-1]) {c[i][j]=c[i-1][j]; b[i][j]=2;}else { c[i][j]=c[i][j-1]; b[i][j]=3; }}}void LCS(int i，int j，char *x，int **b){if (i ==0 || j==0) return;if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<