资源描述：
《(已公布!)算法设计与分析 期末试卷 A卷(完整含答案)2010.12.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、华南农业大学期末考试试卷（A卷）2010学年第一学期考试科目：算法分析与设计考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业线订装题号一二三四总分得分评阅人注意：所有答案请写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）得分1、以下有关NP完全性理论的相关描述，正确的是（）。（A）P问题都是NP问题（B）NP问题指的是不能够在多项式时间内求解的问题（C）P=NP（D）0-1背包问题属于P问题2、voidhanoi(intn,inta,intb,intc){if(n>0
2、){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的时间复杂度为（）。nn（A）O（2）（B）O（nlogn）（C）Θ（n！）（D）Θ（n）3、在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。（A）回溯法1（B）分支限界法（C）回溯法和分支限界法（D）回溯法求解子集树问题4、下列算法中通常以自底向上的方式求解最优解的是（）。线订装（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法5、蒙特卡罗算法是（）的一种。（A）概率算法
3、（B）分支界限算法（C）贪心算法（D）回溯算法6、有n个独立的作业{1,2,..,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）。（A）作业从小到大依次分配给空闲的机器（B）作业从大到小依次分配给空闲的机器（C）每个机器分配一样的作业数（D
4、）使用以上几种贪心策略都能找到最优解，所以都合适7、考虑背包问题：n=6，物品重量W=(1,5,2,3,6,1），价值P=(15,59,21,30,60,5)，背包载重量C＝10。能放进背包的物品价值最大为（）。（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（
5、i≠j）。此解空间的状态空间树被称为（）。（A）排列树（B）子集树2（C）宽度优先生成树（D）深度优先生成树9、当输入规模为n时，算法增长率最快的是（）。n5（A）n!（B）10log2n（C）2（D）3n线订装10、有9个村庄，其坐标位置如下表所示：i123456789x（i）123456789y（i）123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在（）才能使到邮局到这9个村庄的总距离和最短。（A）（4.5，0）（B）（4.5，4.5）（C）（5，5）（D）（5，0）二、应用题（本大题共5
6、小题，每小题6分，共30分）得分1、对于以下程序段，分析其最坏时间复杂度。intBinary(intn){intcount=1;while(n>1){count=count+1;n=n/2;}returncount;}2、请分析使用分治法求解最接近点对问题其最坏时间复杂度如何为O（nlogn）。33、有n个集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi，集装箱不可分割。最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。请写出使用贪心算法求解最优装载问题所用的贪心策略。4、请列举
7、3个会影响回溯搜索算法时间效率的因素。线订装5、使用动态规划算法求解矩阵连乘问题，令m[i][j]为计算矩阵A[i:j]所需的最少乘法次数，请写出m[i][j]的递归式子，并说明计算过程中求解所有m[i][j]的先后次序。说明：A[i:j]表示从第i个矩阵开始连续到第j个矩阵结束。1.5CM三、程序填空题（本大题共10空格，每空2分，共20分。得分注意：每个空格只填一个语句）1、使用回溯法求解n皇后问题，x[t]用于存储第t个皇后放置的列号，可直接使用求绝对值函数intabs(intx)。boolPlace(i
8、ntk){for(intj=1;jn)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t)==true)2}}42、计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1,x2,…,xm}和Y={y1,y
