算法设计与分析复习题

《算法设计与分析复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、终极一班小鸟出版一、选择题（多选）1.算法必须满足哪些条件？算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足条件：(1)输入：有零个或多个由外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。2.哪些问题比较适合用递归算法？阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的

2、递归算法）：（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）旅行售货员问题

3、（9）圆排列问题（10）电路板排列问题（11）连续邮资问题二、概念题1.递归的概念是什么？直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。2.什么是0-1背包问题？给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。该问题被称为0-1背包问题。3.什么是哈夫曼编码，它有什么优缺点？由哈夫

4、曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼编码是广泛地用于数据文件压缩。用于数据的无损耗压缩。其压缩率通常在20%～90%之间。优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。4.什么是图的m着色问题？给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜

5、色。是否有一种着色法使G中每条边的2的顶点着有不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。5.什么是单源最短路径问题？-8-终极一班小鸟出版给定一个带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路的长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。6.分治法适用

6、的条件有哪几个？分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。7.贪心算法有哪几个重要的性质，为什么可以适合处理某些问题？从许多可以用贪心算法求解的问题中可以看到它们具有两个重要的性质：贪心选择性质和最优子结构性质。贪心选择性质是指所求问题的整体

7、最优解可以通过一系列局部最优的选择，即由贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。8.n后问题是什么意思？在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。9.什么是最大团问题？给定无向图G=(V，E)。如果UÍV，且对任意u

8、，vÎU有(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!应该排在哪一位？按渐近阶从低到高答