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

1华南农业大学期末考试试卷（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。2（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、对于0－1背包问题和背包问题的解法，下面C答案解释正确。（A）0－1背包问题和背包问题都可用贪心算法求解（B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解（C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解（D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解11、关于回溯搜索法的介绍，下面D是不正确描述。（A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法（C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯（D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径改：树结构回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结3点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。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、一个直接或间接调用自身的算法称为递归算法。4出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相等。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（1），在最坏情况下，搜索的时间复杂性为O（logn（或n2log））。4、动态规划算法的基本要素是最优子结构性质和子问题重叠性质。5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6、贪心算法的基本要素是贪心选择性质和最优子结构性质。三、简答题（32分，五题任选四题，每题8分）1、有4个矩阵},,,{421AAA，连乘积为421AAA。其中iA与1iA是可乘的，321,,i。在这个四矩阵连乘积问题中，不同子问题的个数为4＋C(4,2)＝10个。请写出这10个子问题．．．。A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n个C(n,2)个2、最大子段和问题：问题描述：给定由n个整数（其中可能有负数）组成的序列naaa,,,21，求该序列形如jikka的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：5}max,max{jikknjia10动态规划解决方案：记njiajbjikkji11,}{max][，则对于n个整数序列的最大子段和问题，][maxjbnj1即为所求。动态规划递归式：njjajajbjajb11110]}[],[][max{]}[,max{][问：对于实例：（621aaa,,,）＝（－2，11，－4，13，－5，－2），按照前述动态规划递归式填充b数组，算法运行完毕后，请写出b．数组中的数值．．．．．．，和最大子段．．．．和的值．．．。a1a2a3a4a5a6－211－413－5－2ab1b2b3b4b5b60117201513b最大子段和值：201][maxjbnj3、对于如下描述的背包问题，请计算最终装入背包的最大价值．．．．和．以及各个物品装入．．．．．．背包的数量．．．．．。背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物6品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个符号（即n＝4）时，解空间树．．．．的形状。＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－5、在最接近点对问题中，用一条垂直线L：x=m将平面点集分为大致相等的两个子集S1和S2。设P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，d1和d2分别是S1和S2中最小距离，且设d=min{d1,d2}。++-++---+-7对于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个点，则：222223625)3/2()2/())()(())()((dddvyuyvxuxdistance(u,v)≤5d/6d。这与d的意义相矛盾。即，矩形R中最多只有6个S中的点。上图b中就是矩形R中恰有6个S中的点的极端情形。四、算法设计题（18分，五题任选三题，每题6分）1、【主油管最佳位置】（6分）Olay教授正在为一家石油公司咨询，该公司正在计划建造一条由东向西的石油主管道，该管道要穿过一片有n口井的油田，从每口井中都有一条喷油管沿最短路径与主管道直接相连（喷油管道为南北方向）。给定各个井的X坐标和Y坐标，Olay教授要如何才能选择最佳主管道的位置（即：使各喷油管长度之和最小）？8喷油管主油管参考解答：这是中位数的应用问题。在顺序统计的问题中，中位数的应用最广，例如在X轴上有n个点，由左到右依次排列为X1，X2，…，Xn。XX1X2…Xn-1Xn我们希望在x轴上寻找一点Xp，使得Xp与各点距离之和nipiXXd1)(最小。这个问题可以归结为中位数问题。即：当n为奇数时，Xp为1)/2(nX，否则，Xp为2/)X(X1n/2n/2。从这个例子出发，本题求主油管道的问题也是类似的。由于主管道由东向西，因此，要使连接油井和主油管道的喷井管道最短，喷井管道必须南北走向，与主管道垂直，即主管道的最优位置应为一条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坐标的中位数。评分准则：1)答到求n个油井Y坐标的中位数，本题即可得满分；92)仅说明求中位数，但未提到是对Y坐标求取，扣2分；3)其它情况酌情考虑。2、【特殊的0-1背包问题】（6分）在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明．．．．算法的正确性）参考解