2004算法试题B

曲阜师范大学计算机科学学院试题第1页共2页2004级计算机科学与技术、网络工程专业2006—2007学年第一学期《算法设计与分析》期末试题（B卷）一、填空题（10×2分＝20分）1.算法复杂性依赖于（）、（）、（）。2.递归的两个基本要素包括（）和（）。3.用贪心算法求解的问题一般具有两个重要性质（）和（）。4.背包问题和0－1背包问题中，可以用贪心算法求解的问题是（）。5.含有n个顶点的连通图的生成树含有（）条边。6.状态空间树的搜索方法主要包括深度优先搜索、广度优先搜索和（）搜索。7.所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为（），通常有（）个叶子结点，遍历此空间树需要（）的计算时间。8.分支限界法中，通常以（）作为活结点表的数据结构。9.最小优先队列分支限界法中，优先值较（）的结点优先级较高，通常用（）实现，体现（）的原则。10.NP问题的英文全称是（）。二、名词解释（5×5分＝25分）1．算法复杂性表示中O、、的含义2．备忘录方法3．状态空间树的广度优先展开方法4．P类判定问题5．NP完全问题三、算法设计、分析（5×5分＝25分）1．设a[0:n-1]是已排序的数组，请改写二分搜索算法，使要搜索的元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。2．设序列12{,,,}mXxxx和12{,,,}nYyyy的最长公共子序列为12{,,,}kZzzz，试说明最长公共子序列问题的最优子结构性质。3．对于下图所示的带权图，给出按照Prim算法构造其最小生成树的过程。曲阜师范大学计算机科学学院试题第2页共2页4．n－皇后问题的回溯算法中，用12(,,,)nxxx表示解向量，其中，ix表示第i个皇后的列号，试分析其空间树的表示形式及其约束条件。5．对于如下图所示的TSP问题，使用优先队列式分支限界法进行求解，试构造出描述其搜索过程的状态空间树，并说明活结点表的变化情况。四、分析说明题（6×5分＝30分）1.分析说明分治法与动态规划法的联系与区别。2.给出0－1背包问题的形式化描述。3.说明动态规划算法与贪心算法的联系与区别。4.说明回溯法解决问题的一般步骤。5.0－1背包问题的回溯算法中，其右子树中解的上界是如何确定的？6.分析说明分支限界法中活结点表的两种组织形式及其特点。13024320610451623456315556642