算法导论期末复习要点

《算法导论期末复习要点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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．贪心算法与动态规划算法的主要区别是（B）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解

3、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、堆的高度与元素个数之间的关系2、散列表技术中碰撞的定义与解决方法是什么3、平摊分析的方法有哪些？重点是势能法的应用。例、对某个

4、数据结构执行一个n个操作的序列。如果i为2的整数次幂，则第i个操作的代价为i，否则为1.请用聚集分析来确定每次操作的平摊代价。解：不妨设，其中k和j均为非负整数，且j2/2取满足等式最大的整数。定义第i个操作的势能函数为，下面分析第i个操作的平摊代价。当时，第i个操作的实际代价，从而当时，第i个操作的实际代价，从而所以第i个操作的平摊代价总为。4、贪心算法的应用，参考书上的0-1背包问题和部分背包问题的例子。5、作图说明利用合并排序算法将输入数组按从小到大排序的执行过程。6、作图说明利用堆排序（HEAPSORT）将数组从小到大排序的执行过程，注意包含建最大堆（BUILD-MAX-HEAP

5、）的执行过程。7、用主方法求解递归式紧确的渐进界，比如8、写出利用动态规划解矩阵链乘问题的最小代价的递归式，并由此给出维数序列为的最优加全括号的方案。9、会写出利用动态规划解最长公共子序列（LCS）问题的最大长度的递归式，并由此确定和的最长公共子序列。10、对某个数据结构执行一个个操作的序列。如果为2的整数次幂，则第个操作的代价为，否则为1.请用聚集分析来确定每次操作的平摊代价。11、猜测下列递归式的良好渐进界，并用代换法证明你的猜测：(1).的解为；(2).的解为。12、给出红黑树的定义，并由此证明：（1）从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。（2）一棵有n个内节点的

6、红黑树的高度至多为13、给出渐进记号Θ记号、Ω记号和Ο记号的定义，并证明：对任意实常数a和b,其中b>0,，提示：当n足够大时，2/2