A.该问题的规模缩小到一定的程度就可以容易地解决
B.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
C.利用该问题分解出的子问题的解不可以合并为该问题的解
D.原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
此题为判断题(对，错)。
求解整数规划问题，可以通过先求解无整数约束的松弛问题最优解，然后对该最优解取整求得原整数规划的最优解
采用动态规划策略解决问题的显著特征是满足最优性原理，其含义是(50)。
A．当前所做出的决策不会影响后面的决策
B．原问题的最优解包含其子问题的最优解
C．问题可以找到最优解，但利用贪心法不能找到最优解
D．每次决策必须是当前看来最优的决策才可以找到最优解
采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是______。
A．当前所做出的决策不会影响后面的决策
B．原问题的最优解包含其子问题的最优解
C．问题可以找到最优解，但利用贪心法不能找到最优解
D．每次决策必须是当前看来最优的决策才可以找到最优解
A．
B．
C．
D．
算法设计与分析试题A及答案一填空题：（每题4分，共20分）1. 算法是指（解决问题的）一种方法或一个过程，是（若干指令的）有穷序列。2程序是（算法用某种程序设计语言的）具体实现。程序可以不满足算法的（有限性）性质。3. 贪心选择性质是指所求问题的 整体最优解 可以通过一系列 局部最优的选择 来达到。4递归函数的两大基本要素是_递归方程 和 边界条件_ .5在回溯法中，一个问题的解空间是指一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间.二简答题：（每题5分，共20分）1. 简述分治法所能解决的问题一般应具有的特征。1.)该问题的规模缩小到一定的程度就可以容易地解决；2.)该问题具有最优子结构性质；3.)利用该问题分解出的子问题的解可以合并为该问题的解；4.)该问题所分解出的各个子问题是相互独立的 。2设有待安排的8个活动的开始时间和结束时间如下表。请采用贪心算法给出活动安排序列，要求安排尽可能多的活动。i 12345678Si4510 28571fi6715410993解：将待安排的8个活动的开始时间和结束时间按结束时间的非减序排列如下：i 12345678Si124557810fi3467991015用贪心算法给出活动安排序列：1，3，6，8。贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。3请描述分治法的具体过程。 将原问题划分成k个子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。4. Fibonacci数列如下定义： 1、 请设计一个递归算法，计算F(n)。2、 分析算法的时间复杂性。解 1、int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 2、T(n)=T(n-1)+T(n-2)。三算法分析解答题：（每小题20分,共60分）1考虑金钱兑换问题：有一个货币系统，它有n种硬币，它们的面值为v1,v2,vn，其中 v1=1. 我们想这样来兑换价值为y的钱，要让硬币的数目最少。更形式地，我们要让下面的量 在约束条件 下达到最小. 其中x1, x2, , xn是非负整数.1) 用贪心算法求解该问题；2) 如果硬币的面值有1分，5分，7分和11分，给出反例说明用贪心算法并不总是有效的。1) 贪心伪代码为：Greedy_exchange ( int v, int y, int num, int n) int i=0；for( i=0;i0) numi=y/vi; y=y % numi+； return num;2) 反例：假如要给顾客找15分钱，按照上述贪心策略，则应将15分分解为：11分+1分+1分+1分+1分。而事实上15分可分解为：5分+5分+5分。显然后者的张数更少。2. 假设有n(nN且n1)个硬币，已知其中有一个是假币且假币较真币轻. 请设计分治算法求解该问题.并给出其复杂度分析.Feit_money(low, high) / 假定伪币较真币轻 float mid; if ( high-low=1 ) if (AlowAhigh) return Ahigh; else mid=(low+high)/2; if (high-low+1)%2)=0 sum1=sum(low, mid); sum2=sum(mid+1, high); else sum1=sum(low, mid-1); sum2=sum(mid+1, high); if sum1=sum2 return Amid;else if (sum1sum2) (high-low+1)%2=0? Feit_money(low, mid) : Feit_money(low, mid-1); else Feit_money(mid+1, high); return 0; /其时间复杂度为：O(log n).3. 设序列是序列和的最长公共子序列。a) 请说明最长公共子序列具有最优子结构性质。b) cij记录序列i和的最长公共子序列的长度。由最长公共子序列问题的最优子结构性质建立子问题最优值cij的递归关系。c) 写出寻找最长公共子序列的算法。解 a、设Xm=x1,x2,xm和Yn=y1,y2,yn的最长公共子序列为Zk=z1,z2,zk ，则(1)若xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xmyn且zkxm，那么Zk是Xm-1和Yn的最长公共子序列。(3)若xmyn且zkyn，那么Zk是Xm和Yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 b、当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下： c、void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);算法设计与分析试卷B与解答一填空题：（每题4分，共20分）1. 算法的特性有 0至多个输入， 至少一个输出， 指令无歧义性，指令条数有限且每条指令执行时间有限 .2直接或间接地调用自身的算法称为 递归 算法。用函数自身给出定义的函数称为 递归 函数。3在回溯法中，为了避免无效的搜索，通常采用两种剪枝策略，分别为约束剪枝 和限界剪枝4算法的复杂性是指 算法运行所需要的 计算机资源. 算法的时间复杂性T(n) 是指算法 所需要的时间资源的量；其中n是问题的规模。5动态规划算法的两大基本要素分别为 最优子结构性质和子问题的重叠性质二简答题：（每小题5分，共20分）1. 给定2个序列和，说明X和Y的最长公共子序列问题具有最优子结构性质。 设序列Xm=x1,x2,xm和Yn=y1,y2,yn的最长公共子序列为Zk=z1,z2,zk ，则(1)若xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xmyn且zkxm，那么Zk是Xm-1和Yn的最长公共子序列。(3)若xmyn且zkyn，那么Zk是Xm和Yn-1的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2. 简述常见的两种分支限界法。 （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。3. 假设以加法和乘法为关键操作，估算下述n 次多项式求值函数的时间复杂度（取T为整型） template T PolyEval(T coeff, int n, const T& x) / 计算 n 次多项式的值， coeff0:n 为多项式的系数 T y=1, value=coeff0; for(i=1;i=n;i+) y*=x; value+=y*coeffi; return value; 解答： T PolyEval(T coeff, int n, const T& x) / 计算 n 次多项式的值， coeff0:n 为多项式的系数 T y=1, value=coeff0; for(i=1;i=n;i+) /n 循环 / 累加下一项 y*=x; /一次乘法 value+=y*coeffi; /一次加法和一次乘法 return value; / 3n 次基本操作4. 动态规划算法的基本思想是什么？ 它和分治法有什么区别和联系？ 答：动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复
分治法也许是使用最广泛的算法设计方法，以下关于分治法的结论中正确的是(54)。
A．分治法能解决动态规划方法所能解决的任何问题
B．分治法找到的问题的解一定是最优解
C．用分治法能求出任何问题的解
D．分治法只能把大问题简单分解成一些较小的问题
采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是(52)。
A．当前所做出的决策不会影响后面的决策
B．原问题的最优解包含其子问题的最优解
C．问题可以找到最优解，但利用贪心法不能找到最优解
D．每次决策必须是当前看来最优的决策才可以找到最优解
已知初始问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。这是知识表示法叫（）
使用分治法求解不需要满足的条件是（）。