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

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