20141210--计科_算法分析与设计试卷(A).doc

《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(j

6、品的收益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