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