《算法基础》复习提纲.doc

《《算法基础》复习提纲.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法基础》复习提纲1引言(ch1)1.什么是算法及其特征2.问题实例和问题规模2算法初步(ch2)1.插入排序算法2.算法复杂性及其度量(1)时间复杂性和空间复杂性；(2)最坏、最好和平均情形复杂性；3.插入排序的最坏和平均时间4.归并排序算法及其时间复杂性3函数增长率(ch3)1.渐近记号O、Ω、θ的定义及其使用2.标准复杂性函数及其大小关系3.和式界的证明方法4递归关系式(ch4)1.替换法(1)猜测解à数学归纳法证明；(2)变量变换法；2.迭代法(1)展开法；(2)递归树法；3.主定理5概率分析(ch5)1..序列随机排列的两种方法及其复杂

2、性6堆排序(ch6)1堆的概念和存储结构2.堆的性质和种类3.堆的操作：建堆；整堆；4.堆排序算法和时间复杂性5.优先队列及其维护操作7快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间2.随机快速排序算法及其期望时间8线性时间排序(ch8)1.基于比较的排序算法下界：Ω(nlogn)2.计数排序适应的排序对象、算法和时间3.基数排序适应的排序对象、算法和时间4.桶排序适应的排序对象、算法和时间9中位数和顺序统计(ch9)1.最大和最小值的求解方法2.期望时间为线性的选择算法3.最坏时间为线性的选择算法及其时间分析10红黑树(ch13)

3、1.红黑树的定义和节点结构2.黑高概念3.一棵n个内点的红黑树的高度至多是2log(n+1)4.左旋、右旋算法5.插入算法、时间、至多使用2次旋转6.删除算法、时间、至多使用3次旋转11数据结构的扩张(ch14)1.动态顺序统计：扩展红黑树，支持①选择问题(给定Rank求相应的元素)，②Rank问题(求元素x在集合中的Rank)(1)节点结构的扩展；(2)选择问题的算法；(3)Rank问题的算法；(4)维护树的成本分析；2.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理3.区间树的扩张和查找算法12递归与分治法1.递归设计技术2.递归程序的非递

4、归化3.算法设计(1)最近点对；(2)生成全排列；(3)大整数乘法；(4)Stranssen矩阵乘法；13动态规划(ch15)1.方法的基本思想和基本步骤2.动态规划和分治法求解问题的区别3.最优性原理及其问题满足最优性原理的证明方法4.算法设计(1)多段图规划；(2)矩阵链乘法；(3)最大子段和；(4)最长公共子序列；(5)0-1问题求解；14贪心算法(ch16)1.方法的基本思想和基本步骤2.贪心算法的正确性保证：满足贪心选择性质3.贪心算法与动态规划的比较4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质5.算法设计(1)小数背包；(

5、2)活动安排；(3)找钱问题；(4)最优装载问题；(5)单源最短路径；15回溯法1.方法的基本思想和基本步骤2.回溯法是一种深度遍历的搜索3.术语:三种搜索空间,活结点,死结点,扩展结点,开始结点,终端结点4.两种解空间树和相应的算法框架5.算法设计：(1)n后问题；(2)0-1背包；(3)排列生成问题；(4)TSP问题；(5)符号三角形问题;(6)图的m着色问题；16分支限界法1方法的基本思想和基本步骤2.与回溯法的区别3.活结点的两种扩展方式4.0-1背包问题的搜索:FIFO队列和优先队列5.算法设计(1)0-1背包问题；(2)装载问题(3)单

6、源最短路径问题；1.算法基础考试题型一、填空题（选择题）1．给定一个由11个活动组成的活动集合，各个活动的起始时间和结束时间如下表所示，则该活动集合中最大兼容活动子集的元素个数为；i1234567891011si130535688212fi45678910111213142．任意一个比较排序算法在最坏情况下都需要做次比较。由于堆排序和合并排序的运行时间上界是，所以它们都是渐近最优的比较排序算法；3．分治法是一种常用的算法设计策略，包括、、三个步骤。基于分治法设计得到的两个n位大整数的乘法运算的算法运算时间为；4．基数排序算法是一种按位排序算法，它按

7、进行排序，并且要求按位排序算法是稳定的。给定n个d位数，每一个数位可以取k种可能的值，则基数排序算法能以的时间正确地对这些数进行排序；5．有4个算法的时间复杂度分别为O(n2)、O(nlgn)、O(nn)、O(n),则它们之间的大小关系为；6．可以利用动态规划法求解的问题必须满足两个性质：和。二、简答题（25分）1．对于0-1背包问题和小数背包问题，什么问题可以用贪心法求解？其贪心策略是什么？2．计数排序算法的输入需要满足什么条件？桶排序算法的输入需要满足什么条件呢？它们的时间复杂度是多少？3．如下图所示，给定一棵二叉查找树，请:画出对结点x进行左

8、旋操作得到的新二叉查找树xy11918141217192220三、计算证明题1．求出下面各题运行时间T(n)的渐近阶：四、