2010.6试卷A

1装订线华南农业大学期末考试试卷（A卷）2009学年第二学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1、优先队列通常用（B）数据结构来实现。（A）栈（B）堆（C）队列（D）二叉查找树2、渐进算法分析是指（B）。（A）算法在最佳情况、最差情况和平均情况下的代价（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间（D）在最小输入规模下算法的资源代价3、拉斯维加斯算法的特征是（A）。（A）其所做的随机性决策有可能导致算法找不到所需的解（B）其所做的随机性决策用于求问题的近似解（C）其所做的随机性决策用于消除问题的好坏实例之分（D）总能求得一个解，但是其所做的随机性决策导致所求到的解有可能是不正确的4、设有n个活动的集合s={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si,fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si=fj或者sj=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（C）。（A）最早结束的活动优先安排（B）最先开始的活动优先安排（C）占用资源时间最少的活动优先安排（D）占用资源时间最长的活动优先安排5、已知序列X={x1,x2,…,xm}，序列Y={y1,y2,…,yn}，使用动态规划算法求解序列X和Y的最长公共子序列，其最坏时间复杂度为（A）。（A）O(m*n)得分2装订线（B）O(m+n)（C）O(m*2n)（D）O(n*2m)6、关于回溯算法和分支限界法，以下（A）是不正确描述。（A）回溯法中，每个活结点只有一次机会成为扩展结点（B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中（C）回溯法采用深度优先的结点生成策略（D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略7、考虑背包问题：n=6，物品重量W=(1,5,2,3,6,1），价值P=(15,59,21,30,60,5)，背包载重量C＝10。能放进背包的物品价值最大为（B）。（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）排列树（B）子集树（C）宽度优先生成树（D）深度优先生成树9、当输入规模为n时，算法增长率最小的是（A）。（A）100n（B）10log2n（C）2n（D）3nlog2n10、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。但不同方法，算法复杂度上界可能不同二、应用题（本大题共5小题，每小题6分，共30分）1、对于以下程序段，分析其最坏时间复杂度。intF(intn){if(n==0)return1;得分3装订线elsereturnF(n-1)*n;}2、请解释什么是P问题，NP问题以及NP完全问题并描述这三者之间的关系；最后，请列举几个常见的NP完全问题。3、对于n=3，重量w=[16,15,15]，价值p=[45,15,25]，背包载重量C=30的0-1背包问题，请画出其解空间树，并在此解空间树中标出使用回溯法搜索时由剪枝条件：当前放进背包的物品重量之和不能超过背包载重量限制触发的剪枝。4、设a[1…n]是已排好序的数组。请改写二分搜索算法，使得当搜索元素不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当所搜元素在数组中时，i和j相同，为x在数组中的位置。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数组中的数值以及最大子段和的值。三、程序填空题（本大题共10空格，每空2分，共20分。得分1.5CM4装订线注意：每个空格只填一个语句）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}}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++)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++){5装订线intt;6if(tm[i][j]){m[i][j]=t;7}}}}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;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;}6装订线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;}四、算法设计题（本大题共2小题，每小题15分，共30分。请先说明算法设计思路，然后用C语言实现）1、googlebook作为世界上最好的黑客之一，你希望下载由GoogleBook发行的书本，因此你需要事先获取书本每页的地址。调研之后，你发现书本的每页地址由两部分组成：一部分是页码，另一部分是每页的个性签名。你可以通过向服务器发送查询来得到此签名，查询时以页码为参数，服务器会返回包含查询页在内的若干连续页的签名。如你向服务器发送参数i，则服务器会返回第i页的签名，另外，服务器还有可能返回与第i页相邻的其他页签名。为了尽量避免管理员发现你的黑客身份，你现在的任务是，如何以最少的查询次数把一本n页的书每页的签名都获取到。输入：第一行：页码n接下来输入n行，其中第i行为两个整数ai，bi，表示查询页码i时返回第ai页到第bi页的签名，(ai=i=bi)。输出：最少的查询次数。得分7装订线2、邮局选址问题有一条公路经过Ｖ个村庄，每一个村庄都处在整数的坐标点上（这里假设公路为一直线，定为Ｘ轴）。规划在这条公路上建立Ｐ个邮局，当然为了方便，这些邮局应建在某Ｐ个村庄上，但是要求让不同村庄的人到邮局要走的总路程最小。请设计一个合理的算法去建立这P个邮局。输入：读入两个整数Ｖ和Ｐ，V为村庄的数目，P为要盖邮局的数目，然后再读入Ｖ个整数，分别表示Ｖ个村庄的坐标（坐标＞＝０）。输出：输出Ｐ个以空格分隔的整数，按坐标从小到的顺序给出Ｐ个邮局的坐标。