算法设计与分析复习试题

一、选择题（5题/3分，总15分）循环赛日程表问题的相关叙述。每个人与n-1个选手比赛，每天只能比赛一场，比赛一共进行n-1天算法运行时所需要占用的存储空间有？算法本身占有的存储空间，输入输出占有的数据，运行时辅助变量占有的存储空间。动态规划法的求解步骤分析最优解得性质，规划定义最优值，从底向上计算最优值。解空间树是排列树的问题有。皇后问题，旅行商问题，批处理作业调度问题，圆排列问题，电路板排列问题。分治法的步骤分解治理（求解各个子问题）合并就会场安排问题，贪心法的最佳贪心策略每次从剩下未安排的会议中选择开始时间最早的会议安排。每次从剩下的未安排的中选择时间最短的会议安排。选择最早结束时间。快速排序法基准元素的选取方法第一个元素，中间位置的元素，取最后一个元素，三者取中原则，取位于lowhigh之间的随机数k。满足满m叉树的问题有？n皇后问题，图的m着色问题，最小重量机器设计问题。分支限界法的解题步骤定义问题的解空间，确定问题解空间的组织结构，收索解空间。事前分析法相关的影响因素有算法本身，问题规模，输入序列用分治法求解的问题一般需要具备一些特征，主要有？问题的规模缩小到一定程度就可以轻易解决，问题可以分为若干规模较小的相同子问题，问题分解的子问题相互独立，子问题不包含公共的子问题。二、填空题（5题/3分，总15分）1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n元组。3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。4．一个正在生成孩子的结点称为扩展结点。5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。7．一个自身已生成但其孩子还没有全部生成的结点称为活结点8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。10．分支限界法采用的是宽度优先搜索。11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法12．一个所有孩子已经生成的结点称做死结点13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。三、判断题（10题/2分，总20分）1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。Y2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采用自底向上的递归，由子问题的解得到原问题的解。Y3．贪心法可以理解为以逐步的局部最优，达到最终的全局最优，而且不一定能达到全局最优。Y4．子集树中的所有非叶子结点均有左右两个分支，左分支为1，右分支为0。Y5．回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。Y6．最长公共子序列问题具有最优子结构性质。）Y7．凸多边形最优三角剖分问题具有最优子结构性质。Y8．时间复杂性是对算法运行时间的长短的度量。N9．贪心法是根据贪心策略来逐步构造问题的解，该算法的好坏关键在于正确地选择贪心策略。Y10．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。Y11．子集树的深度等于问题的规模Y12．隐约束也叫剪枝函数，一般有两种：约束条件和限界条件。Y13．加工顺序问题具有最优子结构性质。Y14．包含元素最多的公共子序列即为最长公共子序列。Y15．回溯法问题的解是一个n元组(x1,x2,…,xn)。Y16．子集树中，从根结点到叶子结点的路径表示一个可行解。Y17．针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。Y18．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。Y19．动态规划法与分治法和贪心法类似，都是把待求解的问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。N20．快速排序法通过一趟扫描将待排序的元素分成独立的三个序列。N四、简答题（5题/10分，总50分）1会场安排问题。设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi<ei。如果选择了会议i使用会议室，则它在半开区间[bi,ei)内占用该资源。如果[bi,ei)与[bj,ej)不相交，则称会议i与会议j是相容的。也就是说，当biej或bjei时，会议i与会议j相容。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。设有11个会议等待安排，如下表所示，用贪心法找出满足要求的会议集合（用箭头画出即可）。会议i1234567891011开始时间bi130535688212结束时间ei45678910111213141设G=(V，E)是无向连通带权图，V={1,2,…,6}，如下图所示，根据贪心策略写出用Prim算法求解最小生成树的过程。（1）（2）（3）（4）（5）（6）4.图的m着色问题。给定无向连通图G=(V，E)和3种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。要求有边相连的两个顶点着不同颜色，找出所有不同的着色方法。要求给出最终的搜索树。2．用分治法求解循环赛安排问题。设有4个运动员要进行乒乓球循环赛，现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它3个选手各赛一次；（2）每个选手一天只能比赛一次；（3）循环赛一共需要进行7天。要求：安排4个选手的比赛日程表。4．有7个工件，它们在第一台机器和第二台机器上的处理时间分别为：[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15][t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4]求7个工件的最优加工顺序。要求：用动态规划法按照算法步骤，求出问题的解。（1）N1={1,4,6}，N2={2,3,5,7}（2）将N1中工件按t1i非减序排序N1={1,6,4}，将N2中工件按t2i非增序排序N2={3,7,5,2}（3）N1中工件接N2中工件N1N2={1,6,4,3,7,5,2}。5．布线问题。布线问题就是在N×M的方格阵列中，指定一个方格的中点为a，另一个方格的中点为b，如图所示，问题要求找出a到b的最短布线方案（即最短路径）。布线时只能沿直线或直角，不能走斜线，黑色的单元格代表不可以通过的封锁方格。ab要求给出搜索结果，并构造问题的最优解。5．用优先队列式分支限界法求解0-1背包问题：n=4，W=[3，5，2，1]，v=[9，10，7，4]，C=7。要求给出最终的搜索结果。3用二分查找算法在有序序列（6，12，15，18，22，25，28，35，46，58，60）中查找元素12，画出每次划分的示意图。3.已知待排序序列A=<8，3，2，9，7，1，5，4>，采用合并排序法进行排序，画出合并排序的过程示意图。6.用分支限界法求解旅行商问题。如图所示，n=4，城市1为售货员所在的住地城市，画出最终的搜索树。2．已知某系统在通信联络中只可能出现8种字符，分别为a，b，c，d，e，f，g