算法设计与分析复习题参考_算法设计与分析复习题资源-CSDN文库

需积分: 5 162 浏览量 2023-06-01 12:24:41 上传评论收藏 138KB DOC 举报

资源推荐

资源详情

资源评论

1 页

算法设计与分析复习题

一、选择题（多选）

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页未读，立即下载

内容反馈

2201_75683007

粉丝: 0
资源: 127

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip