[toc]
题型
- 判断题，对了得分，错了倒扣
- 简答题
- 概念、什么是平衡二叉树、什么是有向连通图
- 给一个AVL树、SPlay，画出计算过程
- 给一个函数判断是不是递归、这个递归有没有什么问题
- 是否少了边界条件或者递归条件
- P是不是NP的子集、你能解释是为什么吗？分别说出他们的概念
- 解释什么是Worse-case和平均情况、什么时候用WC什么时候用AC、AC和平均分摊之间有什么区别
- 排序算法的basic操作
- 给一个数据写一下最近邻
- 给一个图写出MST
- 红黑树的判断、构造一个红黑树（只要写过程、不用实现）
- splay tree 的时间复杂度
Lecture 1-2
P19.Optimizing and heuristic algorithms
- 最优解（优化算法）和启发式的区别、原因
P20.Why heuristics?
- 为什么选择启发式
P22.Constructive heuristics
- 均匀分布，在某个范围内等概率生成某些数
- 步骤、过程，step0-2、了解一下流程图
P26-.Huffman’s algorithm
- 哈夫曼编码、文字压缩
P29.Graph
- 图的定义
P31.Binary tree
- 什么是二叉树
P35.Tries
- 什么是Tries
P36.Definition - Prefix
- 什么是前缀、后缀
- 给出字符串、能够写出前缀后缀、注意不止一个、是有一系列的前缀
P42-.Huffmans’s algorithm
- 给一个例子，然后画出过程
P58.Neighborhood search
- 用来求解背包问题、把背包问题描述成数学的形式、自己写一遍算法、写出计算步骤
- 1.x1
- 2.求解x2（根据已知方法）写计算过程
P89.Tabu search （不确定会考）
- 哪些要、哪些不要
P119.Mergesort
- 先分解在合并排序的过程
- 写出每步步骤
P133.Dynamic Programming
- 动态规划找出最优解、相比贪心算法的优点
P138
- 不选、选、画出图、动态规划要掌握该图
- 背包问题的动态规划图
Lecture 3-4
P4-
- 连通图、有向图、计算出度入度
P8.Cycle in directed graph
- 回路存在即不能进行拓扑排序
P10.Connected undirected graph
- 概念判断、什么是强连通图、连通图、判断这个图是不是强连通的、判断是不是完全图
- 完全的无向图里面的边数的关系
P15.Tree
- 什么是树、判断是不是树
P18.Graph representation
- 图的两种存储方式、把选择的那一种画出来
- 各自的优缺点
- 矩阵索引快，但是空间消耗大
- 链表慢，但是节省空间，没有无效存储、多次搜索（不知道是否正确具体参考ppt？）
P33.Prim’s algorithm
- 根据这两个算法、画出MST、会画就可以了
P35.Topological ordering
- 找出拓扑排序、并且解释为什么不能有环、彼此是彼此的依赖结点
Lecture 5-6
P2.What is complexity analysis?
- 什么是算法复杂度
P4-5.Basic operations of an algorithm & What is a basic operation?
- 不同算法的。。。排序中的遍历过程、merge比较
P7.Complexity as a function of the input - Examples
- 常见算法的复杂度、最好的情况、最坏的情况、在什么情况下最好
P20.Average and Worst case analysis
- 掌握最坏的情况、不用掌握平均的
P23.Relative growth rate of functions
- 给出一个表达式，可以用Big O的形式表达出来、去掉常数项和低次项还有系数
P29.Example: O(n3), Ω(n3), and Θ(n3)
- 上下界、O的上界、Ω的下界、Θ的确界
P36.P and NP
- NP中N 的含义、NP是否等于P、一般是不等、说明原因
P46.How to show that a problem is N P complete I
- 过于具体、可以简化
P47.How to show that a problem is N P complete II
- 具体证明步骤、会证明
- 把第二条分成两点
P48.Amortized analysis - Initial example
- 只需要掌握基本概念、 a sequence of operations是关键词
P53.Amortized vs average-case analysis
- 两者并不一样、AC是发生的概率，并不考虑多个步骤再平均
Lecture 7-8
P4.Binary tree
- 二叉树的基本操作
P5.Binary search tree
- 什么是balance search tree、大小关系、给出一个不平衡的->平衡
P20.Tree balance
- 如何判断一棵树是否平衡
P29.Inserting
- 要会操作、和splay tree 两个考一个
P30.Splay trees
- 考步骤、会插入删除
P58.Red-black trees
- 掌握四条定义、会判断是否是红黑树
最后一次复习内容
splay tree （肯定考）
- 旋转目的是把新加入的节点放到根节点，使得方便。。。
- 理由：因为新加入的节点很可能再次使用
- 旋转方式：
[图片上传失败...(image-462672-1547515591948)]
红黑树
-
判断
- Each node is colored either red or black.
- The root and leaves(NIL's--叶子节点标示) are black.
- If a node is red, its children must be black.
- Every path from a node to a leaf must contain the same number of black nodes.
- = Num_black(node)
-
构造
- Self-balancing BST
-
插入
新插入的是红色，保证第四条，并且保证BST性质
[图片上传失败...(image-8296fb-1547515591949)]-
四种情况
- z = root
- 节点变为黑色
- z.uncle = Red
- Grandparent、Parent、Uncle 颜色转成相反的颜色
[图片上传失败...(image-5e4ec7-1547515591949)]
- Grandparent、Parent、Uncle 颜色转成相反的颜色
- z.uncle = Black(triangle)
- 旋转Parent节点，变成线性
[图片上传失败...(image-921444-1547515591949)]
- 旋转Parent节点，变成线性
- z.uncle = Black(line)
- 旋转Grandparent节点，Grandparent、Parent 颜色转成相反的颜色
[图片上传失败...(image-1a34ff-1547515591949)]
- 旋转Grandparent节点，Grandparent、Parent 颜色转成相反的颜色
- z = root
suffix tree
-
suffix 有很多
- s = abaaba$
- $
- a$
- ba$
- aba$
- aaba$
- baaba$
- abaaba$
- s = abaaba$
-
suffix trie 树
- 可以得到三个信息
- 有没有
- 有几个
- 分别从哪边开始
[图片上传失败...(image-1f6fe5-1547515591949)]
- 可以得到三个信息
-
两个字符串判断公共的子串
- 分别先往子串后面加上富豪
- 最后标上每一层X or Y or XY，找XY层数最多的，字符最长的，把边读出来就是最长子串
[图片上传失败...(image-43362e-1547515591949)]
[图片上传失败...(image-e239eb-1547515591949)]
