计算机科学技术学院09级《算法设计与分析》中考试题简答题（共3小题，第1小题2分，第2，3小题4分，总计10分）1.(2分)请用英文写出两种以上能求解0-1背包问题的设计算法策略。2.(4分)请叙述动态规划法的基本思想。3.(4分)请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？二、填空题（共10个空，每空1分，总计10分）1．递归的快速排序算法在最好情况下divide阶段所花的时间是，conquer阶段所花的时间是，算法的时间复杂度是。3．背包问题可用，等策略求解。4．用动态规划算法计算矩阵连乘问题的最优值所花的时间是，子问题空间大小是。5．n个物品的0-1背包问题可用法求解，其解空间树中叶子结点个数是，解空间树中每个内结点的孩子数是。三、计算题（共4小题，第1,2,3小题10分，第4小题15分，总计45分）1．(10分)给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请按下列动态规划算法求其最长公共子序列。要求分别填写s矩阵和m矩阵，并标示出怎样求其最长公共子序列。填空。voidLCSLength(intm,intn,char*x,char*y,int**m,Type**s){inti,j;for(i=0;i<=m;i++)m[i][0]=0;for(j=0;j<=n;j++)m[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){m[i][j]=m[i-1][j-1]+1;s[i][j]=‘↖’;}elseif(m[i-1][j]>m[i][j-1]){m[i][j]=m[i-1][j];s[i][j]=‘↑’;}else{m[i][j]=m[i][j-1];s[i][j]=‘←’;}}voidLCS(inti,intj,char*x,Type**s){if((i==0)||(j==0))return;if(s[i][j]==‘↖’){LCS(i-1,j-1,x,s);cout<<x[i];}elseif(s[i][j]==‘↑’)LCS(i-1,j,x,s);elseLCS(i,j-1,x,s);}s矩阵最长公共子序列:m矩阵2．（10分）对下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简要说明理由。(1)f(n)=logn3；g(n)=(2)f(n)=n!；g(n)=3n(3)f(n)=1000；g(n)=log100(4)f(n)=5n；g(n)=7n(5)f(n)=2n；g(n)=n53．（10分）对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的基本思想及贪心策略，并简要分析算法的时间复杂度。123456181117151921266794．考虑n=3的批处理作业调度实例：tji机器1机器2作业1111作业231作业321其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。要求：（1）画出该问题的解空间树；（5分）（2）写出该问题的剪枝策略(即限界条件)，要求只保留第一个最优解；（2分）（3）按回溯法搜索解空间树，并用剪枝策略对解空间树中该剪枝的位置打；（5分）（4）给出最优解及最优值。（3分）四、算法填空题（共1小题，总计15分）（15分）用分治策略设计的求一维空间上点集S中最接近点对的算法如下。intCpair(intS[],intl,intr)//算法的功能是确定数组S中[l,r]区间的最近点对距离{if(l>=r)ruturn∞;//注释：____________________________intm=selec(S,l,r,(r-l)/2);//找出中位数m，所花时间：__________i=partition(a,l,r,m）;//用中位数m将数组分为两段,所花时间：_____d1=Cpair(S,l,i);//求数组S中[l,i]区间的最近点对距离,所花时间：_______d2=_________;p=max(S,l,i);//求数组S中[l,i]区间的最大数，所花时间：_______q=min(S,i+1,r);//求数组S中