算法设计与分析复习题.doc

终极一班 小鸟出版一、选择题（多选）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后问题是什么意思？ 在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。9.什么是最大团问题？ 给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。10.回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。三、综合题1.给出n个表达式，比较它们的阶？例：按照渐近阶从低到高的顺序排列以下表达式：4n2、logn、3n、20n、2、n2/3 又n!应该排在哪一位？按渐近阶从低到高答案为：2、logn、n2/3、20n、4n2、3n、n!2.对于下面几个递归算法写出伪代码 注意：递归条件和递归退出的条件?（1）阶层函数阶乘函数可递归地定义为： 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。阶层函数的自变量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 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)例：设有四个矩阵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的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。 例如，对于右图中的带权图，按Prim算法选取边的过程如下图所示。用这个办法实现的Prim算法所需的计算时间为 Kruskal算法Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。当图的边数为e时，Kruskal算法所需的计算时间是 。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。8.给定一张有向图，利用分支限界法求有向图的单源最短路径问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源