2004算法试题A

曲阜师范大学计算机科学学院试题第1页共2页2004级计算机科学与技术、网络工程专业2006—2007学年第一学期《算法设计与分析》期末试题（A卷）一、填空题（10×2分＝20分）1.按照渐近阶从低到高的顺序排列下列表达式：n5254lognnnn!n2/3、、、30、100、、（）2.最优子结构性质的含义是（）。3.流水作业调度问题中，作业,ij不满足Johnson不等式时，交换它们的加工顺序后，加工时间（）（增加、不增加、减少、不减少、不变）。4.动态规划算法通常以（）的方式解各子问题，而贪心算法通常以（）的方式进行迭代。5.优化问题主要由两个部分组成（）和（）。6.贪心算法的核心问题是（）。7.当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为（），通常有（）个叶子结点，遍历此空间树需要（）的计算时间。8.按照活结点表的组织方式的不同，分支限界法包括（）和（）两种形式。9.最大优先队列分支限界法中，优先值较（）的结点优先级较高，通常用（）实现，体现（）的原则。10.问题Q的非确定性算法分为两个阶段（）阶段和（）阶段。二、名词解释（5×5分＝25分）1．渐近复杂性2．备忘录方法3．贪心选择性质4．状态空间树中的活结点、E-结点、死结点5．非确定性算法三、算法设计、分析（5×5分＝25分）1．对任何非零偶数n，总可以找到奇数m和正整数k，使得2knm。为了求出两个n阶矩阵的乘积，可以把一个n阶矩阵分成mm个子矩阵，每个子矩阵有22kk个元素。当需要求22kk的子矩阵的积时，使用Strassen算法（不必写出）。设计一个传统方法与Strassen算法相结合的矩阵相乘曲阜师范大学计算机科学学院试题第2页共2页算法，对任何偶数n，都可以求出两个n阶矩阵的乘积，并分析算法的计算时间复杂性。2．设序列12{,,,}mXxxx和12{,,,}nYyyy的最长公共子序列为12{,,,}kZzzz，试说明最长公共子序列问题的最优子结构性质（不必证明）。3．对于下图所示的有向图，用Dijkstra算法计算从源顶点1到其他顶点间的最短路径，请列表描述出Dijkstra算法的迭代过程。4．n－皇后问题的回溯算法中，用12(,,,)nxxx表示解向量，其中，ix表示第i个皇后的列号，试分析其空间树的表示形式及其约束条件。5．对于如下图所示的TSP问题，使用优先队列式分支限界法进行求解，试构造出描述其搜索过程的状态空间树，并说明活结点表的变化情况。四、分析说明题（6×5分＝30分）1.分析说明分治法与动态规划法的联系与区别。2.在0－1背包问题中，设(,)mij是背包容量为j，可选择物品为,1,,iin时背包问题的最优值，请给出用动态规划算法求解(,)mij的递归定义。3.说明贪心选择性质的证明过程。4.分析说明回溯法与分支限界法之间的联系与区别。5.在求解装载问题的队列式分支限界法中，设bestw是当前最优解，说明为什么要提前更新bestw值？如何更新bestw值？对应的回溯法中，bestw的值是如何处理的？6.列举NP完全问题常用的求解策略。130243206104551234105020103010060