《算法分析样卷.doc》由会员分享，可在线阅读，更多相关《算法分析样卷.doc（8页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计 样卷一、选择题（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（n
2、2）6. 大整数乘法可以利用（ ）的算法来实现。A、分治策略 B、动态规划法C、贪心法 D、回溯法7.下列程序段的频度是（ ）。for(i=0;in;i+)for(j=0;jn;j+) k+;A、n2 B、n C、n*(n+1)/2 D、 2n8. 下列问题一般不采用分治法的是（ ）。A、三分检索 B、求最大最小值问题C、最大子段和 D、矩阵连乘问题9. 对多段图问题描述不正确的是（ ）A、多段图是一个无向图 B、可用向前处理法C、可用向后处理法 D、可用分治法解决。10.以下对回溯法描述正确的是（ ）A、必须使用栈来实现算法。B、使用广度优先方式系统搜索问题解C、它可以用裁剪函数来减少搜索空
3、间的规模，减少时间复杂度D、回溯法只能用来求最优化问题二、填空题（20分，每空2分）1 算法的确定性是（ ）。有限性是指（ ）。2 矩阵连乘问题可以用（ ）设计。3 所谓贪心选择性质是指所求问题的（ ）以通过( )，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与（ ）主要区别。4 可以用（ ）来描述回溯法和分支限界法的解空间树。5 在回溯法中常用剪枝函数有( )和（ ）。6 矩阵连乘问题的最优子结构性质建立子问题最优值的递归关系。用m ij记录需要的最少数乘次数，则m ij递归定义为：（ ）三、简答题（20分，每小题5分） 1. 写出动态规划的基本要素。2. 说明贪心算法与
4、动态规划算法的的主要差别。3. 写出用回溯法搜索排列树的一般算法。4. 简述利用分冶法来解决大整数乘法的基本思想。四、算法设计题（40分）1.给定数组a0:n-1，试设计一个分治算法，在最坏情况下用 n+logn-2次比较找出a0:n-1中元素的最大值和次最大值。要求写出算法的思想，算法步骤，并说明时间复杂性。（20分）2. 给定由n 个整数组成的序列a0:n-1。序列a 的递增子序列定义为，存在下标序列i1i2ik使得ai1=ai2=n) output(x); else for (int i=t;iAi+n/2 将Ai和Ai+n/2交换3） 数组An/2:n-1的大小2, 则递归地进行分治法
5、求出最大值和次最大值。数组An/2:n-1的大小aright)*pmax=left;*psecond=right;else*pmax=right;*psecond=left;elseint m=(right-left+1)/2;for(int i=left;iai+m)int temp=ai;ai=ai+m;ai+m=temp;Search(a,pmax,psecond,left+m,right); if(a*pmax-ma*psecond) *psecond=*pmax-m; 时间复杂性4分当n是2的幂时(n=2k),有，T(n)=T(n/2) +n/2+1 n2 =1 n=2 =0 n=1
6、 上式展开： 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的最长公共子序列。若xmyn且zkxm，则Z是
7、Xm-1和Y的最长公共子序列。若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 (4)由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下： 由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
