资源描述：
《华南农业大学算法设计与分析期末试卷a卷完整含答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、华南农业大学期末考试试卷（A卷）2010学年第二学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟线订装学号姓名年级专业题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1、渐进算法分析是指（）。B（A）算法在最佳情况、最差情况和平均情况下的代价（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间（D）在最小输入规模下算法的资源代价2、下列算法中通常以自底向上的方式求解最优
2、解的是（）。B（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法3、n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下（）说法不正确？AA．让水桶大的人先打水，可以使得每个人排队时间之和最小B．让水桶小的人先打水，可以使得每个人排队时间之和最小C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样4、设有n个活动的集合s={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在
3、同一时间内只有一个活动能使用这一资源。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)n
4、m（C）O(m*2)（D）O(n*2)6、关于回溯算法和分支限界法，以下（）是不正确描述。A（A）回溯法中，每个活结点只有一次机会成为扩展结点1（B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中（C）回溯法采用深度优先的结点生成策略（D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略7、考虑背包问题：n=6，物品重量W=(1,5,2,3,6,1），价值P=(15,59,21,30,
5、60,5)，背包载重线订装量C＝10。能放进背包的物品价值最大为（）。C（A）101（B）110（C）115（D）1208、分派问题一般陈述如下：给n个人分派n件工作，把工作j分派给第i个人的成本为cost(i，j)，1≤i，j≤n，要求在给每个人分派一件工作的情况下使得总成本最小。此问题的解可表示成n元组（X1，…，Xn），其中Xi是给第i个人分配的工作号，且Xi≠Xj（i≠j）。此解空间的状态空间树被称为（）。A（A）排列树（B）子集树（C）宽度优先生成树（D）深度优先生成树9、当输入规模为n时，算法增长
6、率最小的是（）。B（A）100n（B）10log2n（C）2n（D）3nlog2n10、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。D（A）随机选择一个元素作为划分基准（B）取子序列的第一个元素作为划分基准（C）用中位数的中位数方法寻找划分基准（D）以上皆可行。但不同方法，算法复杂度上界可能不同二、应用题（本大题共5小题，每小题6分，共30分）1、对于以下程序段，分析其最坏时间复杂度。intF(intn){if(n==0)re
7、turn1;elsereturnF(n-1)*n;}解：T(n)=T(n-1)+1n=0T(n)=T(n-1)+1n>0得T（n）＝O（n）2、将下列复杂性函数按照渐进阶从低到高排序。nn2n323lognn!nlognnn1032nnn解：10lognnlognn23n!n23、请画出0-1背包问题采用回溯搜索法的解空间树。解：线订装4、有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物
8、品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？解：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。j5、最大子段和问题：给定由n个整数（
