算法设计与分析课程期末试卷.docVIP

华南农业大学期末考试试卷（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。 A．O（2n） B．O（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) { int left = 0, right = n-1; while(left = right) { int middle = (left + right) / 2; if(x == a[middle]) return middle; if(x a[middle]) left = middle; else right = middle; }//while return –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 = a[middle]) left = middle; else right = middle; }//while if(x == a[left]) return left; else return –1; } （C）public static int binarySearch (int[] a, int x, int n) { int left = 0, right = n-1; while(left right-1) { int middle = (left + right) / 2; if(x a[middle]) right = middle; else left = middle; }//while if(x == a[left]) return left; else return –1; } （D）public static int binarySearch(int[] a, int x, int n) { if(n 0 x = a[0]) { int left = 0, right = n-1; while(left right) { int middle = (left + right + 1) / 2; if(x a[middle]) right = middle - 1; else left = middle; }//while if(x == a[left]) return left; }//if return –1; } 4、当输入规模为n时，算法增长率最快的是 C 。 （A）12n （B）100log2n （C）2n2 （D）3nlog3n 5、关于0－1背包问题以下描述正确的是 。 （A） 可以使用贪心算法找到最优解 （B） 能找到多项式时间的有效算法 （C） 使用教材介绍的动态规划方法可求解任意0－1背包问题 （D） 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题 6、有 n 个独立的作业 { 1 , 2 , .. , n }，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为 ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成（n m）。对于多级调度问题，使用以下哪种贪心策略比较合适 B 。 （A） 作业从小到大依