数据结构章节练习题及答案10.docx

第10章算法设计策略及应用实例1 .具有什么特征的问题适合用分治策略求解？三个特征：(1) 原问题可以分解成规模较小、相互独立和类型相同的子问题；(2) 子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；(3) 所有子问题的解能够合并成原问题的解。2 .递归算法和迭代算法的区别是什么？递归算法是利用函数直接或者间接调用自身来完成某个计算过 程。为了求解规模为n的问题，设法将它分解成规模较小的问题，并 能从规模较小的解构造出原问题的解。迭代法根据问题规模为i-1的 解，由问题的迭代性质，构造问题规模为i的解，最后得到规模为n 的原问题的解。所以，递归算法是从大到小、从上到下地构造问题的 解，而迭代算法是从小到大、从下到上地构造或者逼近问题的解。3 .具有什么性质的问题适合贪心策略求解？具有如下性质：第一、最优子结构性质；第二、贪心选择性质。4 .具有什么性质的问题适合动态规划策略求解？具有如下性质：第一、最优子结构性质；第二、子问题重叠性质。5 .贪心策略和动态规划策略之间的差异有哪些？两种策略的不同之处在于，贪心策略做出的每步贪心选择都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上 一步的最优解无需保存。动态规划策略的全局最优解一定包括某个局 部最优解，但是不一定包括前一个局部最优解，因此动态规划策略需 要保存之前的所有局部最优解。6 .回溯策略和分支限界策略之间的差异有哪些？回溯策略和分支限界策略的差异表达在以下方面：第一、分支限 界策略没有限制树的搜索方法，可以是广度优先搜索，也可以是最小 本钱搜索，而回溯策略采用的是深度优先搜索；第二、分支限界策略 只能用于优化问题，而回溯策略可以用于非优化问题，例如求问题的 可行解。