计算机学院2012工程硕士《算法设计与分析》考试试卷.doc

湖北工业大学二O一二 年工程硕士班试卷算法设计与分析 试题 （计算机专业用）一、单项选择题，共5题，每小题4分。 （20分）1阶乘函数用递归定义Public static int factorial(int n) if(n = = 0) return 1; return _ ;A. n*factorial(n)B. n*factorial(n-1)C. n*factorial(n-2)D. n*factorial(n+1)2上界函数bound计算结点所相应价值的上界。private static double bound (int i) /计算结点所相应价值的上界 double cleft = c-cw;/剩余容量 double b = cp;/价值上界 / 以物品单位重量价值递减序装填剩余容量 while (i=n & wi=cleft) cleft -= wi; b += pi; i+; /装填剩余容量装满背包 if (ian/2C. x=an/2D. xan/24实现快速排序算法如下：private static void quickSort(int p ,int r) if(pr) int q=partition(p,r); /以确定的基准元素ap对子数组ap;r进行划分 _ /对左半段排序 quickSort(q+1,r); /对右半段排序 A. quickSort(p,q-1)B. quickSort(p+1,q-1)C. quickSort(p,q+1)D. quickSort(p,q-2)5回溯法对解空间进行深度优先搜索，一般使用递归方法实现回溯法：void backtrack (int t) if (tn) output(x); else for (int i=f(n, t); i 0) （1）hanoi(n-1,a,b,c) ; move(a,b); （2）hanoi(n-1,c,a,b) ; 2、用随机投点法计算p值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率，从而 。double Darts(int n) static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if ( （3）X*Y/r*r )=1) k+; return （4）4K/N ;3、N皇后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。bool Queen:Place(int k)/ 解向量：(x1, x2, , xn)/ 显约束：xi=1,2, ,n/ 隐约束：/ 1)不同列/ 2)不处于同一正、反对角线 for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); 三、简答题，共5题，每题10分。 （50分）1、分治法的基本思想是什么？ 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题（1kn），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 2、动态规划算法的基本思想是什么？动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。3、贪心算法的基本思想是什么？贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 4、回溯法的基本思想是什么？(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。5、分支限界法的基本思想是什么？ 四、棋盘覆盖问题 （15分）假设对44的棋盘进行L型分割示意图如下：请根据递归思想，将如下88的棋盘进行L型分割:五、算法分析题 （15分）给出如下顺序搜索算法，请分别分析该算法最好情况下、最坏情况下、及平均情况下的算法搜索次数。其中，在平均情况下，假设搜索成功的概率为p ( 0 p 1 )，在数组的每个位置i ( 0 i n )搜索成功的概率相同，均为 p/n。 templateint seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1;六、算法设计题 （20分）用贪心算法设计背包问题算法, 其算法基本思想如下：首先计算每种