算法设计问答题整理.doc

一、问答题（30分）。1什么是最坏情况时间复杂性？什么是平均情况时间复杂性？2什么是递归算法？什么是递归函数？递归算法:直接或间接地调用自身的算法称为递归算法递归函数:用函数自身给出定义的函数称为递归函数3 递归函数的二要素是什么？边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。4 分治法的设计思想是什么？分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之5 什么叫问题的最优子结构性质？矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征6 动态规划基本步骤是什么？ 1.找出最优解的性质，并刻划其结构特征 2.递归地定义最优值 3.以自底向上的方式计算出最优值。 4.根据计算最优值时得到的信息，构造最优解7动态规划算法的基本要素是什么？举例说明一些可以用动态规划算法解决的问题。8说明分治法与动态规划法的相同点和不同之处？9贪心算法的两个重要要素是什么？举例说明一些可以用贪心算法解决的问题。贪心选择性质和最优子结构性质最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。public static float loading(float c, float w, int x) int n=w.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,i); MergeSort.mergeSort(d); float opt=0; for (int i = 0; i n; i+) xi = 0; for (int i = 0; i n & di.w = c; i+) xdi.i = 1; opt+=di.w; c -= di.w; return opt; 10 什么叫贪心选择性质？所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到11 贪心算法与动态规划算法的的相同点和不同之处？贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。12 背包问题与01背包问题有何区别？ 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： public static float knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; opt+=di.v; c-=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。 13回溯法与分支限界法之间的相同点是什么？不同之处在哪些方面？14分支限界法基本思想是什么？分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 15常用的剪枝函数有哪两类？16约束函数的功能是什么？1