算法设计期末考试.docVIP

算法设计 一、填空题 1、衡量算法的两个指标：时间复杂度、空间复杂度。 2、回溯算法的基本思想：按照深度优先的策略，从根节点出发有哪些信誉好的足球投注网站解空间树。 3、动态规划算法适合解决的问题：最优化问题。 4、分治算法的典型应用：二分法。 5、时间复杂度T（n）中O的定义；判断时间复杂度等价于什么？ 定义：用来表示解决问题算法所需的时间总量f（n）的上界。O是数量级的符号，用来表示时间复杂度。 6、分支限界法的基本思想：以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 7、贪婪算法适合解决什么问题：局部最优化问题。 8、递归算法的定义： 定义：递归是一个过程或函数在其定义或说明中又直接或间接调用自身的方法。 算法定义：就是把一个大型复杂的问题层层转化为一个与原问题想死的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。 二、选择题 1、算法时间复杂度密集度高低判断？ O（l）O（log2n）O（n）O（n^t）O（t^n）O（n!） 2、最大效益优先是哪种算法的首选方式？ 分支限界法。 3、P、NP类问题及关系？ 存在多项式时间的算法的一类问题为P类问题，没有找到多项式时间的算法的一类问题为NP类问题。NP类中的所有问题都是P类。 4、设计循环赛日程表采用什么算法？ 二分策略递归算法、二分策略非递归算法、利用数据间的规律构造算法、二维递推算法。 5、动态规划的步骤有：划分阶段、选择状态、确定决策并写出状态转移方程。 6、贪婪算法的基本要素：最优子结构设计、贪婪选择性质。 7、分治算法解决问题必须满足的条件： 1）能将这几个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1k=n； 2）分解所得到的子问题与原问题具有相似的结构，便于利用地柜或循环机制； 3）在求出这些子问题的解之后就可以推理出原问题的解。 8、动态规划算法与贪婪算法解决问题的特征： 动态规划算法：多阶段最优化解决问题。 贪婪算法：以逐步的局部最优达到最后的全局最优。 三、简答题 1、递归算法的设计与执行过程。 1）递归算法设计：把一个大型复杂的问题层层转化为一个与原问题想死的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。 2）执行过程：分析问题，寻找递归关系；设置边界，控制递归；设计函数，确定参数。 2、动态规划算法的设计步骤。 1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。 2）选择状态：将问题发展到各个阶段时所出现的各种客观情况用不同的状态表示出来。 3）确定决策并写出状态转移方程。 3、阐述某个数列的特征（先写式子，再写特点） 1）斐波那契数列的特点 a1,a2已知 a(n)=a(n-1)+a(n-2) n=3 2）上楼梯问题为什么适合用斐波那契数列求解？ 上楼梯问题通过反向思考，到第n阶有两种情况：从第n-1阶到第n阶；从第n-2阶到第n阶。 记n阶台阶的走法数为f(n),则f(n)=1 n=1;2 n=2;f(n-1)+f(n-2) n2 反向分析法和递归设计一样，就是找出大规模问题与小规模问题之间的关系，而这个关系正好符合斐波那契数列的规律。 4、写出算法设计思路并分析。 （1）递归（汉诺塔问题） 设计思路：找出大规模问题与小规模问题的递归关系。 1）将A基座上面的n-1个盘子借助B基座移到C基座上。 2）将A基座剩余的一个n号盘子移到B基座上。 3）将C基座的n-1个盘子借助A基座移到B基座上。 分析：递归算法执行中有递归调用的过程和回溯的过程，递归法就是通过调用把问题从大规模归结到小规模，当小规模得到解决后又把小规模的结果回溯，从而退出大规模的解。 （2）上楼梯问题 设计思路：通过反向分析法考虑到第n阶有两种情况：从第n-1阶到第n阶；从第n-2阶到第n阶。记n阶台阶的走法数为f(n),则f(n)=1 n=1;2 n=2;f(n-1)+f(n-2) n2 分析：反向分析法和递归设计一样，就是找出大规模问题与小规模问题之间的关系。 5、分析某一个程序的执行结果包括执行过程（test()） 执行结果：当n=3时：3210---0123 执行过程： test (int n){???? print n;??? ? if( n0)????? ? test(n-1) ;??? else?????? ?? print “---; ??? print n } 四、证明题 1、证明时间复杂度的线性/非线性。 假设n=2^k，有迭代方程T(n)=2T(n/2)+2，计算O（n）。 T(n)=2T(n/2)+2=2(T(n/2^2)+2)+2=4+n/2^2+4+2=4(2T(n/2^3)+2)+4+2