![](https://csdnimg.cn/release/download_crawler_static/87851868/bg1.jpg)
算法设计与分析复习题
一、选择题(多选)
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 可着色优化