《《算法基础》复习提纲.doc.pdf》由会员分享，可在线阅读，更多相关《《算法基础》复习提纲.doc.pdf（8页珍藏版）》请在三一文库上搜索。
1、算法基础复习提纲 1引言(chi) 1.什么是算法及其特征 2.问题实例和问题规模 2算法初步(ch2) 1.插入排序算法 2.算法复杂性及其度量 (1)吋间复杂性和空间复杂性； (2)最坏、最好和平均情形复杂性; 3.插入排序的最坏、最好和平均时间 4.归并排序算法及其时间复杂性 3函数增长率(ch3) 1.渐近记号O、Q、0的定义及其使用 2.标准复杂性函数及其大小关系 3.和式界的证明方法 4递归关系式(ch4) 1.替换法 (1)猜测解9数学归纳法证明； (2)变量变换法； 2.迭代法 (1)展开法； (2)递归树法； 3.主定理 5概率分析(ch5) 1 ?雇佣问题及其随机算法 (
2、略) 2.序列随机排列的两种方法及其复杂性 3.在线雇佣问题及其概率分析( 略) 6堆排序(ch6) 1堆的概念和存储结构 2.堆的性质和种类 3.堆的操作：建堆；整堆； 4.堆排序算法和时间复朵性 5.优先队列及其维护操作 7快速排序(ch7) 1.快速排序算法及其最好、最坏时间和平均时间 2.随机快速排序算法及其期望时间 8线性时间排序(ch8) 1 ?基于比较的排序算法下界： (nlogn) 2.计数排序适应的排序对象、算法和时间 3.基数排序适应的排序对彖、算法和时间 4.桶排序适应的排序对象、算法和时间 9中位数和顺序统计(ch9) 1.最人和最小值的求解方法 2.期望时间为线性的选
3、择算法 3.最坏时间为线性的选择算法及其时间分析 10红黑树(chl3) 1 . 红黑树的定义和节点结构 2.黑高概念 3.棵n个内点的红黑树的高度至多是21og(n+l) 4.左旋算法 5.插入算法、时间、至多使用2次旋转 6.删除算法、时间、至多使用3次旋转 11数据结构的扩张(chl4) 1.动态顺序统计： 扩展红黑树，支持选择问题( 给定Rank求相应的元素 )，Rank问题(求元 素x在集合中的Rank) (2)生成全排列； Stranssen矩阵乘 (1)多段图规划； (3)最大了段和； (5) 0-1问题求 (1)节点结构的扩展； (2)选择问题的算法； (3) Rank问题的算
4、法； (4)维护树的成本分析； 2.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理( 略) ； 3.区间树的扩张和查找算法(略) 12递归与分治法 1.递归设计技术 2.递归程序的非递归化 3.算法设计 (1)最近点对； (3)大整数乘法； 13动态规划(chl5) 1.方法的基本思想和基木步骤 2.动态规划和分治法求解问题的区别 3.最优性原理及其问题满足最优性原理的证明方法 4 . 算法设计 (2)矩阵链乘法； (4)最长公共了序列； (6)凸多边形最优三角剖分问题; 14贪心算法(chl6) 1.方法的基本思想和基本步骤 2.贪心算法的止确性保证：满足贪心选择性质 3.贪心算法与动态
5、规划的比较 4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质 5 ?算法设计 (1)小数背包；(2)活动安排； (3)找钱问题；(4)最优装载问题； (5)单源最短路径； 15回溯法 1? 方法的基本思想和基本步骤 2.回溯法是一种深度遍历的搜索 3.术语：三种搜索空间，活结点，死结点，扩展结点，开始结点，终端结点 4.两种解空间树和和应的算法框架 5.算法设计： n后问题； (3)排列生成问题； 符号三角形问题 ; (2) 0-1 背包； (4) TSP 问题； 图的 m 着色问题 ; 16分支限界法 1方法的基本思想和基本步骤 2. 与冋溯法的区别 3 ?活结点的两种扩展方式 4
6、.0-1背包问题的搜索 :FIFO队列和优先队列 5.算法设计 (1)0-1背包问题；装载问题 (略)； (3)单源最短路径问题； 17数论算法(ch31) 1 -gcd(a, b)及其表示成a, b线性组合方法 2. Euclid ,s Alg. 的运行时间 3.线性模方程的求解方法 4.中国余数定理及线性同余方程组的求解 18排序网络(ch27) 1.比较网络 2.0?1原理 3.双调排序网络 4.合并网络 5.排序网络 算法基础考试题型 一、填空题 ( 选择题 ) 1.给定一个由 11 个活动组成的活动集合，各个活动的起始时间和结束时间如下表所示, 则 该活动集合中最大兼容活动了集的元素
7、个数为_ : ? 1 12 345 6 7 8 9 1011 Si 1 3 0 535 688212 fi 45 6 7 8 9 101112 1314 2.任意一个比较排序算法在最坏情况下都需要做 _ 次比较。由于堆排序和合并排序 的运行时间上界是 _ , 所以它们都是渐近最优的比较排序算法； 3.分治法是一种常用的算法设计策略，包括 _ 、_ 、_ 三个步骤。 基于分治法设计得到的两个n 位大整数的乘法运算的算法运算时间为_ ; 4.基数排序算法是一种按位排序算法，它按 _ 进行排序，并R 要求按位排序 算法是稳定的。给定个位数，每一个数位可以取k 种可能的值，则基数排序算法能 以 _ 的
8、时间正确地对这些数进行排序； 5.有 4个算法的时间复杂度分别为0（/）、0? 初）、 00）、。（心则它们Z 间的大小关 系 为 _ ; 6.可以利用动态规划法求解的问题必须满足两个性质： _ 和 _ O 二、简答题 （25分） 1.令。=177“ = 78，请填充下表给出利用扩展欧几里得算法求解gcd（177, 78）的完整计 算 过程。 答: ab _a/b _ d x y 17778 2.对于 0-1 背包问题和小数背包问题，什么问题可以用贪心法求解？其贪心策略是什么？ 3.计数排序算法的输入盂要满足什么条件？桶排序算法的输入需要满足什么条件呢？它 们的时间复杂度是多少？ 4.如下图所
9、示，给定一棵二叉查找树，请: 画出对结点 x 进行左旋操作得到的新二叉查找 树 三、计算证明题 1.求出下面各题运行时间TS)的渐近阶： T(n) = 4T(n/2) + n 2.求出方程 35x = 10 (mod 50)的所有解。 四、综合题 1.设，.n和 Yln 为两个数组，每个都包含n个已排好序的数。给出一个求数组X 和 Y 中所有2n个元素的中位数的、0(妙)时间的算法。 2.给定一个数组A = , (1) 请画出该数组的二义树表示形式； (2) 利用建堆算法 BUILD-MAX-HEAP把数组 A 造成一个最大堆，其时间复杂度多大? 请画出最人堆的二义树表示形式； (3) 结点 10 在大根堆中的高度是多少？