2008.1算法设计与分析课程期末试卷new

《2008.1算法设计与分析课程期末试卷new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华南农业大学期末考试试卷（A卷）2007学年第一学期　考试科目：　算法分析与设计　考试类型：（开卷）　　　考试时间：　120　分钟学号姓名年级专业题号一二三总分得分评阅人一、选择题（20分，每题2分）1、voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}上述算法的时间复杂度为。A．O（2n）B．O（nlogn）C．Θ（n！）D．Θ（nn）2、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用来消除或减少问题的好坏实例间的这

2、种差别。（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法3、对于下列二分搜索算法，正确的是。（A）publicstaticintbinarySearch(int[]a,intx,intn)7{intleft=0,right=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle;elseright=middle;}//whilereturn–1;}（B）publicstaticintbinarySearch

3、(int[]a,intx,intn){intleft=0,right=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x>=a[middle])left=middle;elseright=middle;}//whileif(x==a[left])returnleft;elsereturn–1;}（C）publicstaticintbinarySearch(int[]a,intx,intn){intleft=0,right=n-1;while(left

4、(x0&&x>=a[0]){intleft=0,right=n-1;while(left

5、rnleft;}//ifreturn–1;}4、当输入规模为n时，算法增长率最快的是。（A）12n（B）100log2n（C）2n2（D）3nlog3n5、关于0－1背包问题以下描述正确的是。（A）可以使用贪心算法找到最优解（B）能找到多项式时间的有效算法（C）使用教材介绍的动态规划方法可求解任意0－1背包问题（D）对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题6、有n个独立的作业{1,2,..,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更

6、小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适。（A）作业从小到大依次分配给空闲的机器（B）作业从大到小依次分配给空闲的机器（C）每个机器分配一样的作业数（D）使用以上几种贪心策略都能找到最优解，所以都合适77、使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为。（A）10（B）11（C）500（D）10008、设q（n，m）是将正整数n划分成最大加数不大于m的若干不同正整数之和的划分数，则q（n，m）为。（A）1（n=

7、1

8、

9、m=1）q(n,n)（nm>1）（B）1（n=1

10、

11、m=1）q(n,n)（nm>1）（C）1（n=1

12、

13、m=1）q(n,n)（nm>1）(D)0（n>1&&m=1）1（n=1）q（n，m）=q(n,n)（