《算法导论期末复习要点》由会员分享，可在线阅读，更多相关《算法导论期末复习要点（3页珍藏版）》请在金锄头文库上搜索。
1、1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。2.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。3. 快速排序算法是基于 分治策略 的一种排序算法。4.矩阵连乘问题的算法可由 动态规划 设计实现。5、算法是指解决问题的 一种方法 或 一个过程 。6、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。7、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。8、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。9.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。10
2、.动态规划算法的两个基本要素是最优子结构性质和重叠子问题 性质 。11、合并排序算法是利用（ A ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法12、下列不是动态规划算法基本步骤的是（ A ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解13下列算法中通常以自底向上的方式求解最优解的是（ B ）。A、备忘录法B、动态规划法C、贪心法D、回溯法14.备忘录方法是那种算法的变形。（ B ）A、分治法B、动态规划法C、贪心法D、回溯法15最长公共子序列算法利用的算法是（ B ）。A、分支界限法B、动态规划法C、贪心法D、回溯法16贪心算法与动态规划算法的主
3、要区别是（ B ）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解17. （ D ）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质18. 矩阵连乘问题的算法可由（ B）设计实现。A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法19、使用分治法求解不需要满足的条件是（A ）。A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解20下列是动态规划算法基本要素的是（ D ）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质二、分析解答部分1、堆的高度与元素个数之间
4、的关系2、散列表技术中碰撞的定义与解决方法是什么3、平摊分析的方法有哪些？重点是势能法的应用。例、对某个数据结构执行一个n个操作的序列。如果i为2的整数次幂，则第i个操作的代价为i，否则为1.请用聚集分析来确定每次操作的平摊代价。解：不妨设，其中k 和j均为非负整数，且j取满足等式最大的整数。定义第i个操作的势能函数为，下面分析第i个操作的平摊代价。当时，第i个操作的实际代价，从而当时，第i个操作的实际代价，从而 所以第i个操作的平摊代价总为。4、贪心算法的应用，参考书上的0-1背包问题和部分背包问题的例子。5、作图说明利用合并排序算法将输入数组按从小到大排序的执行过程。6、作图说明利用堆排序
5、（HEAPSORT）将数组从小到大排序的执行过程，注意包含建最大堆（BUILD-MAX-HEAP）的执行过程。7、用主方法求解递归式紧确的渐进界，比如8、写出利用动态规划解矩阵链乘问题的最小代价的递归式，并由此给出维数序列为的最优加全括号的方案。9、会写出利用动态规划解最长公共子序列（LCS）问题的最大长度的递归式，并由此确定和的最长公共子序列。10、对某个数据结构执行一个个操作的序列。如果为2的整数次幂，则第个操作的代价为，否则为1.请用聚集分析来确定每次操作的平摊代价。11、猜测下列递归式的良好渐进界，并用代换法证明你的猜测：(1).的解为； (2).的解为。12、给出红黑树的定义，并由此证明：（1）从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 （2）一棵有n个内节点的红黑树的高度至多为13、给出渐进记号记号、记号和记号的定义，并证明：对任意实常数a和b, 其中b0,，提示：当n足够大时，3 / 3
