华南农业大学算法设计与分析期末试卷A卷完整含答案.pdf

1 装订线 华南农业大学期末考试试卷华南农业大学期末考试试卷（A 卷卷） 2010 学年第学年第二二学期学期 考试科目考试科目： 算法分析与设计算法分析与设计 考试类型考试类型： （闭卷闭卷）考试考试 考试时间考试时间： 120 分钟分钟 学号 姓名 年级专业 题号题号 一一 二二 三三 四四 总分总分 得分得分 评阅人评阅人 注意注意：所有答案请写在答卷上所有答案请写在答卷上，写在试卷上不得分写在试卷上不得分。 一一、选择选择题题（本大题共10小题，每小题2分，共20分） 1、渐进算法分析是指（ ） 。B （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析 （C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 2、下列算法中通常以自底向上的方式求解最优解的是（ ） 。B （A）备忘录法 （B）动态规划法 （C）贪心法 （D）回溯法 3、n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒 定。如下（ ）说法不正确？A A让水桶大的人先打水，可以使得每个人排队时间之和最小 B让水桶小的人先打水，可以使得每个人排队时间之和最小 C让水桶小的人先打水，在某个确定的时间 t 内，可以让尽可能多的人打上水 D若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 4、设有 n 个活动的集合 s=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等， 而在同一时间内只有一个活动能使用这一资源。si, fi 分别为活动 i 的开始时间和结束时间， 活动 i 和 j 相容当且仅当 si= fj 或者 sj= fi。 应怎样对这 n 个活动进行安排才能令最多的活 动可以使用资源？（ ） 。A （A）最早结束的活动优先安排 （B）最先开始的活动优先安排 （C）占用资源时间最少的活动优先安排 （D）占用资源时间最长的活动优先安排 5、已知序列 X=x1,x2,xm，序列 Y=y1,y2,yn，使用动态规划算法求解序列 X 和 Y 的最长公共子序列，其最坏时间复杂度为（ ） 。A （A）O(m * n) （B）O(m + n) （C）O(m * 2n) （D）O(n * 2m) 6、关于回溯算法和分支限界法，以下（ ）是不正确描述。A （A）回溯法中，每个活结点只有一次机会成为扩展结点 2 装订线 （B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些 儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点 表中 （C）回溯法采用深度优先的结点生成策略 （D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略 7、考虑背包问题：n=6，物品重量 W=(1,5,2,3,6,1） ，价值 P=(15,59,21,30,60,5)，背包载重 量 C10。能放进背包的物品价值最大为（ ） 。C （A）101 （B）110 （C）115 （D）120 8、 分派问题一般陈述如下： 给 n 个人分派 n件工作， 把工作 j分派给第 i个人的成本为 cost(i， j)，1i，jn，要求在给每个人分派一件工作的情况下使得总成本最小。此问题的解可表 示成 n 元组（X1，Xn） ，其中 Xi 是给第 i 个人分配的工作号，且 XiXj（ij） 。此 解空间的状态空间树被称为（ ） 。A （A）排列树 （B）子集树 （C）宽度优先生成树 （D）深度优先生成树 9、当输入规模为 n 时，算法增长率最小的是（ ） 。B （A）100n （B）10log2n （C）2n （D）3nlog2n 10、在寻找 n 个元素中第 k 小元素问题中，如快速排序算法思想，运用分治算法对 n 个元 素进行划分，如何选择划分基准？下面（ ）答案解释最合理。D （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 二、应用应用题题（本大题共5小题，每小题6分，共30分） 1、对于以下程序段，分析其最坏时间复杂度。 int F(int n) if (n = 0) return 1; else return F(n-1)*n; 解：T(n) = T(n-1) + 1 n=0 T(n) = T(n-1) + 1 n0 得 T（n）O（n） 2、将下列复杂性函数按照渐进阶从低到高排序。 23 23log!log10 nnn nnnnnn 解： 32 10loglog23! nnn nnnnnn 3 装订线 3、请画出 0-1 背包问题采用回溯搜索法的解空间树。 解： 4、有这样一类特殊 0-1 背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3） ，W=（5，3，2，10，4，8） 。 其中 n 为物品个数，c 为背包载重量，P 表示物品的价值，W 表示物品的重量。请问 对于此 0-1 背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大， 能获得的最大总价值多少？ 解：因为该 01 背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的 物品放进背包。最终可以把重量分别为 2，3，4，5 的三个物品放进背包，得到的价值和为 15 + 8 + 6 + 4 = 33，为最大值。 5、最大子段和问题：给定由n个整数（其中可能有负数）组成的序列，求该序列形如 j ik k a 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最 优值为： max,max j ik k nji a 1 0 动态规划解决方案：记njiajb j ik k ji 1 1 , max，则对于n个整数序列的最大子 段和问题，maxjb nj1 即为所求。 动态规划递归式： njjajajb ja jb 11 110 ,max ,max 问：对于实例： （ 621 aaa,）（12，11，14，3，5，20） ，按照前述动态规划 递归式填充b数组，算法运行完毕后，请写出b数组中的数值数组中的数值以及最大子段和的值最大子段和的值。 解：b=12, 1, 15, 12, 17, -20 最大子段和为17。 4 装订线 三三、程序程序填空题填空题（本大题共10空格，每空2分，共20分。注意：每个空格只填一 个语句） 1、使用回溯法求解 n 皇后问题，xt用于存储第 t 个皇后放置的列号，可直接使用求绝对 值函数 int abs(int x)。 bool Place(int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if ( 2 ) 3 1、 (abs(k-j)=abs(xj-xk)|(xj=xk) 2、 Place(t) 3、 Backtrack(t+1) 2、 矩阵连乘问题， 设p0为矩阵A1的行号， pi为矩阵Ai的列号， mij为计算矩阵Ai:j 相乘所需的最少数乘次数，sij记录矩阵Ai:j相乘的最优断开位置。 void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) 4 for (int r = 2; r = n; r+) 1.5CM 5 装订线 for (int i = 1; i = n - r+1; i+) int j; 5 mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t; 6 if (t mij) mij = t; 7 4、 mii = 0; 5、 j = i+r-1; 6、 t = mik + mk+1j + pi-1*pk*pj; 7、 sij = k; 3、使用归并排序法求逆序对。 int b10000; void copy(int a, int b, int l, int r) int k = l; for(k; k = r; k+) ak = bk; int merge(int a, int b, int left, int m, int right) int i = left, j = m + 1, c = left, count = 0; 6 装订线 while(i = m while(i = m) bc+ = ai+; while(j = right) bc+ = aj+; return count; int mergeSort(int a, int left, int right) int total = 0; if (leftright) /至少有2个元素 int m = (left+right)/2; /取中点 total += mergeSort(a, left, m); total += mergeSort(a,m+1, right); 10 copy(a, b, left, right); /复制回数组a return total; 8、 bc+ = ai+; 9、 count += m - i + 1; 10、 total += merge(a, b, left, m, right); 四四、算法设计算法设计题题（本大题共2小题，每小题15分，共30分） 1、【最长上升子序列问题最长上升子序列问题】 （15 分分） 7 装订线 对于给定的一个序列 12 ( ,) N a aa，11000N。我们可以得到一些递增上升的 子序列 12 (,) iiiK aaa，这里 12 1 K iiiN。比如，对于序列(1, 7, 3, 5, 9, 4, 8)， 有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是 4，比如子序列 (1, 3, 5, 8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设 计的算法思想及递推函数的公式表达。 参考解答参考解答：设( )f i表示：从左向右扫描过来直到以 a i元素结尾的序列，获得的最长 上升子序列的长度，且子序列包含 a i元素（1in ） 。 11 ( )max ( ) 1: ;11 11;(1) i f if ja ia jjii ijjia ia j 当 ,都有 即，( )f i是从(1)f，(2)f到(1)f i中找最大的一个值，再加 1。或者就是 1。 主要是看 ai这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前 已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子 序列，长度为 1。 最后，所要求的整个序列的最长公共子序列长度为 maxf(i): 1=i=n 例如，对于序列：4 2 6 3 1 5 2 i 1 2 3 4 5 6 7 array 4 4 2 2 6 6 3 3 1 1 5 5 2 2 f(i) 1 1 1 1 2 2 2 2 1 1 3 3 2 2 评分准则评分准则： 1) 答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设 定清晰， 本题即可得满分； （阅卷时仔细看递推公式表达， 公式表达含义正确即可， 因其表达形式可能不唯一） 2) 说明使用动态规划算法，但对递推函数表达错误或含糊，扣 2 分以上； 3) 其它情况酌情考虑。 2、 【整数因子分解整数因子分解】 （15 分分） 大于 1 的正整数 n 都可以分解为 n = x1 * x2 * . * xm 例如：当 n=12 时，共有 8 种