算法设计与分析期末试题解析：中位数查找、石子合并、贪心策略

"2019秋算法期末回忆版试题，涉及多种算法问题，包括排序算法、动态规划、中位数查找、石子合并优化、贪心策略、A*搜索算法和二进制加法的平摊代价计算。" 这篇资料是2019年秋季学期算法课程的期末考试回忆版，由WuuTang项目提供，出题人为何震宇。试卷可能相对简单，但不保证难度一致性。何震宇老师倾向于使用作业题目和课堂例子。试卷包含选择题和大题，考察了学生对算法设计与分析的理解和应用能力。 一、选择题部分涉及排序算法的下界和Floyd算法的思想，即动态规划。 二、Master定理的应用，用于求解递归式\( T(n) = 4T'\left(\frac{n}{3}\right) + n! - 7n + 20 \)的时间复杂度。 三、中位数查找问题，要求设计一个时间复杂度为O(log(m+n))的算法，找到两个已排序数组的中位数。题目提供了A和B两个具有相同元素的数组作为示例，但实际数据可能不同，只需画出示意图即可。 四、石子合并问题，讨论了如何在一条直线上通过合并相邻石子堆达到最小花费。要求写出递推方程、给出特定情况下的运算矩阵和伪代码，此题来源于作业原题。 五、饼干分配问题，使用贪心策略解决，目标是最大化满足孩子胃口的饼干数量。需编写伪代码来描述解决方案。 六、A*搜索算法的应用，要求画出搜索树，原图包含25个节点。 七、势能法计算二进制加法的平摊代价，该问题来源于课堂幻灯片的原题。 八、Dijkstra算法寻找最短路径，需要填写表格和补充伪代码，原图包含15个节点。 这些题目涵盖了算法设计中的多个重要概念，包括排序算法、动态规划、递归复杂度分析、贪心策略、图算法和数据结构优化。解答这些问题需要深入理解算法原理并具备良好的问题解决能力。