算法设计与分析习题课 一.填空题 1.算法的复杂性有 复杂性和 复杂性之分。 2.快速排序算法是基于 的一种排序算法。 3.适用于贪心算法求解的问题一般具有两个特性： 和 ，其中 是运用该算法解决问题的核心。 4.贪心算法和动态规划算法的主要区别在于 。 5.分析 0/1 背包问题时，可使用贪心法、动态规划法和回溯法，其中需要对数据 进行事先排序的是 和 ；不需要排序的是 。 6. 能 够 运 用 动 态 规 划 算 法 实 现 设 计 的 问 题 需 具 备 两 个 要 素 ， 分 别 是 和 7. 是 。 算 法 具 有 5 个 特 征 ， 分 别 、 、 、 。 、 8.算法按计算时间可以分为 和 ；多项式时间算法 的渐近时间复杂度之间的关系为 。 二．选择题 1．二分搜索算法是利用（ ）实现的算法。 A.分治策略 B.动态规划法 C.贪心法 D.回溯法 2. 贪心算法的基本要素的是（ ）。 A.重叠子问题 B.构造最优解 C.贪心选择性质 D.定义最优解 3. 为避免无效搜索，在回溯算法中采用哪种函数（ ）。 A.递归函数 B.剪枝函数 C.随机数函数 D.搜索函数 4. 贪心算法与动态规划算法的共同点是（ ）。 A.重叠子问题 B.构造最优解 C.贪心选择性质 D.最优子结构性质 5. 使用分治法求解不需要满足的条件是（ ）。 A.子问题必须是一样的 B.子问题不能够重复 

C.子问题的解可以合并 D.原问题和子问题使用相同的方法解 6. 下面不能使用贪心法解决的是（ ）。 A.单源最短路径问题 B.N 皇后问题 C.最小代价生成树问题 D.背包问题 7. 以深度优先方式系统搜索问题解的算法是( )。 A.分枝界限算法 B.概率算法 C.贪心算法 D.回溯算法 8. 回溯法的效率不依赖于下列哪些因素（ ） A.满足显约束的值的个数 B.计算约束函数的时间 C.计算限界函数的时间 D.确定解空间的时间 9. 矩阵连乘问题的算法可用（ ）设计解决。 A.分治策略 B.动态规划法 C.贪心算法 D.回溯算法 10.实现合并排序可用的算法是( )。 A.分治策略 B.动态规划法 C.贪心算法 D.回溯算法 三.简答题 1.简述分治法的基本思想。 2.设计动态规划算法的主要步骤是什么? 3.简述回溯算法的基本思想。 4.简述分枝限界算法的基本思想。 四．分析题 如图 1 所示为 4-皇后问题解空间的树结构，结点可按深度优先检索编号。 试运用回溯法来说明，如何从根结点沿路径一直找到答案结点 31 所进行的回溯 分析步骤，并用图示的方式来表示这一过程。 

图 1 4-皇后问题解空间的树结构 五．计算题 (1)运用上述解决背包问题的算法，求以下背包问题的最优解： n=3，背包容量 M=6，各物品的产生的效益值(P1，P2，P3 )=(1， 2，5)，各物品的重量为(W1，W2，W3)=(2，3，4)，运用贪心法 求解背包的最佳效益值，及其相应各物品的 (X1，X2，X3)值。（其 中 0≤Xi≤1） (2)若将问题(2)转化为 0/1 背包问题，即 Xi 只能取 0 或 1，其余条 件均与(2)相同。可由式 fi(X)=max{fi-1(X),fi-1(X-wi)+Pi}，从前向 后不断递推求出 f1，f2，f3 在 X 相应取值范围内的值。试写出每 个 fi 阶跃点的序偶集合 Si，并求在 M=6 的情况下最优决策序列 (X1，X2，X3)的值。 六．分析题 

设有子集和数问题的实例 W=（w0,w1,w2,w3,w4,w5,w6）= （5,7,10,12,15,18,20）和 M=35。求 W 中元素之和等于 M 的所有 子集。画出对于这一实例由 SumOfSub 算法实际生成的那部分状 态空间树。 七.计算题 运用多段图的动态规划法，对图 2 运用多段图的向前处理法或向 后处理法求解由源点 s 到汇点 t 的一条最小成本路径及相应的成 本。 图 2 一个 5 段图 八.计算题 在图 3 所示的有向图中，运用迪杰斯特拉算法，求得按长度非降次序排列的由结 点 1 到其它结点的最短路径长度。 1 30 10 10 2 50 100 5 60 3 4 20 图 3 有向图