发布时间 : 星期六 文章算法分析与设计复习题及参考答案更新完毕开始阅读13b82668abea998fcc22bcd126fff705cc175cff
忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。 备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 2.简述回溯法解题的主要步骤。 回溯法解题的主要步骤包括： 1）针对所给问题，定义问题的解空间； 2）确定易于搜索的解空间结构； 3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 3.简述动态规划算法求解的基本要素。 动态规划算法求解的基本要素包括： 1）最优子结构是问题能用动态规划算法求解的前提； 2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 4.简述回溯法的基本思想。 回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 将递
归算法转化为非递归算法的方法主要有： 1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2）用递推来实现递归函数。 3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 6.简要分析分支限界法与回溯法的异同。 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标
则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
NIAC如果分别用、和表示算法要解问题的规模、算法的输入和
算法本身，而且用表示复杂性，那么，C=F(N,I,A)应该有。 算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。 8.贪心算法求解的问题主要具有哪些性质？简述之。 贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这
是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。 分治法的基本思想：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 优解为：（1，0，1） 2.按要求完成以下关于排序和查找的问题。 （1） 对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。 （2） 请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 （3） 给出上述算法的递归算法。 （4） 使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。 解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5 第三步：135 32 29 18 27 25 15 5 1 第四步：135 32 29 27 25 18 15 5 1 （2）基本思想：首先将待搜索元素v与数组的中间元 素进行比较，如果，则在前半部分 元素中搜 索v；若，则搜索成功；否则在后半部分数组中搜索v。 非递归算法： 输入：递减数组A[left:right]，待搜索元素v。 输出：v在A中的位置pos，或者不在A中的消息（-1）。 步骤：【3分】 int BinarySearch(int A[],int left,int right,int v) { int mid; while (left<=right) { mid=int((left+right)/2); if (v==A[mid]) return mid; else if (v>A[mid]) right=mid-1; else left=mid+1; } return -1; } （3）递归算法： 输入：递减数组A[left:right]，待搜索元素v。 输出：v在A中的位置pos，或者不在A中的消息（-1）。 步骤： int BinarySearch(int A[],int left,int right,int v) { int mid; if (left<=right) { mid=int((left+right)/2); if (v==A[mid]) return mid; else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);