华南农业大学大三计算机专业算法设计与分析期末试卷及答案

PAGEPAGE6华南农业大学期末考试试卷（A卷）20XX学年第二学期(20xx.6) 考试科目：算法设计与分析（开卷）考试时间：120分钟学号题号一姓名二三年级专业四 总分得分评阅人一、选择题（30分，每题2分）1、一个算法应该包含如下几条性质，除了A 。（A）二义性 （B）有限性 （C） 正确性 可终止性2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。这个算法能在一定的时间和空间资源限制内将问题解决这个算法能在人的反应时间内将问题解决这个算法比其他已知算法都更快地将问题解决（D）A和C3、当输入规模为n时，算法增长率最小的是 B 。3（A）5n （B）20log2n （C）2n2 （D）3nlogn34、渐进算法分析是指 B 。算法在最佳情况、最差情况和平均情况下的代价当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析数据结构所占用的空间在最小输入规模下算法的资源代价5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C（A）大O表示法 （B）大Ω表示法（C）Θ表示法 （D）小o表示法6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下顺序搜索法分析正确的是 B 。最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同最佳情况的渐进代价要好于最差情况和平均情况的渐进代价最佳情况和平均情况的渐进代价要好于最差情况的渐进代价7、递归通常用 C 来实现。（A）有序的线性表 （B）队列 （C）栈 （D）数组8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 C问题规模相同，问题性质相同问题规模相同，问题性质不同问题规模不同，问题性质相同问题规模不同，问题性质不同9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个素进行划分，如何选择划分基准？下面 D 答案解释最合理。随机选择一个元素作为划分基准取子序列的第一个元素作为划分基准用中位数的中位数方法寻找划分基准以上皆可行。但不同方法，算法复杂度上界可能不同10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。0－1背包问题和背包问题都可用贪心算法求解0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解0－1包问题则可以用贪心算法求解0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解、关于回溯搜索法的介绍，下面 D是不正确描述。回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解回溯法是一种既带系统性又带有跳跃性的搜索算法改：树结构回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。12、关于回溯算法和分支限界法，以下 A是不正确描述。回溯法中，每个活结点只有一次机会成为扩展结点儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中回溯法采用深度优先的结点生成策略分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略13、优先队列通常用以下 B数据结构来实现。栈堆队列二叉查找树14、在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常分类，以下 D 描述最为准确采用FIFO队列的队列式分支限界法采用最小值堆的优先队列式分支限界法采用最大值堆的优先队列式分支限界法以上都常用，针对具体问题可以选择采用其中某种更为合适的方式15、对布线问题，以下C 是不正确描述布线问题的解空间是一个图（这个方案如果存在的话）b法结束条件二、填空题（20分，每空2分）1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此法的复杂性有 时间 复杂性和 空间 复杂性之分。2、一个直接或间接调用自身的算法称为递归 算法。出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，些子问题的规模都大致 相等 。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的间复杂性为（ 1，在最坏情况下，搜索的时间复杂性为（logn （ 或log2n） 。4、动态规划算法的基本要素是最优子结构性质和子问题重叠质 。5“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6、贪心算法的基本要素是贪心选择性质和最优子结构性质。三、简答题（32分，五题任选四题，每题8分）1、有4个矩阵{A,A1 2

,,4

，连乘积为AA1 2

。其中Ai

与Ai1

是可乘的，A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n个C(n,2)个i1,2,A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n个C(n,2)个2、最大子段和问题：问题描述：给定由n个整数（其中可能有负数组成的序列aa,a，求该序列1 2 n形如jakki

的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：max, maxja}1ijn ki[j]maj1ijki

ak

1ijnn个整数序列的最大子段和问题，maxb[j]即为所求。1jnj]jj],j]}

j11j问：对于实例（a,a, ,a）＝（21，13，5，2，按照前述动态1 2 6a规划递归式填充b数组，算法运行完毕后，请写出。aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值：maxb[j]201jn3、对于如下描述的背包问题，请计算最终装入背包的．．．．．。背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。150元/260元/30元千克。采用贪心算法解此背包问题。此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品13，直至将背包装满。21202030千克；物品1全部装入背包，当前背包中价值220元120100元，背包占用40千克，剩余10千克；物品3的1/3250（120元＋10090×1/，50千克（装满。250122031/310千克。4符号三角形的第一行有n“＋”或“－”，以下“+”，2“－”++-++ - - +-++-++ - - +-4个符号（即n＝4）的形状。－－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋5将平面点集分为大致相等的两个子集S2P1P2Ld和d2分别是S1S2中最小距离，且设d=min{d1,d2}。P1pP2q构成全平面点集的最接近点对的候选6证明：鸽笼原理n+1n或两只以上的鸽子。将矩形R的长为2d3d的边26个(d/2)×(2d/3)（a所示R6个S鸽笼原理易知至少有一个(d/2)×(2d/3)2个以上S中的点。设2则：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236distance(u,v)≤5d/6<ddR6SbR6S中的点的极端情形。四、算法设计题（18分，五题任选三题，每题6分）1、【主油管最佳位置】（6分）Olay教授正在为一家石油公司咨询，该公司正在计划建造一条由东向西的石油主管道，该管道要穿过一片有n。给定各个井的X坐标和Y坐标，Olay教授要如何才能选择最佳主管道的位置（使各喷油管长度之和最小）？7PAGEPAGE14喷油管喷油管主油管参考解答：这是中位数的应用问题。在顺序统计的问题中，中位数的应用最广，例如在X轴上有n个点，由左到右依次排列为X1，X2，…，Xn。XXX1X2…Xn-1 Xn我们希望在x轴上寻找一点Xp与各点距离之和i1

d(Xi

X p个问题可以归结为中位数问题。即：当n为奇数时为X ，否则为(X X )/2。(n1)/2 n/2 n/21从这个例子出发，本题求主油管道的问题也是类似的。由于主管道由东向西，因此，要使连接油井和主油管道的喷井管道最短，喷井管道必须南北走向，与主管道垂直，即主管道的最优位置应为一条Y＝YkYk如何确定。为了使Yk与各油井的Y坐标Y1，Y2，…，Yn间的距离和最短，我们将YnYk（(n+1)/2小的Y坐标作为n/2小的Y(n/2+1)小的Y坐标值的平均数作为Yk的值。显然，确定主油管道的最佳位置，实际上就是求n个油井的Y坐标的中位数。评分准则：答到求n个油井Y坐标的中位数，本题即可得满分；仅说明求中位数，但未提到是对Y2分；其它情况酌情考虑。2、【特殊的0-1背包问题】（6分）在0-10-1背包问题，设计一个有效的算法找出最优解（描述你的算法即可，算法的正确性）参考解答：对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。贪心策略如下：首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。评分准则：答到使用贪心算法，并且贪心策略描述清晰，本题即可得满分；仅说明使用贪心算法，但贪心策略描述含糊，扣1～2分；其它情况酌情考虑。3Gray（6分）问题描述：“格雷码”是一个长度为2的n次方的序列，满足：每个元素都是长度为n比特的串序列中无相同元素1个比特不同例如：n=2{00，01，11，10}Gray误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一种构造方法，输入长度序列n，输出格雷码（只要做出一种构造方案即可，格雷码并不唯一）。参考解答：此题也可用分治法解决。当n＝1时，输出格雷码{0,1}当n>1时，格雷码的长度为2n，即共有2n个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。评分准则：（即当仅输出位的格雷码如何处理，本题即可得满分；说明使用分治算法，但漏边界条件，扣1分；其它情况酌情考虑。4、【男女运动员最佳搭配问题】（6分）n人。给定两个n×n的矩阵P和QP[i][j]动员i和女运动员jQ[i][j是女运动员i和男运动员j并不一定等于Q[j][i]。采用回溯法设计一个算法，计算男女运动员最佳搭配的配对法，使得各组男女双方竞赛优势乘积的总和达到最大。对于这个问题，解空间如下：男男1男n女1女…女n男…女1女…女n女1女…女n在这个解空间中采用回溯方法，由于一个男队员只能和一个女队员搭档，反之也同理，因此，对于搜索的第一步选定某男和某女，那么第二个男队员就不能和第一个男队员的女搭档组合，因此，剪去改女队员的分枝。将男女队员的竞赛优势乘积计算出来，然后将各组男女的优势乘积进行相加。找出最大值。评分准则：满分；说明使用回溯算法，但解空间含糊，扣2～3分；其它情况酌情考虑。5、【优美打印问题】（6分）问题描述：考虑在一台打印机上优美地打印一段文章的问题。输入的文章正文是由长度Ln个英文单词构成的序列。我们希望将这段文章分若干行打印出来，1 2 n每行的最大长度为m，且“优美度”的标准如下：如果某一行包含从单词i到单词j，且每两个单词间留一空格，行首无空格，则在行末多余的空格数为：mjij Lkki（这个公式如何得到呢？由于某一行包含单词i到单词一空格因此单词间的空格数为－又由于从第i个单词到第j个单词的长度和为j L ，kki因此行末多余的空格为mjij L 。）kki不同的断行（即切断从单词i到单词j形成一行）度”（即除最后一行的所有行的行末多余空格总和）。计出一个优美的打印出一段有n个单词的文章的方案。参考解答：此题的题目已经指定了动态规划算法，而且算法思路也已较为清晰，所需要做的只是写出状态转移方程和边界设定。ijnr[i]j(mjijn0

k

Lk

(1in)(in1)解题思路提示：由于必须打印完n个单词且每行打印的单词是连续的，因此，我们从第n个单词开始，依次考虑填一个单词（单词n），填两个单词（单词n-1，单词n），……，填n个单词（单词1，单词2，…，单词n）的打印方案。由于单词填入的方式是按单词序号递减的顺序进行的．．．设r[i]——填入单词i到单词n后，所有被填行的行末空格数总和的最小值。显然，r[i]的动态规划递归式可以由以上思路得到。另外，我们专门设置了一张记忆表k[i]（1≤i≤n+1），记下使得r[i]j示填单词i到单词n的最佳方案中，第一行应填单词i到单词j（jk[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]最小，必须使这两个要素。我们可以按自下而上的方式求解，充分利用了重叠子问题。最后求出的r[1]即为最优“优美打印方案”中行末空格数的总和；从单词1出发，顺着记忆表K的指示，可顺序打印出文章的各行。问题和任务：根据以上的算法提示，请写出r[i]的动态规划递归式，并定义递归的边界。20XX学年第一学期 考试科目：算法设计与分析考试类型（开卷） 考试时间：120 分钟学号姓名年级专业题号得分一二三四 总分评阅人一、选择题（302分）1A2D3B4B5C6B7C8C9D10C11D12A13B14D15C二、填空题（202分）1、时间2、递归3、1

空间相等logn（或log2n）4、最优子结构性质5、备忘录方法6、贪心选择性质

子问题重叠性质三、简答题（32分，五题任选四题，每题8分）1、子问题如下所列：A1A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n个C(n,2)个2、aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值：maxb[j]201jn3、物品1的单位重量价值为50元/千克；物品2的单位重量价值为60元/千克；物品3的单位重量价值为30元/千克。采用贪心算法解此背包问题。此时，贪心的策略是：每次选择单位重量价值最大的物品。因此，首先选择物品13，直至将背包装满。21202030千克；物品1全部装入背包，当前背包中价值220元120100元，背包占用40千克，剩余10千克；物品3的1/3250（120元＋10090×1/，50千克（装满。250122031/310千克。4、4个符号（即n＝4）时，解空间树是一棵完全二叉树。－ ＋－ ＋ － ＋－＋ － ＋ － ＋ － ＋－＋－＋－＋－＋－＋－＋－＋－＋5、证明：鸽笼原理n+1n或两只以上的鸽子。将矩形R的长为2d3d的边26个(d/2)×(2d/3)（a所示R6个S鸽笼原理易知至少有一个(d/2)×(2d/3)2个以上S中的点。设2则：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236distance(u,v)≤5d/6<ddR6SbR6S中的点的极端情形。四、算法设计题（18分，五题任选三题，每题6分）1、【主油管最佳位置】（6分）参考解答：这是中位数的应用问题。在顺序统计的问题中，中位数的应用最广，例如在X轴上有n个点，由左到右依次排列为X1，X2，…，Xn。15PAGEPAGE18XXX1X2…Xn-1 Xn我们希望在x轴上寻找一点Xp与各点距离之和i1

d(Xi

X p个问题可以归结为中位数问题。即：当n为奇数时为X ，否则为(X X )/2。(n1)/2 n/2 n/21从这个例子出发，本题求主油管道的问题也是类似的。由于主管道由东向西，因此，要使连接油井和主油管道的喷井管道最短，喷井管道必须南北走向，与主管道垂直，即主管道的最优位置应为一条Y＝YkYk如何确定。为了使Yk与各油井的Y坐标Y1，Y2，…，Yn间的距离和最短，我们将YnYk（(n+1)/2小的Y坐标作为n/2小的Y(n/2+1)小的Y坐标值的平均数作为Yk的值。显然，确定主油管道的最佳位置，实际上就是求n个油井的Y坐标的中位数。评分准则：答到求n个油井Y坐标的中位数，本题即可得满分；仅说明求中位数，但未提到是对Y2分；其它情况酌情考虑。2、【特殊的0-1背包问题】（6分）参考解答：对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。贪心策略如下：首先将各物品依重量递增序（