2005.6算法设计与分析课程期末试卷.doc

华南农业大学期末考试试卷（A卷）2004学年第二学期(2005.6) 考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟学号 姓名 年级专业 题号一二三四总分得分评阅人一、选择题（30分，每题2分）1、一个算法应该包含如下几条性质，除了 A 。（A）二义性（B）有限性（C）正确性（D）可终止性2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。（A）这个算法能在一定的时间和空间资源限制内将问题解决（B）这个算法能在人的反应时间内将问题解决（C）这个算法比其他已知算法都更快地将问题解决（D）A和C3、当输入规模为n时，算法增长率最小的是 B 。（A）5n（B）20log2n（C）2n2（D）3nlog3n4、渐进算法分析是指 B 。（A）算法在最佳情况、最差情况和平均情况下的代价（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间（D）在最小输入规模下算法的资源代价5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？ C （A）大O表示法（B）大表示法（C）表示法（D）小o表示法6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。（A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同（B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价（C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价（D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价7、递归通常用 C 来实现。（A）有序的线性表（B）队列（C）栈（D）数组8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。C（A）问题规模相同，问题性质相同（B）问题规模相同，问题性质不同（C）问题规模不同，问题性质相同（D）问题规模不同，问题性质不同9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。但不同方法，算法复杂度上界可能不同10、对于01背包问题和背包问题的解法，下面 C 答案解释正确。（A）01背包问题和背包问题都可用贪心算法求解（B）01背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解（C）01背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解（D）因为01背包问题不具有最优子结构性质，所以不能用贪心算法求解11、关于回溯搜索法的介绍，下面 D是不正确描述。（A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法（C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯（D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径改：树结构回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。12、关于回溯算法和分支限界法，以下 A 是不正确描述。（A）回溯法中，每个活结点只有一次机会成为扩展结点（B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中（C）回溯法采用深度优先的结点生成策略（D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略13、优先队列通常用以下 B 数据结构来实现。（A）栈（B）堆（C）队列（D）二叉查找树14、在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下 D 描述最为准确（A）采用FIFO队列的队列式分支限界法（B）采用最小值堆的优先队列式分支限界法（C）采用最大值堆的优先队列式分支限界法（D）以上都常用，针对具体问题可以选择采用其中某种更为合适的方式15、对布线问题，以下 C 是不正确描述（A）布线问题的解空间是一个图（B）可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定（C）采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的（D）采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件二、填空题（20分，每空2分）1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间 复杂性和 空间 复杂性之分。2、一个直接或间接调用自身的算法称为 递归 算法。出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相等 。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn（或） ）。4、动态规划算法的基本要素是 最优子结构性质和子问题重叠性质 。5、动态规划算法有一个变形方法 备忘录方法 。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6、贪心算法的基本要素是 贪心选择性质 和最优子结构性质。三、简答题（32分，五题任选四题，每题8分）1、有4个矩阵，连乘积为。其中与是可乘的，。在这个四矩阵连乘积问题中，不同子问题的个数为4C(4,2)10个。请写出这10个子问题。2、最大子段和问题：问题描述：给定由n个整数（其中可能有负数）组成的序列，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：动态规划解决方案：记，则对于n个整数序列的最大子段和问题，即为所求。动态规划递归式：问：对于实例：（）（2，11，4，13，5，2），按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b数组中的数值，和最大子段和的值。最大子段和值：3、对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。背包容量：C50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物品3的单位重量价值为30元/千克。采用贪心算法解此背包问题。此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品2，然后是物品1，最后是物品3，直至将背包装满。 物品2全部装入背包，当前背包中价值120元，背包占用20千克，剩余30千克； 物品1全部装入背包，当前背包中价值220元（120元100元），背包占用40千克，剩余10千克； 物品3的1/3被装入背包，当前背包中价值250元（120元100元90元1/3），背包占用50千克（装满）。因此，最终装入背包的最大价值为250元，物品1和物品2都全部装入，分别是20千克和20千克，物品3装入1/3，是10千克。4、对于符号三角问题，符号三角形的第一行有n个符号。符号可以为“”或“”，以下每一行的符号由上行得到，2个同号下面都是“+”，2个异号下面都是“”。如下图所示（第一行有4个符号的符号三角中的其中的一个）：+ + - + - - +-请画出使用回溯法求解第一行有4个符号（即n4）时，解空间树的形状。5、在最接近点对问题中，用一条垂直线L：x=m将平面点集分为大致相等的两个子集S1和S2。设P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，d1和d2分别是S1和S2中最小距离，且设d=mind1,d2。对于P1中任意一个点p，可能和在P2中点q构成全平面点集的最接近点对的候选点对，请证明：P2中最多有6对这样的候选点对。证明：根据鸽笼原理：如果n+1只鸽子飞入n个笼子中，那么至少有一个笼子里包含两只或两只以上的鸽子。将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则：distance(u,v)5d/61时，格雷码的长度为，即共有个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。评分准则：1) 答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出1位的格雷码如何处理），本题即可得满分；2) 说明使用分治算法，但漏边界条件，扣1分；3) 其它情况酌情考虑。4、【男女运动员最佳搭配问题】（6分）问题描述：羽毛球队有男女运动员各n人。给定两个nn的矩阵P和Q。Pij是男运动员i和女运动员j配合组成混合双打的竞赛优势，Qij是女运动员i和男运动员j配合的竞赛优势。由于技术配合或心理状况等各种因素的影响，Pij并不一定等于Qji。采用回溯法设计一个算法，计算男女运动员最佳搭配的配对法，使得各组男女双方竞赛优势乘积的总和达到最大。对于这个问题，解空间如下：在这个解空间中采用回溯方法，由于一个男队员只能和一个女队员搭档，反之也同理，因此，对于搜索的第一步选定某男和某女，那么第二个男队员就不能和第一个男队员的女搭档组合，因此，剪去改女队员的分枝。将男女队员的竞赛优势乘积计算出来，然后将各组男女的优势乘积进行相加。找出最大值。评分准则：1) 答到使用回溯算法，并且大致写出回溯的解空间树及回溯的方法，本题即可得满分；2) 说明使用回溯算法，但解空间含糊，扣23分；3) 其它情况酌情考虑。5、【优美打印问题】（6分）问题描述：考虑在一台打印机上优美地打印一段文章的问题。输入的文章正文是由长度为L1，L2，Ln的n个英文单词构成的序列。我们希望将这段文章分若干行打印出来，每行的最大长度为m，且“优美度”的标准如下：如果某一行包含从单词i到单词j，且每两个单词间留一空格，行首无空格，则在行末多余的空格数为：（解释：这个公式如何得到呢？由于某一行包含单词i到单词j，且每两个单词间留一空格，因此单词间的空格数为ji，又由于从第i个单词到第j个单词的长度和为，因此行末多余的空格为。）不同的断行（即切断从单词i到单词j形成一行）的方式，将可能产生不同的“优美度”（即除最后一行的所有行的行末多余空格总和）。我们希望除最后一行的所有行中，行末多余空格的总和最小。请用动态规划算法设计出一个优美的打印出一段有n个单词的文章的方案。参考解答：此题的题目已经指定了动态规划算法，而且算法思路也已较为清晰，所需要做的只是写出状态转移方程和边界设定。解题思路提示：由于必须打印完n个单词且每行打印的单词是连续的，因此，我们从第n个单词开始，依次考虑填一个单词（单词n），填两个单词（单词n-1，单词n），填n个单词（单词1，单词2，单词n）的打印方案。由于单词填入的方式是按单词序号递减的顺序进行的，因此填入单词i到单词n后的行末空格数的总和应为当前行的行末空格数加后面行的行末空格数的和。我们的目标是使它最小。设ri 填入单词i到单词n后，所有被填行的行末空格数总和的最小值。显然，ri的动态规划递归式可以由以上思路得到。另外，我们专门设置了一张记忆表ki（1 i n+1），记下使得ri最小的j值，表示填单词i到单词n的最佳方案中，第一行应填单词i到单词j（j即是ki）。r的递归的边界可定义为：rn+10；kn+1n+1；表示不填任何单词时的行末空格数为0。我们从rn+1出发，依次求rn，rn-1，r1。由ri的递归式的由来可以看出，求ri最小值的子问题，包含了求ri+l，rn+l这些子问题。要使ri最小，必须使这些子问题的值最小，因此符合动态规划程序设计要求的“最优子结构”和“重叠子问题”两个要素。我们可以按自下而上的方式求解，充分利用了重叠子问题。最后求出的r1即为最优“优美打印方案”中行末空格数的总和；从单词1出发，顺着记忆表K的指示，可顺序打印出文章的各行。问题和任务：根据以上的算法提示，请写出ri的动态规划递归式，并定义递归的边界。2004学年第一学期 考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟学号 姓名 年级专业 题号一二三四总分得分评阅人一、选择题（30分，每题2分）1A2D3B4B5C6B7C8C9D10C11D12A13B14D15C二、填空题（20分，每空2分）1、时间空间2、递归相等3、1logn（或）4、最优子结构性质子问题重叠性质5、备忘录方法6、贪心选择性质三、简答题（32分，五题任选四题，每题8分）1、子问题如下所列：2、最大子段和值：3、物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物品3的单位重量价值为30元/千克。采用贪心算法解此背包问题。此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品2，然后是物品1，最后是物品3，直至将背包装满。 物品2全部装入背包，当前背包中价值120元，背包占用20千克，剩余30千克； 物品1全部装入背包，当前背包中价值220元（120元100元），背包占用40千克，剩余10千克； 物品3的1/3被装入背包，当前背包中价值250元（120元100元90元1/3），背包占用50千克（装满）。因此，最终装入背包的最大价值为250元，物品1和物品2都全部装入，分别是20千克和20千克，物品3装入1/3，是10千克。4、第一行4个符号（即n4）时，解空间树是一棵完全二叉树。5、证明：根据鸽笼原理：如果n+1只鸽子飞入n个笼子中，那么至少有一个笼子里包含两只或两只以上的鸽子。将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个(d/2)(2d/3