算法设计与分析复习试题.docVIP

一 、选择题（5题/3分，总15分） 循环赛日程表问题的相关叙述。 每个人与n-1个选手比赛，每天只能比赛一场，比赛一共进行n-1天 算法运行时所需要占用的存储空间有？ 算法本身占有的存储空间，输入输出占有的数据，运行时辅助变量占有的存储空间。 动态规划法的求解步骤 分析最优解得性质，规划定义最优值，从底向上计算最优值。 解空间树是排列树的问题有。 皇后问题，旅行商问题，批处理作业调度问题，圆排列问题，电路板排列问题。 分治法的步骤 分解治理（求解各个子问题）合并 就会场安排问题，贪心法的最佳贪心策略 每次从剩下未安排的会议中选择开始时间最早的会议安排。每次从剩下的未安排的中选择时间最短的会议安排。选择最早结束时间。 快速排序法基准元素的选取方法 第一个元素，中间位置的元素，取最后一个元素，三者取中原则，取位于low high之间的随机数k。 满足满m叉树的问题有？ n皇后问题，图的m着色问题，最小重量机器设计问题。 分支限界法的解题步骤 定义问题的解空间，确定问题解空间的组织结构，收索解空间。 事前分析法相关的影响因素有 算法本身，问题规模，输入序列 用分治法求解的问题一般需要具备一些特征，主要有？ 问题的规模缩小到一定程度就可以轻易解决， 问题可以分为若干规模较小的相同子问题， 问题分解的子问题相互独立， 子问题不包含公共的子问题。 二、填空题（5题/3分，总15分） 1．给定一个有向带权图 G=(VE)，其中每条边的权是一个非负实数另外给定V中的一个顶点，称为源点现在要计算从源点到所有其各顶点的最短路径长度这里的路径长度是指路径上经过的所有边上的权值之和这个问题通常称为源最短路径问题。（x1,x2,…,xn）当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为一个正在的结点称为扩展结点子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树当所给问题的n个元素中每一个元素均有m选择，要求确定其中的一种选择，使得这n个元素的选择结果组成的向量满足某种性质，即找满足某种特性的n个元素取值的一种组合这类问题的解空间树称为满m叉树一个自身已生成但其还没有全部生成的结点称活结点对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间一个所有已经的结点称做死结点分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，再把子问题分成更小的子问题…直到最后子问题可以简单地直接求解，各个子问题合并原问题的解Y 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题不是相互独立的在求解过程中，将已解决的子问题的进行保存，在需要时可以轻松找出Y 3．贪心法可以理解为以逐步的局部最优，达到最终的全局最优Y 4．子集树中的所有非叶子结点均有左右两个分支，左分支为1，右分支为0。Y 5．回溯法是一种“能进则进，进不了则换，换不了则退”的有哪些信誉好的足球投注网站方法。Y 6．最长公共子序列问题具有最优子结构性质。）Y 7．凸多边形最优三角剖分问题具有最优子结构性质。Y 8．时间复杂性是对算法运行时间的长短的度量。N 9．贪心法是根据贪心策略来逐步构造问题的解该算法的好坏关键在于正确地选择贪心策略Y 10．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为Y 11．子集树的深度等于问题的规模Y 12．隐约束也叫剪枝函数，一般有两种：约束条件和限界条件。Y 13．加工顺序问题具有最优子结构性质。Y 14．包含元素最多的公共子序列即为最长公共子序列。Y 15．回溯法问题的解一个n元组(x1,x2,…,xn)。YY 17．针对问题的可能解有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解Y 18．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 Y设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且biei。如果选择了会议i使用会议室，则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj, ej)不相交，则称会议i与会议j是相容的。也就是说，当biej或bjei时，会议i与会议j相容。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。会议i 1 2 3 4 5 6 7 8 9 10 11 开始时间bi 1 3 0 5 3 5 6