return binarysearch(low,mid-1,a,x); else return binarysearch(mid+1,high,a,x); end if end if
算法分析与设计模拟试题二答案
一、填空题答案（每小题4分，共计40分） 1. 程序设计语言、有限性 2. 最坏
3. 递归算法、递归函数
4. 贪心算法、动态规划算法
5. )(2n O 、O(C n )
6.
n log 、n 20、25n 、3n
7. 分治策略、已排好序、)(log n O 、)(n O 8. 最优子结构（性质）、子问题重叠（性质） 9. 自顶向下、自底向上 10. 贪心算法、动态规划算法。
二、简答题答案（每小题10分，共计40分） 1. 分治算法的一般步骤：
分解 → 直接或递归求解子问题 → 组合 递归方程
分治算法的时间复杂性C(n)往往满足如下的递归方程：
⎩⎨
⎧>+===0
0n n , )()()(n ,
)(n g c n aC n C n d n C
其中，n: 问题的规模。
n 0: 可直接解的问题规模的阈值。 a: 分解出的需要求解的子问题的个数。 n/c: 分解出的子问题的规模。
g(n): 分解规模为n 的问题以及组合相应子问题的解 所需的时间。
d: 直接解规模为n 0的问题所需的时间。 2. 0-1背包问题的形式化描述是：
3. 贪心算法的简要求解步骤如下：
① 将优化问题转化成这样的一个问题，即先做出选择，再解决剩下的一个子问题。 ② 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全性。
③ 说明在做出贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所
做的贪心选择联合起来，可以得出原问题的一个最优解。
4. 归并排序的基本思想是：
将待排序的序列分成长度大致相等的两个子序列，分别对2个子序列进行排序，最终将2个已排好序的子序列合并为有序的完整序列。
三、算法分析和设计题答案（每小题10分，共计20分） 1. Fibonacci 数列的递归定义式是：
⎩⎨
⎧>=-+-=11,0)2()1(1)(n n n F n F n F 当当
第n 个Fibonacci 数可以递归计算如下:
public static int Fibonacci(int n) { if( n<=1 ) return 1;
return Fibonacci(n-1) + Fibonacci(n-2) ;
}
2. 二分搜索算法的java 语言描述如下： public static int BinarySearch(int[ ] a, int x, int n) {
int left=0; int right=n-1; while(left<=right) {
int middle = (left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left = middle+1;
∑∑==≤∈-≤≤>>>n
i i i n
i i i i n i i C x x x x v w C 1
1
21x v ,x w },1,0{),,...,,(10n ,
n i 1,0,0,0达到最大。
而且使得向量元要求找出给定
