算法设计与分析期末考试题，急！

来源：蜘蛛抓取(WebSpider) 时间：2022-06-20 07:05 标签： 算法期末考试大题

算法分析与设计期末复习

1. 问答题（30分5道或6道）

概念（集中在第一章概论）、主要算法思想（分治法、蛮力法、回溯法、分支限界法、贪心算法、动态规划）

2. 计算题（30分，两部分，一部分求准确界，或着说上界下界，判断两个式子是什么关系、一部分递推式的计算）

算法复杂度分析：两个算法上界、下界、准确界（等阶）

递归算法、递推式的复杂度的计算（书上2.5P74页）

3. 算法分析题（40分4道）

大部分是书上已有的例子、不同的方法

只要求把算法的主要步骤写出来、程序可以不写，可以不写源代码

只要把算法的主要步骤，用伪代码的形式写出来就可以了

因此对于这些渐近记号的使用最准确应该是“f(n)∈ O (g(n))”，但是一般都是写成“f(n)=O(g(n))”。

1. 二阶常系数齐次递归方程求解步骤：

（2）得到特征根，r1和r2,

（4）代入初始条件，求c1和c2

（5）得到递归方程的解f(n)=...

2. 二阶常系数非齐次递归方程求解步骤：

（1）写出对应齐次特征方程

（3）得到对应齐次递归方程的通解：f’(n)=

（4）由于g(n)= 属于n的m次多项式

（6）代入原递归方程得，

（8）非齐次递归方程的通解为：

（9）初始条件代入，求c1和c2

（10）所以，非齐次递归方程的通解为：

算法是求解问题是的一系列计算步骤，能够将输入数据转换成输出结果。如果一个算法能够对其几乎每一个输入实例输出正确的结果并停止，那么这个算法就是正确的。一个正确的算法能解决给出的求解问题，一个不正确的算法对于某些输入来说可能根本不会停止，或者停止后得到的不是预期想要的结果。

2. 算法设计的目标？

（1）正确性：要求算法能够正确地执行预先设定的功能和性能的要求，这是最重要也是最基本的要求。

（2）可使用性：要求算法能够很方便地使用，这个特性也叫做用户友好性。

（3）可读性：算法应该易于人的理解，也就是可读性好。算法的逻辑应该是简单的、清晰的和结构化的。

（4）健壮性：算法应该具有一定的容错性，即提供异常处理，对那些不合理的数据进行检查，不经常出现异常中断和死机现象。

（5）高效率和低存储量：通常，算法的效率主要指算法的执行时间，如果一个问题能够被多个算法求解，执行时间短的算法效率高。算法的存储量指的是算法在执行的过程中所占用的最大存储空间。算法的效率和低存储量都与问题的规模有关。

（1）有限性：一个算法总是能够在执行有限步之后结束，每一步都可以在有限的时间内完成。

（2）确定性：算法的每一条指令都有明确的含义，不会产生二义性。

（3）可行性：算法的每一条运算都必须是足够基本的，原则上都能够被精确地执行，甚至人们仅用纸和笔通过有限次运算就能完成。

（4）输入性：一个算法有0个或多个输入。

（5）输出性：一个算法有1个或多个 输出。

在数学和计算机科学中，递归是指函数在定义是调用自身的方法。如果在定义函数p是调用函数p,则成为直接递归。如果在定义函数p时调用函数q，在定义函数q是调用函数p,则成为间接递归。任何间接递归都能够转换成直接递归。

5. 递归算法设计的一般步骤？

（1）对原问题f(Sn)进行分析，抽象出合理的“小问题”f(Sn-1)。

（2）假设f(Sn-1)是可解的，在此基础上确定f(Sn)的解，即给出了f(Sn)与f(Sn-1)之间的关系。

（3）给出一个特定情况（如f(1)或f(0)）的解,由此作为递归出口。

6. 分治法的主要思想？

对于一个难以直接计算的问题，将它分解为一些规模较小的相同问题，以便琢个击破，分而治之。对于一个规模为n的问题，如果能够很容易的解决，那么直接求解。如果不能，那么将这个问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题的形式相同，递归地求解这些子问题，然后通过这些子问题的解得到原问题的解。

7. 快速排序伪代码：

1. 将记录i和j分别指向待排序区域的最左端和最右端。

2. 重复下述过程，直到i=j

3. 右侧扫描，直到记录j的关键码小于基准的关键码；

5. 左侧扫描，直到记录i的关键码小于基准的关键码；

7. 退出循环，直到i和j指向基准的位置，并返回该位置。

8. 归并排序主要步骤：

2. 递归地将两个序列a[low...mid]和a[mid+1...high]进行二路归并排序，其终结条件是直到子序列的长度为1或0

9. 折半查找伪代码：

2. 测试查找区间a[low...high]是否存在，若不存在，则查找失败，否则

10. 蛮力法求解0/1背包问题伪代码

输入：背包的最大容量，物品的个数n,n个物品的重量w[n]和物品的价值v[n]

输出：装入背包的物品编号及其产生的最大价值

1. 初始化背包的最大价值max=0，结果子集s=空集

2. 对集合{1,2,....n}的每一个子集t，执行如下操作

3. 初始化当前背包的重量w=0,背包的价值v=0

4. 对子集t中的每一个元素j

6. 否则，转到步骤2考察下一个子集

8. 输出子集s中的元素

11. 蛮力法解决任务分配问题伪代码

3. 初始化当前方案的成本cost=0

12. 什么是回溯法？

答：回溯法是在包含所有解的解空间树中，采用深度优先搜索策略，从根节点出发搜索该解空间树。

13. 回溯法的主要思想：从一条路出发，能进则进，不能进就退回来，换一条路在试

答：它是按跳跃式的深度优先搜索方式搜索解空间树，即判定函数先判定x[k]的取值，如果x[k]的取值是合理的，则搜索以x[k]为根节点的子树，如果x[k]取完了所有的取值，则回溯到x[k-1]。

15. 回溯法求解0/1背包问题伪代码：

2. If（i>n），输出一个解，结束算法；

16. 回溯法求解N皇后问题伪代码：

3.2 将皇后k摆放在位置x[k]处，如果不发生冲突，则转步骤3.3，否则x[k]--，考察下一列

3.3 如果n个皇后全部摆放，则输出一个解，结束算法；

3.4 如果仍有皇后未摆放，则转步骤3，摆放下一个皇后

4. 退出循环，则n皇后问题无解

17. 分支限界法求解0/1背包问题

1. 根据限界函数计算目标函数的上界up，采用贪心算法求其下界down

2. 计算根结点的目标函数值并加入到待处理的结点表PT中

3. 循环直到某个叶子结点的目标函数值取极大值

4. i=pt 表中具有最大值的结点

5. 对结点i的每一个孩子x结点进行如下操作：

6. 如果结点x不满足约束条件，则丢弃该结点；

7. 如果结点x满足约束条件，则计算它的目标函数值，并加入到PT表中，

4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量。

下载百度知道APP，抢鲜体验

使用百度知道APP，立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。

我要回帖

更多关于 算法期末考试大题 的文章

 

随机推荐