算法设计与分析 期末试卷 A卷(完整含答案).pdf

1 装订线 华南农业大学期末考试试卷华南农业大学期末考试试卷（A 卷卷） 2012 学年第学年第 1 学期学期 考试科目考试科目： 算法设计与分析 考试类型考试类型： （闭卷闭卷）考试考试 考试时间考试时间： 120 分钟 学号 姓名 年级专业 题号题号 一一(20) 二二(25) 三三(16) 四四(24) 五五(15) 总分总分 得分得分 评阅人评阅人 说明： （1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再 写，若空白的位置不够，标注清楚后可以写反面； （2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条 理清晰，思想简洁，勿长篇累述不得要领。 得分 一一、填空题填空题（13题题每空每空1分分，第第4题题每每空空2分分，共共20分分，结果直接填于划线处结果直接填于划线处） 1、化简下面f(n)函数的渐进上界表达式。 （5分） n nnf32/)( 2 1 ， 则_)(_)( 1 OnfO 3 2 2)( n nf， 则_)(_)( 2 OnfO 3 3 log)(nnf， 则_)(_)( 3 OnfO 2 log 4 2)( n nf， 则_)(_)( 4 OnfO n nf3log)( 5 ， 则_)(_)( 5 OnfO 参考解答参考解答：)3()( 1 n OnfO；)2()( 2 n OnfO；)(log)( 3 nOnfO； )()( 2 4 nOnfO；)()( 5 nOnfO。 2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。 （3分） 算法1：O( )； 算法2：O( )； 算法算法 2 Loop2(n) s=0; for(i=1;ix，将y插入堆中并重新整合成最小堆和形成新的堆顶元素x；否则丢弃y。当后续n-i个 元素全部比较完毕，则最小堆中的i个元素即为原序列n个数中最大的i个数，最后对这堆中 的i个数调用i次extract_Min过程即可有序输出。 请分析A、B、C、D和E这五个算法在最坏情况下的渐进时间复杂性（用n和i表示，但 需化简，即忽略系数且略去低阶项） 。 算法A：_)(_)(OnTA； 算法B：_)(_)(OnTB； 算法C：_)(_)(OnTC； 算法D：_)(_)(OnTD； 算法E：_)(_)(OnTE。 参考解答参考解答：算法A： )()(niOnTA； )log()(innOnTB或)log()(nnOnTB )log()(ninOnTC，其中建立堆需要 )(nO，i 次堆顶元素删除)log(niO。 算法算法 3 Loop3(n) s=0; for(i=1;i0) b+=ai; else b=ai; if(bsum) sum=b; return sum; 7 装订线 int MaxSum2(int m, int n, int *a) /求解二维整数数组的最大子矩阵和 int sum=0; int *b=new intn; for(int i=0;isum) sum = max; return sum; (4) (5) 参考解答参考解答： (4) bk+=ajk; (5) MaxSum(n,b); 3、 “子集和问题”是求解：n个元素的整数集合，是否能找到一个子集，使得子集元素之和 为c。其回溯搜索算法框架Backtrack( )如下，请补充完整。 void Backtrack(int i) /子集树的搜索算法，根节点，i=1 if(in) /搜索到子集树的叶子 if (cw = c) found=1; /cw 为当前的子集之和，found 已被初始化为 false else found=0; /found 是一个寻找标志，找到则为 true，否则为 false return; if(found=0) /无条件左子树 xi = 1; cw += ai; Backtrack(i+1); (6) ; /搜索完左子树，无条件右子树 xi = 0; (7) ; (6) (7) 参考解答参考解答： (6) cw -= ai; (7) Backtrack(i+1); 4、 “n皇后问题”是求解：nn的棋盘上放置n个不同行不同列不同斜线的皇后，是否有放 置方案，有请输出可行的放置方案数。其算法框架nQueen( )如下，请补充完整。 int nQueen() /假定 n,sum,x数组等都为全局变量，并在 nQueen 中初始化； 8 sum=0; for(int i=1; in) /搜索到 n 叉树的叶子 sum+; /sum 为可行放置方案个数的统计变量 /并输出 x解向量,此处略 else for(int i=1; i=w1 else m1xy=0; for(i=2;i=wi else mixy = (12) ; return mncd; (11) (12) 参考解答参考解答： (11) mixy = mi-1 x-wi y-bi + vi; (12) mixy = mi-1xy; 得分 五五、算法设计算法设计题题（共共2小题小题，共共15分分） 此大题请写出算法设计的详细步骤，可用伪代码、文字、图表来描述。 1、 【、 【区间相交问题区间相交问题】 （7分） 给定数轴上n个区间。去掉尽可能少的区间，使剩下的区间都不相交。请给出删除区间的方 案。 （这里：两区间仅边界有交点不算相交） 参考解答参考解答：区间相交问题基本等同于活动安排问题。 1） 、将区间按照区间后端点排序（从小到大） 。 2） 、选择第一个区间 3） 、依次扫描后续区间，和第一个不相交的，拉入相容区间集合 4） 、总区间数减去相容区间集合得到的就是最少的需要去掉的区间数 评分准则： 1) 答到贪心算法，且贪心算法表述正确，本题即可得满分； 2) 说明用到贪心算法，但表述不正确或含糊，扣2分以上； 3) 未提及贪心算法，但有解题思路，若错误，扣一大半分数，若正确，扣一半，因为贪心算法在这个问题中求解的效 率最高； 10 其它情况酌情考虑。 2、 【、 【最长上升子序列问题最长上升子序列问题】 （8分） 对于给定的一个序列100001),.,( 21 Naaa N 。我们可以得到一些递增上升的子序列。比 如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序 列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：对于给定的序列，求出最长上升子 序列的长度。要求写出算法思想和递推公式，并分析算法时间复杂度。 参考解答参考解答：设f(i)表示：从左向右扫描过来直到以ai元素结尾的序列，获得的最长上升子序列的长度，且子序列包含 ai元素（1in） 。 11 ( )max ( ) 1: ;11 11;(1) i f if ja ia jjii ijjia ia j 当 ,都有 即，f(i)是从f(1), f(2),f(i-1)中找最大的一个值，再加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 2 6 3 1