数据结构的概念：数据之间的内在联系。要了解3种数据结构的概念：逻辑结构；物理结构；基本操作。
例如：栈和队的逻辑结构都是线性的，但她们的基本操作不同，就是不同的数据结构。
常见的数据结构的分类：线性关系；集合关系；一对多；多对多（图）；
什么事物理结构（应该有印象）。 ;$* Ai)L
算法设计时要用类PASCAL,类C，不要用C++. fM5)`~
算法分析的常用方法：事前分析；事后统计。 h-ZB}01BQ.
时间/空间复杂度的概念。空间是算法运行时资源占用情况。 Fb1@4mn
时间复杂度：最坏，最好，平均。 5.'r~+_;};
例如：归并排序都是O（n*logn），最好，最怀，平均都是一样的 cfdBbL*
插入排序：最好为O(n) ,最坏为O（n2） aB"AGYIvgP
线性表：逻辑关系，各种基本操作，两个有序表的归并。 6sql`}uW<
线性表的顺序存储：线性表的操作在顺序表中的实现。 Jz]X7l5 Z
例如：1。插入与删除和插入的位置与表长有关。 M^qw d|
2．在一个长为n的表中插入一个元素的平均复杂度，要有插入位置的概率分布表达式，即给出此表达式，算平均复杂度。 $P$}v R[
线性表的链式存储：链表的基本操作：2个有序表的归并。 j # GZ]O@
例如：1。把链表就地逆置：一个指针P指向当前逆置好的一系列节点的最后一个节点，取P的NEXT插入队头。 eJZu9CB
2．三色问题：节点红黄蓝在链表上无序排列，把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针P，头指针S，S.NEXT为Q，S后接红节点。若P为红，插入S后。若P为黄，插入Q后。若P为兰，不动。然后P向后移，求下个。 ^%r]&s^,o
注：要了解单链表的插入，删除在什么位置操作。 ZdZ<sH W1
静态链表（数组表示）：不能象单链表那样不受限增加节点。 U 0mlsKh
循环链表：如果表示队列，用它最好。P指向队尾。好处：用于优先队列中。 R% pfZ8
双向链表：单链表中只有P指向当前节点，不能删除P。因为无法找到P 的前驱。而双向链表可以。注意指针变化情况。 !;>Vn7Xv~
栈：后进先出。基本操作：出入栈，取栈顶。在顺序表和链表上的实现；出栈序列是否合理？ S-#8\.#_
例如：入栈序列是1，2，，，n，则出栈序列有几种？（即n个节点的二叉树的个数。因为树的先序是1，2，，，n）。 .yly!$
栈与递归：见我给你寄过去的手写体。 =j @gk ]
队列：先进现出。链队列，循环队列。 w^pkzrj
例如：1。把从队头开始的第i个元素删除：队列 只有出队入队，不能直接删除。要先将前i-1个出队，入队尾；i出队；i+1以后的出队入队尾。 TKdPi 0$
2．队列逆置（队头与队尾交互）：出队入栈；后出栈入队。 5^ r(D
注意：这些结构的基本操作有什么，不能混。 yk3pzS ^3
循环队列：队头指针和队尾指针。记住队空和满的标志。见手写版。 7}EKi tR
串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为O（m）,要会证明她们。简略证明见手写版。 io>j&X](
2．求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。具体证明估计不会考。 ob ^>e`&E8
17．数组：存储位置与下标对应。特殊数组（对称，上三角等）。 <FOM(%IrOg
三元组，稀疏矩阵（求逆）。计数技术，在设计算法中的应用。 2AHaXq0be
十字链表不考。 I&;dHy<
广义表：基本概念，存储结构（二叉链表）。应用不考。 Bkt@ rKE
广义表递归算法了解。 FxU=[q
二叉树的性质（熟）。 c[R3xcyt]
存储结构：二叉链表，三叉链表。 mU7X2K'f
遍历：中，先，后。 按层遍历：用辅助队列。例如求K层有多少节点。 Vc^J ' [
线索二叉树：中序（先后序不考）。线索中的插入删除不考。 F%0S@]c7
树与森林的遍历：树的先根与后根（分别对应相应二叉树的先序，中序）。森林的先序和后序（分别对应相应二叉树的先序，中序）。 h& kR]kMl
树与二叉树一一对应。 FfNl@t (?[
由先序中序可以唯一确定二叉树。而由先序后序不能。例子见手写版。 JI bs5u$6
二叉树可以为空，树不能为空（树为有根有序树）。 mS>0cM"/
树与等价：例如：判断一个元素是否属于一个特定的集合，可看这个节点是否在此树上。看两个节点是否在一个强联通分量，看他们是否在一棵树上。求KRUSCAL算法（最小生成树集合）。 Aq^C[MS
哈夫曼：前缀码。它是加权外部路径长度最小的二叉树。它是严格二叉树，无度为1的点。节点个数＝2×叶节点－1。 构造，编码。 |X|K Sfm
扩展：用0，1，2三进制编码：元素个数为奇。N个元素K进制：K-1整除N-1。否则增加概率为零的元素。 5RZm+{o X)
注意11。6节的最佳归并。 uG ?0vj
树的计数：记结论。 /."94}@Ot
N个操作符或N个括号，为操作符加括号的情况数目。 V'-k>!&
N＋2个顶点的凸多边形，他的不同三角剖分的个数。 \,[)'[T{
a1,a2,,,an, ai=1/-1,任意前k个ai之和大于等于0，求不同组合数。 ~b? 3=>&h
见手写版。 S-TZfe%YHj
图：存储结构（针对有向图和无向图）。邻接表中边节点中存储的信息不是顶点内容而是顶点序号。 JET2UXC b
图的遍历：深度优先借助于栈；广度优先借助于队列。 EHI*?7f^ !
图的连通：深度优先搜索一次。 Sb}8* 4X
有向图的强联通分量（不重要）。 &:Y5<pqu
最小生成树：PRIM算法，KRUSCAL算法。写算法，要用到树与等价类。（SEL-UNION算法）。她们的时间复杂度。若用优先队列，时间复杂度降低。 B'%6.g'
关节点，关键路径：深度优先数。 b& M'o]
有向无环图：拓扑排序。用邻接矩阵保存它，则入度为0的列全为0。去掉该节点，必还有节点入度为0，所以调整矩阵，可得上三角矩阵。 3` xmZapVX
DAG图等价为拓扑有序。拓扑排序算法：2个共享链栈，利用空间。 B6W%_F
若得逆拓扑序，不用栈而用队列；也可以增加一个栈。也可以用深度优先搜索，找最深得那个节点最先把它输出。 Z\1$4, ]
最短路径：单源（有向图，且权值>=0是DIJISTRU算法的适应范围）。对无向图，可看成2个方向权值一样。例子见手写版。 + 9 3F>9
问：DIJISTRU算法能否求图的最小生成树？不能。 %cC{hggV
打印最短路径，时间O（n2），空间O（n），可以用DIJISTRU算法得到集合的同时，记录每个节点前面那个元素，一个一个向前找。 (GQFm .
二部图：一个图是否是二部图？时间是O（n）。用等价类：一个边的两点分属于不用等价类（估计不会考太深）。 wj!o<1I!
伙伴系统，边界标识（要看）。无用单元收集不考。 I(E*oz$
顺序查找时间（最坏，平均）。有序表查找，二分查找，折半查找（判定树，树的高度，平均检索长度（在成功和不成功时的不同情况））。 "3j^}<
静态树表不考，静态次优不考。 dMyatc\c
索引顺序表：概念。 )V Zn[Ca
动态查找：二叉排序树：中序遍历有序，先序无序。给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。 *a|zBq\
查找长度的量级。 Ik~*I(?^
平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。 w 1W U9 .
M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。 IfQeke 0
B＋树的概念。 键树。 _ #.qv2W
哈希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺序结构和链结构的完美结合。 H uve2w$W
查找长度：1。探测次数（包括最后一次比较为空的次数）。 V[?7mF/%
2．关键字比较次数（不包括最后一次为空的）。 Sd dk &
37．内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。 $Fm3SWHZ
基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。 3dXQ~^
基数排序利用关键字本身的值，而其他基于比较。 ?L%'[8_7Y
找最大和最小值的时间[3/2n]-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。 0ueMxJ3
找最大和次大值：可以调整堆，也可以记下比较 |
收藏
点赞!
反对!