华南农业大学算法设计与分析-期末试卷-A卷(完整含答案)2011.6

1装订线华南农业大学期末考试试卷（A卷）2010学年第二学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1、渐进算法分析是指（）。B（A）算法在最佳情况、最差情况和平均情况下的代价（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间（D）在最小输入规模下算法的资源代价2、下列算法中通常以自底向上的方式求解最优解的是（）。B（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法3、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下（）说法不正确？AA．让水桶大的人先打水，可以使得每个人排队时间之和最小B．让水桶小的人先打水，可以使得每个人排队时间之和最小C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样4、设有n个活动的集合s={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si,fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si=fj或者sj=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。A（A）最早结束的活动优先安排（B）最先开始的活动优先安排（C）占用资源时间最少的活动优先安排（D）占用资源时间最长的活动优先安排5、已知序列X={x1,x2,…,xm}，序列Y={y1,y2,…,yn}，使用动态规划算法求解序列X和Y的最长公共子序列，其最坏时间复杂度为（）。A（A）O(m*n)（B）O(m+n)（C）O(m*2n)（D）O(n*2m)6、关于回溯算法和分支限界法，以下（）是不正确描述。A（A）回溯法中，每个活结点只有一次机会成为扩展结点2装订线（B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中（C）回溯法采用深度优先的结点生成策略（D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略7、考虑背包问题：n=6，物品重量W=(1,5,2,3,6,1），价值P=(15,59,21,30,60,5)，背包载重量C＝10。能放进背包的物品价值最大为（）。C（A）101（B）110（C）115（D）1208、分派问题一般陈述如下：给n个人分派n件工作，把工作j分派给第i个人的成本为cost(i，j)，1≤i，j≤n，要求在给每个人分派一件工作的情况下使得总成本最小。此问题的解可表示成n元组（X1，…，Xn），其中Xi是给第i个人分配的工作号，且Xi≠Xj（i≠j）。此解空间的状态空间树被称为（）。A（A）排列树（B）子集树（C）宽度优先生成树（D）深度优先生成树9、当输入规模为n时，算法增长率最小的是（）。B（A）100n（B）10log2n（C）2n（D）3nlog2n10、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。D（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。但不同方法，算法复杂度上界可能不同二、应用题（本大题共5小题，每小题6分，共30分）1、对于以下程序段，分析其最坏时间复杂度。intF(intn){if(n==0)return1;elsereturnF(n-1)*n;}解：T(n)=T(n-1)+1n=0T(n)=T(n-1)+1n0得T（n）＝O（n）2、将下列复杂性函数按照渐进阶从低到高排序。2323log!log10nnnnnnnnn解：3210loglog23!nnnnnnnnn3装订线3、请画出0-1背包问题采用回溯搜索法的解空间树。解：4、有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？解：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。5、最大子段和问题：给定由n个整数（其中可能有负数）组成的序列，求该序列形如jikka的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：}max,max{jikknjia10动态规划解决方案：记njiajbjikkji11,}{max][，则对于n个整数序列的最大子段和问题，][maxjbnj1即为所求。动态规划递归式：njjajajbjajb11110]}[],[][max{]}[,max{][问：对于实例：（621aaa,,,）＝（12，－11，14，－3，5，－20），按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b数组中的数值以及最大子段和的值。解：b[]={12,1,15,12,17,-20}最大子段和为17。4装订线三、程序填空题（本大题共10空格，每空2分，共20分。注意：每个空格只填一个语句）1、使用回溯法求解n皇后问题，x[t]用于存储第t个皇后放置的列号，可直接使用求绝对值函数intabs(intx)。boolPlace(intk){for(intj=1;jk;j++)if(1)returnfalse;returntrue;}voidBacktrack(intt){if(tn)sum++;elsefor(inti=1;i=n;i++){x[t]=i;if(2)3}}1、(abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])2、Place(t)3、Backtrack(t+1)2、矩阵连乘问题，设p[0]为矩阵A[1]的行号，p[i]为矩阵A[i]的列号，m[i][j]为计算矩阵A[i:j]相乘所需的最少数乘次数，s[i][j]记录矩阵A[i:j]相乘的最优断开位置。voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i=n;i++)4for(intr=2;r=n;r++)1.5CM5装订线for(inti=1;i=n-r+1;i++){intj;5m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt;6if(tm[i][j]){m[i][j]=t;7}}}}4、m[i][i]=0;5、j=i+r-1;6、t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];7、s[i][j]=k;3、使用归并排序法求逆序对。intb[10000];voidcopy(inta[],intb[],intl,intr){intk=l;for(k;k=r;k++)a[k]=b[k];}intmerge(inta[],intb[],intleft,intm,intright){inti=left,j=m+1,c=left,count=0;6装订线while(i=m&&j=right){if(a[i]=a[j])8else{9b[c++]=a[j++];}}while(i=m)b[c++]=a[i++];while(j=right)b[c++]=a[j++];returncount;}intmergeSort(inta[],intleft,intright){inttotal=0;if(leftright){//至少有2个元素intm=(left+right)/2;//取中点total+=mergeSort(a,left,m);total+=mergeSort(a,m+1,right);10copy(a,b,left,right);//复制回数组a}returntotal;}8、b[c++]=a[i++];9、count+=m-i+1;10、total+=merge(a,b,left,m,right);四、算法设计题（本大题共2小题，每小题15分，共30分）1、【最长上升子序列问题】（15分）7装订线对于给定的一个序列12(,,,)Naaa，11000N。我们可以得到一些递增上升的子序列12(,,,)iiiKaaa，这里121KiiiN。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。参考解答：设()fi表示：从左向右扫描过来直到以[]ai元素结尾的序列，获得的最长上升子序列的长度，且子序列包含[]ai元素（1in）。11()max{()1:[][];1}111;(1)[][]ififjaiajjiiijjiaiaj当,都有即，()fi是从(1)f，(2)f……到(1)fi中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。最后，所要求的整个序列的最长公共子序列长度为max{f(i):1=i=n}例如，对于序列：4263152i1234567array4263152f(i)1122132评分准则：1)答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设定清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一）2)说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上；3)其它情况酌情考虑。2、【整数因子分解】（15分）大于1的正整数n都可以分解为n=x1*x2*...*xm例如：当n=12时，共有8种不同的分解式：12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*3对于给定正整数n，计算n共有多少种不同的分解式。8装订线参考解答：设采用递归实现对n的不同分解式个数的统计，设该函数名solve()。voidsolve(intn){if(n==1)total++;elsefor(inti=2;i=n;i++)if(n%i==0)solve(n/i);}