《2008.1算法设计与分析课程期末试卷》由会员分享，可在线阅读，更多相关《2008.1算法设计与分析课程期末试卷（12页珍藏版）》请在金锄头文库上搜索。
1、1华南农业大学期末考试试卷（华南农业大学期末考试试卷（A 卷）卷）2007 学年第一学期学年第一学期 考试科目：考试科目： 算法分析与设计算法分析与设计 考试类型：（开卷）考试类型：（开卷） 考试时间：考试时间： 120 分钟分钟学号 姓名 年级专业 题号题号一一二二三三总分总分得分得分评阅人评阅人一、选择题（一、选择题（20 分，每题分，每题 2 分）分）1、void hanoi(int n, int a, int b, int c)if (n 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a); 上述算法的时间复杂度为 A。 AO（2n）
2、 BO（nlog n）C（n！）D（nn）2、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有 较大差别时，可以使用 B 来消除或减少问题的好坏实例间的这种差别。 （A）数值概率算法 （B）舍伍德算法 （C）拉斯维加斯算法 （D）蒙特卡罗算法3、对于下列二分搜索算法，正确的是 D 。 （A）public static int binarySearch(int a, int x, int n)2int left = 0, right = n-1; while(left amiddle) left = middle; else right = middle;/while re
3、turn 1; （B）public static int binarySearch(int a, int x, int n) int left = 0, right = n-1; while(left+1 != right) int middle = (left + right) / 2; if(x = amiddle) left = middle; else right = middle; /while if(x = aleft) return left; else return 1; （C）public static int binarySearch (int a, int x, int
4、n) int left = 0, right = n-1; while(left 0 while(left m） 。对于多级调度问题，使用以下哪种贪心策略比较合适 B 。 （A） 作业从小到大依次分配给空闲的机器 （B） 作业从大到小依次分配给空闲的机器 （C） 每个机器分配一样的作业数 （D） 使用以上几种贪心策略都能找到最优解，所以都合适47、使用二分搜索算法在 1000 个有序元素表中搜索一个特定元素，在最坏情况下， 搜索总共需要比较的次数为 。 （A）10（B）11（C）500（D）10008、设 q（n，m）是将正整数 n 划分成最大加数不大于 m 的若干不同正整数之和的划 分数，则 q（n，m）为 B 。 （A） 1 （n=1 | m=1） q(n, n) （n m 1）（B）1 （n=1 | m=1） q(n, n) （n m 1）（C）1 （n=1 | m=1） q(n, n) （n m 1）(D)0 （n 1 后一种情况可以从每个盘子中 拿掉一个苹果，不影响不同放法的数目，即 f(m,n) = f(m-n,n). 而总的放苹果的放法 数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)。边界条件为 m=0 或 n=1 时，只有 一种放法。
