资源描述
一、填空题（10x2分=20分）1. 算法复杂性依赖于（）、（）、（）。2. 递归的两个基本要素包括初始值和递归关系。3. 用贪心算法求解的问题一般具有两个重要性质（）和（）。4. 背包问题和01背包问题中，可以用贪心算法求解的问题是（）。5. 含有n个顶点的连通图的生成树含有（）条边。6. 状态空间树的搜索方法主要包括深度优先搜索、广度优先搜索和（）搜索。7. 所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为（），通常有（）个叶子结点，遍历此空间树需要（）的计算时间。8. 分支限界法中，通常以（）作为活结点表的数据结构。9. 最小优先队列分支限界法中，优先值较（）的结点优先级较高，通常用（）实现，体现（）的原则。10. NP问题的英文全称是（）。二、名词解释（5x5分=25分）1算法复杂性表示中O、0的含义2备忘录方法3. 状态空间树的广度优先展开方法4. P类判定问题5. NP完全问题三、算法设计、分析（5x5分=25分）1. 设a0:n-1是已排序的数组，请改写二分搜索算法，使要搜索的元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素X在数组中时，i和j相同，均为x在数组中的位置。2. 设序列X，x,x,x和Y，y,y,y的最长公共子序列为12m12nZ，z,z，,z，试说明最长公共子序列问题的最优子结构性质。12k3. 对于下图所示的带权图，给出按照Prim算法构造其最小生成树的过程。4. n皇后问题的回溯算法中，用（x,x,x）表示解向量，其中，x表示第i12ni个皇后的列号，试分析其空间树的表示形式及其约束条件。5. 对于如下图所示的TSP问题，使用优先队列式分支限界法进行求解，试构造出描述其搜索过程的状态空间树，并说明活结点表的变化情况。四、分析说明题（6x5分=30分）1. 分析说明分治法与动态规划法的联系与区别。2. 给出01背包问题的形式化描述。3. 说明动态规划算法与贪心算法的联系与区别。4. 说明回溯法解决问题的一般步骤。5. 01背包问题的回溯算法中，其右子树中解的上界是如何确定的？分析说明分支限界法中活结点表的两种组织形式及其特点。
展开阅读全文