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