《算法分析与设计》期末试题及参考答案.doc

### 《算法分析与设计》知识点详解 #### 一、算法的基本概念与特性 - **算法的五大特性**： - **确定性**：对于指定的输入，算法只能有一种解释或行为，每一步操作都必须明确无误。 - **可行性**：算法中的每一个步骤都必须是可以实现的，即可以通过有限次的执行来完成。 - **输入**：一个算法至少有一个输入，可以是零个、一个或多个。 - **输出**：一个算法必须至少有一个输出，输出结果必须是明确的。 - **有穷性**：算法必须在有限步之内结束。 - **算法分析的目的**：主要在于评估算法的效率，包括时间和空间两个方面。通过对算法的分析，可以更好地理解算法的性能，从而在实际应用中做出更合理的选择。 - **算法的时间复杂性**：与问题规模相关，是问题大小\( n \)的函数。时间复杂性通常用来评估算法随着输入数据增加时所需时间的增长速度。 - **渐进时间复杂性**：是指当问题规模\( n \)趋向无穷大时，影响算法效率的主要因素是\( T(n) \)的数量级。通过比较算法的渐进时间复杂性，可以更直观地看出算法间的优劣。 - **最坏情况下的时间复杂性与平均时间复杂性的区别**： - **最坏情况下的时间复杂性**：指的是在最不利的输入下算法运行时间的上界。 - **平均时间复杂性**：是所有可能输入实例的运行时间的期望值，通常需要知道每个实例出现的概率。 #### 二、具体算法及其应用 - **二分检索（折半查找）**：适用于有序数组的查找。其基本过程是从中间元素开始比较，根据比较结果缩小查找范围，直至找到目标元素或确认不存在。 - **背包问题**：目标是最大化收益同时不超过容量限制。贪心算法在这里并不总是得到最优解，因为贪心策略考虑的是单个物品的价值密度，而非整体价值最大化。 - **回溯法**：是一种通过试探寻找问题所有解或最优解的方法。在搜索过程中，一旦发现当前路径不可行，则会回溯至上一步重新选择。 - **解空间树**：回溯法中的解空间通常表示为一棵树，其中的每个节点代表一个决策点，每个分支代表一个可能的决策。 - **判别函数**：用于判断当前状态是否可行，如在\( n \)皇后问题中，判别函数用于检查新放置的皇后是否与之前的皇后冲突。 - **分治法**：将问题分解成若干个子问题，这些子问题与原问题属于同一类型，但规模较小。递归地解决这些子问题，最后将子问题的解合并得到原问题的解。 - **递归调用**：由于子问题的规模仍然较大时，继续使用分治法解决，因此经常会出现递归调用。 - **贪心算法**：基于局部最优选择的策略来达到全局最优解。适用于某些特定类型的优化问题，在某些情况下并不能保证得到全局最优解。 - **最优化量度**：贪心算法选择的标准，如背包问题中的价值密度。 - **归并排序**：采用分治法的排序算法，将数组分成两个子数组进行排序，然后合并这两个有序子数组。 - **分治思路**：不断地将数组分成更小的部分，直到每个部分只包含一个元素，然后逐步合并排序。 - **快速排序**：同样是基于分治法的高效排序算法。选择一个基准元素，将数组分成两部分，左边的元素小于等于基准，右边的元素大于基准。 - **基本思想**：通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。 - **递归**：递归调用是一种函数或过程调用自身的方法。 - **直接递归**：函数直接调用自身。 - **间接递归**：两个或更多函数互相调用对方，形成一个循环。 - **消除递归**：通常使用栈数据结构来模拟递归过程，从而实现递归的非递归版本。 以上是《算法分析与设计》课程中的一些核心知识点，这些知识点不仅对于期末考试非常重要，也是计算机科学领域中非常基础且实用的概念和技术。希望通过对这些知识点的学习和掌握，能够帮助大家更好地理解和运用算法解决实际问题。