《计算机学院工程硕士《算法设计与分析》考试试卷》由会员分享，可在线阅读，更多相关《计算机学院工程硕士《算法设计与分析》考试试卷（6页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 7 页湖北工业大学二 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) /计
2、算结点所相应价值的上界double cleft = c-cw;/剩余容量double b = cp;/价值上界/ 以物品单位重量价值递减序装填剩余容量while (ian/2 C. x=an/2 D. xan/24实现快速排序算法如下： private static void quickSort(int p ,int r) if(p 0)（1）hanoi(n-1,a,b,c) ;move(a,b);（2）hanoi(n-1,c,a,b) ;2、用随机投点法计算 值 设有一半径为 r 的圆及其外切四边形。向该正方形随机地投掷 n 个点。设落入圆内的点数 为 k。由于所投入的点在正方形上均匀分布，
3、因而所投入的点落入圆内的概率为 。所以当 n 足够大时，k 与 n 之比就逼近这一概率，从而 。double Darts(int n) static RandomNumber dart;int k=0;for (int i=1;i n) sum+;elsefor (int i=1;i int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+)if (ai=k) return i;return -1; 六、算法设计题 （20 分）用贪心算法设计背包问题算法, 其算法基本思想如下：首先计算每种物品单位重量的 价值 Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选择单位重量价值次高 的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。第 7 页 共 7 页
