一、选择题（多选）1.算法必须满足哪些条件？算法是指解决问题的一种方法或一个过程。

算法是若干指令的有穷序列，满足条件：(1)输入：有零个或多个由外部提供的量作为算法的输入。

(2)输出：算法产生至少一个量作为输出。

(3)确定性：组成算法的每条指令是清晰，无歧义的。

(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

2.哪些问题比较适合用递归算法？阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的递归算法）：（1）二分搜索技术、（2）大整数的乘法、（3）Strassen 矩阵乘法、（4）棋盘覆盖、（5）合并排序、（6）快速排序、（7）线性时间选择、（8）最接近点对问题、（9）循环赛日程表3. 哪些问题比较适合用贪心算法？（1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）单源最短路径（5）最小生成树（6）多机调度问题4. 哪些问题比较适合用回溯法？（1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题二、概念题1.递归的概念是什么？直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2.什么是0-1背包问题？给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。

选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。

该问题被称为0-1背包问题。

3.什么是哈夫曼编码，它有什么优缺点？由哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。

哈夫曼编码是广泛地用于数据文件压缩。

用于数据的无损耗压缩。

其压缩率通常在20%～90%之间。

优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。

4.什么是图的m着色问题？给定一个无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

是否有一种着色法使G中每条边的2的顶点着有不同颜色。

这个问题是图的m可着色判定问题。

若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。

求一个图的色数m的问题称为图的m可着色优化问题。

5.什么是单源最短路径问题？给定一个带权有向图G =(V ,E)，其中每条边的权是非负实数。

另外，还给定V 中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路的长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

6.分治法适用的条件有哪几个？分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

7.贪心算法有哪几个重要的性质，为什么可以适合处理某些问题？从许多可以用贪心算法求解的问题中可以看到它们具有两个重要的性质：贪心选择性质和最优子结构性质。

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即由贪心选择来达到。

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

8.n 后问题是什么意思？在n ×n 格的棋盘上放置彼此不受攻击的n 个皇后。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 后问题等价于在n ×n 格的棋盘上放置n 个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

9.什么是最大团问题？给定无向图G=(V ，E)。

如果U ⊆V ，且对任意u ，v ∈U 有(u ，v)∈E ，则称U 是G 的完全子图。

G 的完全子图U 是G 的一个团当且仅当U 不包含在G 的更大的完全子图中。

G 的最大团是指G 中所含顶点数最多的团。

10.回溯法的基本思想(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

三、综合题1.给出n 个表达式，比较它们的阶？例：按照渐近阶从低到高的顺序排列以下表达式：4n 2、logn 、3n 、20n 、2、n 2/3又n!应该排在哪一位？按渐近阶从低到高答案为：2、logn 、n 2/3、20n 、4n 2、3n、n!2.对于下面几个递归算法写出伪代码 注意：递归条件和递归退出的条件? （1）阶层函数阶乘函数可递归地定义为：边界条件 递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

阶层函数的自变量n 的定义域是非负整数。

递归式的第一式给出了这个函数的初始值，00)!1(1!>=⎩⎨⎧-=n n n n n是非递归地定义的。

每个递归函数都必须有非递归定义的初始值，否则，递归函数就无法计算。

递归式的第二式用较小自变量的函数值来表示较大自变量的函数值的方式来定义n 的阶层。

定义式的左右两边都引用了阶层记号，是一个递归定义式，可递归地计算如下：Int factorial(int n) {If (n= = n) return 1;Return n*factorial(n-1); }（2）Fibonacci 数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci 数列。

它可以递归地定义为：}边界条件 递归方程这是一个递归关系式，它说明当n >1时，这个数列的第n 项的值是它前面两项这和。

它用两个较小的自变量的函数值来定义一个较大自变量的函数值，所以需要两个初始值F(0)和F(1)。

第n 个Fibonacci 数可递归地计算如下：int fibonacci(int n) {if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2); }3.给定一张图，求出从源结点到目标结点的最短路径，用Dijkstra 算法，需画出表格 Dijkstra 算法是解单源最短路径问题的贪心算法。

基本思想是，设置顶点集合S 并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。

初始时，S 中仅含有源。

设u 是G 的某一个顶点，把从源到u 且中间只经过S 中顶点的路称为从源到u 的特殊路径，并用数组dist 记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra 算法每次从V-S 中取出具有最短特殊路长度的顶点u ，将u 添加到S 中，同时对数组dist 作必要的修改。

一旦S 包含了所有V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。

例如，对下图中的有向图，应用Dijkstra 算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。

110)2()1(11)(>==⎪⎩⎪⎨⎧-+-=n n n n F n F n F（1）6皇后问题（3）10皇后问题5.关于汉诺塔的递归算法？设a,b,c是3个塔座。

开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

void hanoi(int n, int a, int b, int c){if (n > 0){hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);}}6.分析给出几个矩阵，要求用加括号的方法，使矩阵连乘所使用的时间最少首先确定这几个矩阵是否可乘！完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号，即A=(BC)QQQQQQQQQQQQQQQQQQQQ例：设有四个矩阵A,B,C,D,它们的维数分别是A=50*10 B=10*40 C=40*30 D=30*5总共有五种完全加括号的方式：(A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC))D)解：①：BC：10*40*30=12000 (BC)*D=10*30*5=1500 A((BC)D)=50*10*5=2500 故(A((BC)D))=12000+1500+2500=16000②：CD=40*30*5=6000 B(CD)=10*40*5=2000 A(B(CD))=50*10*5=2500故(A(B(CD)))=6000+2000+2500=10500③：AB=50*10*40=20000 CD=40*30*5=6000 (AB)(CD)=50*40*5=10000故((AB)(CD))=20000+6000+10000=36000④：AB=50*10*40=20000 (AB)C=50*40*30=60000 ((AB)C)D=50*30*5=7500故(((AB)C)D)=20000+60000+7500=87500⑤：BC=10*40*30=12000 A(BC)=50*10*30=15000 (A(BC))D=50*30*5=7500故((A(BC))D)=12000+15000+7500=34500分别需要计算的次数为：16000, 10500, 36000, 87500, 34500以上用到穷举法，即列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次。

7.给定一张图，利用贪心算法画出此图的最小生成树，共需两种方法Prim算法设G=(V,E)是连通带权图，V={1,2,…,n}。

构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。