2004算法试题B.docVIP

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