1．一个.java文件中可以有（ ）个public类。
A．一个 B．两个 C．多个 D．零个
2．一个算法应该是（ ）
A．程序 B．问题求解步骤的描述
C．要满足五个基本特性 D．A和C
3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ ）
A．唯一性 B．有穷性 C．有0个或多个输入 D．有输出
4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（ ）
A．3，15，130，20，98，67 B．3，15，20，130，98，67
C．3，15，20，67，130，98 D．3，15，20，67，98，130
5．下列关于算法的描述，正确的是（ ）
A．一个算法的执行步骤可以是无限的 B．一个完整的算法必须有输出
C．算法只能用流程图表示 D．一个完整的算法至少有一个输入
6．Java Application源程序的主类是指包含有（ ）方法的类。
A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法
7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（ ）
A．分治法 B．减治法 C．蛮力法 D．变治法
8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。
算法设计与分析■期末考试题整理
1、 一个算法应有哪些主要特征？
又穷性，确定性，可行性，0个或多个输入，一个或多个输岀
2、 分治法(Divide and Conquer)与动态规划(Dynamic Programming)有什么不同？
分治算法会重复的求解公共了问题，会做许多不必要的T作，而动态规划对每个了问题Z求 解一次，将其结果存入一张表屮，从而避免了每次遇到各个了问题有从新求解。
3、 试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。
贪心算有效性：最小生成树、哈弟曼、活动安排、单元最短路径。
无效反例：0——I背包问题，无向图找嚴短路径问题。
4、 求解方程 fi[l)=f(2)=l。
由 f(n)=f(n-1 )+f(n-2) nJ'得
f(n)-f(n-l)-f(n-2)=0M得方程的特征方程为
/ _兀一 1 = 0,设特征方程的2个根本分别为"，兀2,则可得 尤]=心=匕二2,则有
- 2
1 4- V5 „ 1 — yl~5 n /S) = C|(—y—) +C2(—y—)
乂/•⑴= .f(2) “可得
可得 C] = a,c2 = h
f(n) = a(^y+b(^)
5、 求解方稈 T(n)=2T(n/2)+l, T(l)=l,设 尸2匚r(n) = 2r(n/2) + l
2T(n/2) = 22T(n/22) + 2
22T(/7/22) = 23T(A?/23) + 22
2iTS/2z) = 25S/2*) + 2"T
上面所有式子相加，相消得
T(n) = 2*7(1) + 2°+2,+22 + + 2^ -J-2*
=2k +1* -------- 1-2
=2A+, -1
int part(int *a,int p,int r){
int i,j,x,t;
x=a[r];
i=p-l；
算法设计与分析期末复习题【试题.知识点】
算法设计与分析期末考试复习题
1．算法有哪些特点？为什么说⼀个具备了所有特征的算法，不⼀定就是使⽤的算法?
2．证明下⾯的关系成⽴：(参考例题1.5--1.6)
（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)
(3)n!=Θ(n n) (4)5n2-6n=Θ(n2)
3.考虑下⾯的算法：
输⼊：n个元素的数组A
输出：按递增顺序排序的数组A
1. void sort(int A[],int n)
2. {
3. int i,j,temp;
4. for(i=0;i
5. for(j=i+1;j
6. if(A[j]
7. temp=A[i];
8. A[i]=A[j];
9. A[j]=temp;
10. }
11. }
（1）什么时候算法所执⾏的元素赋值的次数最少？最少多少次？
（2）什么时候算法所执⾏的元素赋值的次数最多？最多多少次？
4.考虑下⾯的算法：
输⼊：n个元素的数组A
输出：按递增顺序排序的数组A
1. void bubblesort(int A[],int n)
2. {
3. int j,i,sorted;
4. i=sorted=0;
5. while(i
6. sorted=1;
7. for(j=n-1;j>i;j--) {
8. if(A[j]
9. temp=A[j];2
10. A[j]=A[j-1];
11. A[j-1]=temp;
12. sorted=0;
13. }
14. }
15. i=i+1;
16. }
17. }
（1）算法所执⾏的元素⽐较次数最少是多少次？什么时候达到最少？
（2）算法所执⾏的元素⽐较次数最多是多少次？什么时候达到最多？
（3）算法所执⾏的元素赋值次数最少是多少次？什么时候达到最少？
（4）算法所执⾏的元素赋值次数最多是多少次？什么时候达到最多？
5.解下⾯的递归⽅程：
1、用计算机求解问题得步骤:
1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制
2、算法定义:算法就是指在解决问题时,按照某种机械步骤一定可以得到问题结果得处理过程
3、算法得三要素
1、操作2、控制结构3、数据结构
算法具有以下5个属性:
确定性:算法中每一条指令必须有确切得含义。不存在二义性。只有一个入口与一个出口
可行性:一个算法就是可行得就就是算法描述得操作就是可以通过已经实现得基本运算执行有限次来实现得。
输入:一个算法有零个或多个输入,这些输入取自于某个特定对象得集合。
输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系得量。
算法设计得质量指标:
正确性:算法应满足具体问题得需求;
可读性:算法应该好读,以有利于读者对程序得理解;
健壮性:算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不就是产生莫名其妙得输出结果。
经常采用得算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法
迭代法
基本思想:迭代法也称“辗转法”,就是一种不断用变量得旧值递推出新值得解决问题得方法。
解题步骤:1、确定迭代模型。根据问题描述,分析得出前一个(或几个)值与其下一个值得迭代关系数学模型。
2、建立迭代关系式。迭代关系式就就是一个直接或间接地不断由旧值递推出新值得表达式,存储新值得变量称为迭代变量qL20i。
3、对迭代过程进行控制。确定在什么时候结束迭代过程,这就是编写迭代程序必须考虑得问题。不能让迭代过程无休止地重复执行下去。迭代过程得控制通常可分为两种情况:一种就是所需得迭代次数就是个确定得值,可以计算出来;另一种就是所需得迭代次数无法确定。对于前一种情况,可以构建一个固定次数得循环来实现对迭代过程得控制;对于后一种情况,需要进一步分析出用来结束迭代过程得条件。XvgoD。
第1页 共11页 算法设计与分析的复习要点
第一章：算法问题求解基础
算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
一．算法的五个特征：
1．输入：算法有零个或多个输入量；
2．输出：算法至少产生一个输出量；
3．确定性：算法的每一条指令都有确切的定义，没有二义性；
4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；
5．有穷性：算法必须总能在执行有限步之后终止。
二．什么是算法？程序与算法的区别
1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。
三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。
四．系统生命周期或软件生命周期分为：
开发期：分析、设计、编码、测试；运行期：维护。
五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。
七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定
第2页 共11页 义包括两部分：基础情况和递归部分；
基础情况：以直接形式明确列举新事物的若干简单对象；
递归部分：有简单或较简单对象定义新对象的条件和方法
八．常见的程序正确性证明方法：
1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具；
2.反证法。
第二章：算法分析基础
一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。
二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9）
三．会计算递推式的显式。（迭代法、代换法，主方法）
四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）
1.什么是算法？
2.算法的特点？
有穷性-有限步内完成；确定性-每一步是确定的，不能有二义性；可行性-每一步有意义，每一步能求解；输入-须检查输入值值域合法性；输出-输出问题的解，无输出的算法没有意义。
补：排序算法的特点：稳定性，在位性。
稳定性：如果一个排序算法保留了等值元素在输入中的相对顺序，他被称为是稳定的。换句话说，如果一个输入列表包含两个相等的元素，他们的位置分别是i和j。i
在位性：如果一个算法不需要额外的存储空间(除了个别存储单元外),我们称它是在位的。
3.求最大公约数的伪码？
Euclid(m,n)
//计算m和n最大公约数的欧式算法
//输入：两个不全为0的非负整数m>=n
//输出：m和n的最大公约数
while n≠0 do{
r←m mod n
m←n
n←r}
return m
4.问题求解过程
理解问题；了解设备性能选择计算方法，精确或近似接法高效的数据结构算法的设计技术；设计算法；正确性证明；分析算法；编程实现算法。1-2-3-4-5-6.4-3,4-2,5-3,5-2
（理解问题； 决定：计算方法：精确或近似方法：数据结构：算法设计技术； 设计算法； 正确性证明； 分析算法； 根据算法写代码.）
5.算法分析主要步骤（框架）
算法的运行效率也称为计算复杂性(计算复杂度);
空间效率-算法运行所需的存储空间。
输入规模
增长函数
定义为输入规模的函数，用它来研究算法；
输入规模的选择
它的选择比较直接容易。
6.n元列表查找最大值-数组实现列表
MaxElement(A[0..n-1]) maxval←0
算法－特征：（1）确定性（2）多样性（3）有穷性（4）输出
• T(n)≈copC(n)
O(g(n)) 是增长次数小于等于 g(n)(以及其常数倍，n趋向于无穷大)的函数集合。
符号О
成立条件：对于所有足够大的n，t(n) 的上界由g(n)的常数倍数所确定。即，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥ n0来说，t(n) ≤c g(n)
Ω(g(n))代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合
符号Ω
成立条件：对于所有足够大的n，t(n)的下界由g(n)的常数倍所确定，
即，存在大于0的常数c和非负的整数n0，使得：
对于所有的n≥ n0来说，t(n) ≥c g(n)
Θ(g(n))是增长次数等于g(n) (以及其常数倍,n趋向于无穷大)的函数集合。
符号Θ
成立条件：对于所有足够大的n，t(n) 的上界和下界都由g(n)的常数倍数所确定，
即，存在大于0的常数c1，c2和和非负的整数n0，使得：
对于所有的n≥ n0来说，c2g(n) ≤t(n) ≤ c1g(n)
算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分。
log n
nlog n
n2
n3
2n
n!
动态规划算法的基本要素
（1） 最优子结构性质（2）重叠子问题性质
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果
算法设计与分析期末考试复习题
1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?
2． 证明下面的关系成立：(参考例题1.5--1.6)
（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)
(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)
3.考虑下面的算法：
输入：n个元素的数组A
输出：按递增顺序排序的数组A
1. void sort(int A[],int n)
2. {
3. int i,j,temp;
4. for(i=0;i
5. for(j=i+1;j
6. if(A[j]
7. temp=A[i];
8. A[i]=A[j];
9. A[j]=temp;
10. }
11. }
（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？
（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？
4.考虑下面的算法：
输入：n个元素的数组A
输出：按递增顺序排序的数组A
1. void bubblesort(int A[],int n)
2. {
3. int j,i,sorted;
4. i=sorted=0;
5. while(i
6. sorted=1;
7. for(j=n-1;j>i;j--) {
8. if(A[j]
9. temp=A[j]; 3
10. A[j]=A[j-1];
11. A[j-1]=temp;
12. sorted=0;
13. }
14. }
15. i=i+1;
16. }
17. }
（1） 算法所执行的元素比较次数最少是多少次？什么时候达到最少？
（2） 算法所执行的元素比较次数最多是多少次？什么时候达到最多？
1 1、用计算机求解问题的步骤：
1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制
2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
3、算法的三要素
1、操作2、控制结构3、数据结构
算法具有以下5个属性:
确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的.
输入：一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：
正确性：算法应满足具体问题的需求；
可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法
迭代法
基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。
2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量
3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
算法设计与分析复习知识点
算法设计与分析是计算机科学中的重要概念，它涉及到各种问题的解决方法和效率分析。在本文中，我将回顾一些算法设计与分析的核心知识点。
一、算法的基本概念
1. 算法的定义：算法是一系列明确指定的步骤，用于解决特定问题或执行特定任务。
2. 算法的特性：输入、输出、确定性、可行性和有穷性。
4. 算法的分类：常见的算法分类有分治法、贪心法、动态规划、回溯法等。
2. 空间复杂度：描述算法在执行过程中所需的额外空间，也使用大O符号表示。常见的空间复杂度有O(1)、O(n)、O(n^2)等。
三、常见的算法思想和技巧 1. 分治法：将一个大问题划分成若干个小问题，然后逐个解决，并将结果合并得到最终解。
2. 贪心法：在每一步选择中都采取当前状态下最好或最优的选择，从而希望能得到全局最优解。
3. 动态规划：将一个大问题分解成若干个子问题，通过求解子问题得到最优解，从而得到原问题的解。
4. 回溯法：通过不断地尝试所有可能的选择，然后进行回溯，找到问题的解。
四、常见算法的应用
1. 排序算法：快速排序、归并排序、插入排序等。
2. 搜索算法：深度优先搜索、广度优先搜索、A*算法等。
3. 图算法：最短路径算法、最小生成树算法、拓扑排序等。
4. 字符串匹配算法：暴力匹配算法、KMP算法、Boyer-Moore算法等。
五、算法复杂度分析
1. 最优复杂度：最好情况下算法执行所需的最小资源。
2. 平均复杂度：在所有输入情况下算法执行所需的资源的平均值。
3. 最坏复杂度：最坏情况下算法执行所需的最大资源。
六、常见问题和优化技巧 1. 递归算法的优化：尾递归优化、记忆化搜索等。
一 填空题（20x1=20分）
1. 当设定的问题有多种算法去解决时，其选择算法的主要原则是选择其中复杂性最低者。
2. 用函数自身给出定义的函数是一种递归函数。
3. 动态规划算法适用于解最优化问题。
4. 贪心算法的两个基本要素是最优子结构性质、贪心选择性质。
5. 回溯法在搜索解空间树的时候，为了避免无效搜索，通常使用深度优先手段来提高搜索效率。
6. 依据求解目标的不同，分支界限法和回溯法分别用广度优先遍历或者最小耗费优先、深度优先的方式搜索解空间树。
7. 分支界限法和回溯法主要区别在于求解目标和搜索方式不同。
8. 在分支界限法实现的时候，通常采用 方式来实现最大优先队列。
10. 产生伪随机数最常用的方法是线性同余法。
11. 线性规划算法中转轴变化的目的是将入基变量与离基变量互调位置。 12. 最大网络流问题中可增广路是残留网络中一条容量大于0的路。
13. 待解决问题适用于动态规划法的两个基本要素是 。
14. 算法必须满足的四个特征是输入、输出、确定性、有限性。
15. 算法复杂性依赖于 、 、 三个方面的复杂因素。
16. 实现递归调用的关键是
17. 动态规划算法求解问题的重要线索是问题的 性质。
18. 最优子结构性质是贪心算法求解问题的关键特征。
19. 分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
20. 问题的解空间树常见的有子集树、排列树两种类型。
21. 分支界限算法依据其从和节点表中选择获得下一扩展节点的不同方式被分为
22. 对于任何约束标准型线性规划问题，只要将所用分基本变量都设置为0，就可以获得一个 解。
二 判断题（20x1=20分）
1. 算法的描述方式有自然语言、程序语言，或者两者相结合的形式。（ ）
2. 算法满足的特性有哪些，程序有什么特征，而这有什么关系。
3. 算法复杂度越高或者越低与占用计算机资源的关系是什么。
4. 算法复杂性上界的阶，越高或者越低与结果的准确性和实际价值关系。
5. 递归算法和非递归算法两者之间的效率如何。
6. 动态规划算法带求解的问题是否可以用分支界限法、分治法、线性规划法、回溯法等其他的算法求解。
7. 动态规划算法带求解的问题，经分解得到的子问题，是独立的还是不独立的。
8. 如果问题具有最优子结构性质，请问这个问题使用动态规划法和贪心算法那个更好。
9. 贪心算法在一般情况下，是否能够得到整体最优解，还是最优解的近似值。
10. 动态规划法和贪心算法，在求解问题的时候都是自顶向下的吗？
11. 请问对于待解决的问题，有“通用解题法”之称的是什么算法？
回溯法
12. 回溯法是通过遍历搜索树找到问题的最优解的吗？
13. 在分支界限法和回溯法中，每个节点都有机会成为扩展节点吗？ 14. 对于待解决的同一个问题，随机化算法与非随机化算法，谁的复杂度高？谁的复杂度低？
15. 数值化随机算法用于求解问题的准确解吗？
16. 蒙特卡罗算法是用于球问题的准确解还是近似解，并且得到的解，一定是可靠的吗？
17. 舍伍德算法能够得到问题的准确解吗？
18. 二分搜索算法是那种算法的一种典型实例？ 分治法
19. 矩阵连乘问题，最实用的算法是什么？
20. 程序必须满足算法的所有属性吗？
21. 算法复杂性与计算机的本身资源有关吗？
22. 算法描述的方式除了自然语言、程序语言
23. 算法复杂性的阶越高越好吗？
24. 动态规划法和分治法一定要把求解的问题分解成为若干个子问题吗？
25. 如果问题具有最优子结构性质，贪心算法比其他的算法都要好吗？
三 概念题（6x2=12分）
3. 贪心算法：在对问题求解时，总是做出当前看来是最好的选择。也就是说，贪心算法并不从整体最优考虑，他所做出的选择只是在某种意义上的局部最优选择。贪心算法不能对所有问题都得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
4. 子集树：当所给问题是从n个元素的集合s中找出满足某种性质的子集时，相应的解空间树称为子集树。
5. 队列式（FIFO）分支限界法：将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
6. 分治法：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
7. 算法：由若干条指令组成的有穷序列。
8. 最优子结构：当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
9. 回溯法：以深度优先方式系统搜索问题解的算法称为回溯法。
10. 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
11. 网络流：是定义在网络的边集合E上的一个非负函数flow =
{flow(v,w)}，并称flow(v,w)为边（v,w）上的流量。 四 简答题（3x4=12分）
1. 在一个算法中调用另一个算法时，系统需在运行被调用算法之前完成哪些工作？同时从被调用算法返回调用算法需完成哪些工作？
答：在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：
（1） 将所有实参指针、返回地址等信息传递给被调用算法；
（2） 为被调用算法的局部变量分配存储区；
（3） 将控制转移到被调用算法的入口。
在从被调用算法返回调用算法时需完成三件事：
（1） 保存被调用算法的计算结果；
（2） 释放分配给被调用算法的数据区；
（3） 依照被调用算法保存的返回地址将控制转移到调用算法。
2. 动态规划算法求解问题的步骤？
答：动态规划法适用于解最优化问题。通常可以按以下4个步骤设计：
（1） 找出最优解的性质，并刻画其结构特征；
（2） 递归地定义最优值； （3） 以自底向上的方式计算最优值；
（4） 根据计算最优值时得到的信息构造最优解。
3. 线性规划法中单纯形算法的基本步骤？
答：步骤一 选入基变量。
步骤二 选离基变量。
步骤三 做转轴变换。
步骤四 转步骤一。
4. 分治法的基本思想和原理是什么？
答：分治法的基本思想是将一个规模为ｎ的问题分解为ｋ个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
5. 利用回溯法解决问题包含哪些步骤？
答：利用回溯法解题常包含以下3步骤：
（1） 针对所给问题，定义问题的解空间；
（2） 确定易于搜索的解空间结构；
（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
五 分析题（36分） 1．求下列函数的渐进表达式：
3n2+10n; n2/10+2n; 21+1/n; logn3; 10log3n
分析与解答：
3n2+10n=O(n2);
n2/10+2n=O(2n);
21+1/n=O(1);
logn3=O(logn);
10log3n=O(n)
2．讨论O(1)和O(2)的区别。
分析与解答：
根据符号O的定义易知O(1)=O(2)。用O(1)或O(2)表示同一个函数时，差别仅在于其中的常数因子。
3．按渐近阶排列表达式
按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？ 分析与解答：
按渐近阶从低到高，函数排列顺序如下：2，logn，n2/3，20n，4n2，3n，n！。
4.算法效率
(1)假设某算法在输入规模为n时计算时间为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？
分析解答：
(1)设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3*22=3*2n1/64，解得你n1=n+6。
(2)n12=64n2n1=8n。
(3)由于T(n)=常数，因此算法可解任意规模的问题。
5．阶乘函数
阶乘函数可递归地定义为：
00)!1(1!nnnnn
int factorial(int n)
if(n = = 0) return 1;
return n * factorial(n-1);
6．Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，„„，称为Fibonacci数列。它可以递归地定义为：
请对这个无穷数列设计一个算法，并进行描述（自然语言描述和VC++描述）.
110)2()1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：
int fibonacci(int n)
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
7．循环赛日程表
设有n=2k个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行n-1天。
请设计一个算法解决以上问题，并进行描述（自然语言和C++语言）
按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。