算法导论复习要点

1、一基础知识部分1. 算法的复杂性有 时间复杂性和 空间 复杂性之分。2. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。3. 快速排序算法是基于分治策略的一种排序算法。4. 矩阵连乘问题的算法可由动态规划 设计实现。5. 算法是指解决问题的一种方法或一个过程 。6从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法7、 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的 关键特征。8、 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态 规划算法的主要区别。9. 贪心算法的基本要素是贪心选择 质和 最优子结构性质。10. 动态规

2、划算法的两个基本要素是最优子结构性质和重叠子问题 性质。11、合并排序算法是利用（ A）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法12、下列不是动态规划算法基本步骤的是（A ）oA、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解13下列算法中通常以自底向上的方式求解最优解的是（ B）oA、备忘录法B动态规划法C、贪心法D回溯法14.备忘录方法是那种算法的变形。（B ）A、分治法B动态规划法C、贪心法D回溯法15最长公共子序列算法利用的算法是（B ）oA、分支界限法B动态规划法C贪心法D回溯法16 .贪心算法与动态规划算法的主要区别是（B） oA、最优子结

3、构B、贪心选择性质C、构造最优解 D、定义最优解17. （ D ）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D最优子结构性质18. 矩阵连乘问题的算法可由（ B ）设计实现。A、分支界限算法B 、动态规划算法C、贪心算法 D、回溯算法19、使用分治法求解不需要满足的条件是（A ）oA子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解D子问题重叠性质20. 下列是动态规划算法基本要素的是（D ）o A、定义最优解B构造最优解C、算出最优解二、分析解答部分1、堆的高度与元素个数之间的关系2、散列表技术中碰撞的定义与解决方法是

4、什么3、平摊分析的方法有哪些？重点是势能法的应用。例、对某个数据结构执行一个n个操作的序列。如果i为2的整数次幕，则第i 个操作的代价为i，否则为1.请用聚集分析来确定每次操作的平摊代价。解：不妨设i =2j k，其中k和j均为非负整数，且j取满足等式最大的整数。定义第i个操作Di的势能函数为G( Di)2k，下面分析第i个操作Di的平摊代 价。当k =0时，第i个操作Di的实际代价G =i，从而C =G W(Di) G(Di)=i 0 2(2j -1 -2j)=i - 2j(2 -12=i -i 2当k =0时，第i个操作Di的实际代价Ci =1，从而(? =g r：(Di)=12k -2(

5、k -1)=3所以第i个操作Di的平摊代价总为O (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)=6T(2)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(f) n 的解为 O(n2)；.T(n)=2T(f) n 的解为 O(nig n)。12、给出红黑树的定义，并由此证明：(1)从根到叶子的最长的可能路径不多于最短的可能路径的两倍长