2、C问题的难度D适应能力算法分析是（）。A.将算法用某种程序设计语言恰当地表示岀來B.在抽象数据集合上执行程序，以确定是否会产生错误的结果C.对算法需要多少计算时间和存储空间作定量分析D.证明算法对所有可能的合法输入都能算出止确的答案下面问题（）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小牛成树问题D连续背包问题下列算法中不能解决0-1背包问题的是（）A贪心法B动态规划C回溯法D分支限界法若L是一个NP完全问题，L经过多项式时间变换后得到问题17,则L，是一个AP类问题BNP类问题CNP完全问题D不可解问题下面关于NP问
3、题说法正确的是（）ANP问题都是不可能解决的问题BP类问题包含在NP类问题中CNP完全问题是P类问题的了集DNP类问题包含在P类问题中以F关于判定问题难易处理的叙述中正确的是（）。A.可以市多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的Prim算法求最小生成树采用的是（）算法思想。A贪心算法B动态规划法C冋溯法D蛮力法归并排序算法的时间复杂度和空间复杂度是（）快速排序算法最差情况卜-的时间复杂度是（）实现人
4、整数的乘法的分治算法的时间复杂度是（）冇序表（12,24,36,4&60,72,84）中顺序、分査找关键字72时所盂进的关键字较次数是（）某种排序法对关键字序列（25,84,21,47,15,27,68,35,20）进排序，序列的变化情况如下:20.15.21.25.47.27.68.35.8415,20,21,25,35,27,47,6&8415.20.21.25.27.35.47.68.84请问釆的是哪种排序算法（）设某算法的时间复杂度为0（n3）o在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第
5、一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模多大的问题？1、一个算法的优劣可以用空间复杂度与时间复杂度來衡量。2、这种不断回头寻找冃标的方法称为四溯法o3、宜接或间接地调用自身的算法称为递归算法o二、求解或证明下面各式：（本题共4小题，共30分）1.求和式的计算或证明;=
6、F(n)=bF(n-l)+G(n),F(0)=c证明：F(n)二cb11+£//▼•G(i)。由此，推导Hanoi塔问题的通项公式。/=12.二阶常系数齐次线性递推关系求解x(n)=4x(n-l)-3x(n-2),x(l)=l,x(2)=3x(
7、n)=6x(n-l)-9x(n-2)+n,x(())=(),x(l)=la0=0,al=l,an二5a「-6an21.利用主定理，求T(n)增长的阶T(n)=25T(n/5)+nA2的时间复杂度T(n)=2T(n/3)+nA2的时间复杂度1.函数按照增长的速度从低到高排序4n2,logn,3n,n!,n2b2+3n+4n2,2logn,2n+3n,2A2An,2AnA2,sqrt(n)2.证明：函数的复杂度f(n)=n3+n2log100n3.已知函数x(intn){if(n<=3)return1;elsereturnx(n-2)
8、+x(n-4)+1;}三、算法理解题（本题共4小题，共35分）1.2.求x(x(8))运用分治法算法计算运用俄罗斯农夫算法计算m*no59*473.4.5.运用两种不同的算法求2348和1776的最大公因子。利用减治法计算p"除以q的余数。31000%5利用Dijkstra算法对下图结点a,求a到所有其他结点的最短路径。6.7.按照Johnson-Trotter算法和7典序生成全排列的算法给出下面排列的后面1015324个排列。丄亠丿厶r已知背包承重l,待放入背包的物品如下所示，用分支限界法求其最优解。n二4个物品,大小分别为W二
9、{1,2,4,6},价值分别为P二{5,5,6,9},背包容量为M=10o8.已知矩阵Mi(25*10)、M2(10*5)、M3(5*30)、M4(30*20)、M5(20*15),利用矩阵链相乘的动态规划算法，计算所需的最少乘法次数，并根据计算填
