计算机09级《算法设计与分析》中考试卷试题1

1、计算机科学技术学院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用动态规划算法计算矩阵连乘问题的最优值所花的时间是 ，

2、 子问题空间大小是 。5n个物品的0-1背包问题可用 法求解，其解空间树中叶子结点个数是 ，解空间树中每个内结点的孩子数是 。三、计算题（共4小题，第1,2,3小题10分，第4小题15分，总计45分）1(10分) 给定两个序列X=B,C,D,A，Y=A,B,C,B，请按下列动态规划算法求其最长公共子序列。要求分别填写s矩阵和m矩阵，并标示出怎样求其最长公共子序列。填空。 void LCSLength(int m, int n, char *x, char *y, int *m, Type *s) int i, j; for(i=0; i<=m; i+) mi0=0; for(j=0; j

3、<=n; j+) m0j=0; for(i=1; i<=m; i+) for(j=1; j<=n; j+) if (xi=yj) mij= mi-1 j-1+1; sij=; else if (mi-1j> mij-1) mij= mi-1j; sij=; else mij= mij-1; sij=; void LCS(int i, int j, char *x, Type *s) if( (i=0) | (j=0) ) return ; if (sij=) LCS(i-1, j-1, x, s); cout<< xi; else if (sij=) LCS

4、(i-1, j, x, s); else LCS(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)= log n3； 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,请

5、写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的基本思想及贪心策略，并简要分析算法的时间复杂度。123456181117151921266794考虑n=3的批处理作业调度实例：tji机器1机器2作业1111作业231作业321其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。要求：（1）画出该问题的解空间树； （5分）（2）写出该问题的剪枝策略(即限界条件)，要求只保留第一个最优解； （2分）（3）按回溯法搜索解空间树，并用剪枝策略对解空间树中该剪枝的位置打´； （5分）（4）给出最优解及最优值。 （3分

6、）四、算法填空题（共1小题，总计15分）（15分）用分治策略设计的求一维空间上点集S中最接近点对的算法如下。int Cpair(int S , int l, int r)/算法的功能是确定数组S中l, r区间的最近点对距离 if (l>=r) ruturn ; / 注释：_ _ _int m=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中i+1，r区间的最小数d=min1(d1,d2,q-p); / 求三者中最小数，所花时间：_ _ return d ; / 返回最近点对的距离divide阶段所花的时间：_ _conquer阶段所花的时间：_ _