{ y=y+1;
for （j ＝0；j <=2n ；j++ ）
x ＋＋；
}
9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。
10、算法是指解决问题的 方法或过程 。
二、简答题：
1、按照时间复杂度从低到高排列：O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3),
O( n!)应该排在哪一位？
答：O( 2)，O( logn)，O( n 2/3)，O( 20n)，O( 4n 2)，O( 3n )，O( n!)
2、什么是算法？算法的特征有哪些？
答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。
2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性
3、给出算法的定义？何谓算法的复杂性？
计算下例在最坏情况下的时间复杂性？
for(j=1;j<=n;j++) (1)
for(i=1;i<=n;i++) (2) {c[i][j]=0; (3)
for(k=1;k<=n;k++) (4)
c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)
答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。 所需资源越多，表明算法的复杂性越高
3）该算法的主要元操作是语句5，其执行次数是n 3次。 故该算法的时间复杂度记
为O(n 3).
4、算法A 和算法B 解同一问题，设算法A 的时间复杂性满足递归方程⎩
⎨⎧>+===1n , n )2/n (T 4)n (T 1n , 1)n (T ， 算法B 的时间复杂性满足递归方程⎩
⎨⎧>+===1n , n )4/n (aT )n (T 1n , 1)n (T ，若要使得算法A 时间复杂性的阶高于算法B 时间复杂性的阶，a 的最大整数值可取多少？
答：分别记算法A 和算法B 的时间复杂性为)n (T A 和)n (T B ，解相应的递归方程得：
)n (O )n (T 2
A = ⎪⎩⎪⎨⎧>=<=4a , )n
(O 4a , )n log n (O 4a , )n (O )n (T a log B 4
依题意，要求最大的整数a 使得)n (T B 〈)n (T A 。显然，当a<=4时，)n (T B 〈)n (T A ；
当a>4时，)n (T B 〈(n)T A ⇔2a log 4< ⇔a<24=16。
所以，所求的a 的最大整数值为15。
5、算法分析的目的？
答：1)为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；
2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。
6、算法设计常用的技术？（写５种）
答： ①分治法; ②回溯法； ③贪心法； ④动态规划法
⑤分治限界法 ； ⑥蛮力法； ⑦倒推法
三、算法设计题
1、蛮力法：百鸡百钱问题？
2、倒推法：穿越沙漠问题？
第二章分治算法（1）----递归循环
一、填空题：
1、直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。
2、递归方程和约束函数（递归终止条件）是递归函数的两个要素。
二、判断题：
1、所有的递归函数都能找到对应的非递归定义。（√）
2、定义递归函数时可以没有初始值。（ X ）
三、简答题：
1、什么是递归算法？递归算法的特点？
答：1 )递归算法:是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可以直接或间接地调用自身的算法。
2) 递归算法特点：
①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）
②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）
2、比较循环与递归的异同？
答：
1)相同：
递归与循环都是解决“重复操作”的机制。
2)不同：
就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。
每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。
递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。
3、递归算法解题通常有三个步骤？
答： 1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。
2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。
3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。
