资源描述:
《20141210--计科_算法分析与设计试卷(A).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法分析与设计课程 考试试卷(第 A 卷)考试专业班级 计科12级 考试形式 考试时间 120 分钟考试学期 考试类型 命题教师 徐晓蓉 题号一二三四五六七八总分分值30202525…………………………………密………………封………………线……………………………………学号姓名不准超过密封线,否则试卷作废,成绩记零分。系 级 班 学号 姓名一、填空题(30分,每空2分)1、算法是。2、算法复杂度是指算法执行过程中所需空间和资源的量。3、凡渐进时间复杂度以为界的算法称做多项式时间算法。4、若我们可计算得到某算法的时间复杂度为T(n)=
2、10n2+9nlogn+1则用大O表示法T(n)=。5、一个问题能够用分治法求解的要素是:第一,问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题;第二,;第三,。6、用方法适合求解具有最优子结构特性和最优量度标准的最优化问题。7、在使用动态规划法求解最长公共子序列问题时,需定义一个二维数组来保存最长公共子序列的长度,设c[i][j]保存Xi=(x1,x2,…xi)和Yj=(y1,y2,…yj)的最长公共子序列的长度.那么,当i=0或j=0时,c[i][j]=;若xi=yj(i,j>0),则c[i][j]=;若xi≠yj(i,j>0),则c[i][j]
3、=。8、使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为;广度优先生成结点,并使用剪枝函数的方法称为。9,函数和函数统称为剪枝函数。10、回溯法本质上是一种以优先方式的搜索过程。二选择题(20分,每小题2分)1.对于给定的问题,考虑算法复杂性的意义在于()。A.设计出复杂性尽可能低的算法B.若该问题已有多种算法时,选择其中复杂性低的求解问题C.提高算法设计的学术水平层次D.判断算法的正确性2.下列关于难处理问题的说法正确的是()。A.能在多项式时间内求解的问题B.不存在多项式时间内求解算法的问题C.至今还没有找到多项式时间算法求解的问题D.无论消耗多少计算机时间和空间也
4、不能求解3.分枝限界法在解空间树T上的搜索方式是()。A.深度优先B.广度优先C.最小耗费优先D.活结点优先4.一个使用函数自身给出定义的函数称为()函数A、自定义B、递归C、反身D、可解5.下列不属于NP问题的是()。A.0/1背包问题B.TSP问题C.皇后问题D.排序问题6.有一段程序如下:voidGreedyKnapsack(float*x)//前置条件:w[k]已按p[k]/w[k]的非增次序排序{floatu=m;for(intj=0;ju)break;x[j]=1.0;u=u-w[j];}
5、if(j6、品的收益D.背包容量2三算法设计策略。(25分)1.有一八谜问题(八数码问题),初始状态和目标状态分别如下图所示。8数码问题的初始状态为:目标状态为:1234578612345678请采用LC分枝限界法求解。(1)定义代价估计函数(2分)(2)画出分枝限界法求解过程生成的状态空间树,并计算每个结点的代价估计函数值(6分)(3)请写出一个可行解。(1分)2.对于以下5个矩阵:M1:2*3,M2:3*6,M3:6*4,M4:4*2,M5:2*7,(1),用动态规划法求这5个矩阵相乘需要的最小数乘次数。(必须计算m和s矩阵,否则,不给分)(6分)(2),请给出一个括号化表达式,使在这
7、种次序下达到乘法的次数最少。(2分)3.设有0/1背包问题,n=5,(w0,w1,w2,w3,w4)=(2,6,3,4,4),(p0,p1,p2,p3,p4)=(3,15,6,8,10),M=12。请采用回溯法求解其最优解,要求:(1)画出回溯法求解过程中生成的状态空间树;(6分)(2)请求出最优解时的装包策略以及背包里的最大收益值。(2分)四算法设计(25分)1、Fibonacci数列问题:已知Fibonacci数列为:1,1,2,3,5,8,13,21,34………..(1)试给出Fibo