1. 算法分析的目的：分析算法的效率。
    数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的和的学科。

2，算法设计的要求：可读性，正确性，健壮性，效率与储存量需求。

  1. 算法的五大特征：有穷性，确定性，可行性，输入输出性。

  2. 图的广度优先常用来实现，深度优先遍历常用 来实现。

5，堆：总是完全二叉树。小顶堆：根总是小于它的左右子节点。大顶堆：根总是大于它的左右子节点。
（14年第六题，16年第20题：堆的判断）

  1. 线性表是典型的线性结构。数据结构的逻辑结构有。

  2. 哈希表的二次(平方)探测再散列：加 1 的平方，加（-1）的平方，加 2 的平方.....(以此类推)。（14年第18题）

  3. 平衡二叉树：该节点的左右子树层数的绝对值相差不超过1。

  4. 算法的空间（时间）复杂度是指：程序运行从开始到结束所需的（时间）存储空间的度量。

  5. 使用 判断有向图是否存在回路。

  6. 出栈顺序：如果A不是一进去就出来，那么B一定在它的左面。若进入的顺序是AB 。（ 16年的选择3题）

  7. 完全二叉树：(例如这样) （14年第六题，16年第20题：堆的判断） 

                                                           1
                          2                                                                  3
          4                          5                                        6                             7

    8 9 10 11 12 13

  8. 哈夫曼树是带权路径最小的树：最小的节点放在最下面，最大的节点放最上面。先将两最小的数放一起，再放进一堆数中比较，再选两个最小的数放到一起。根节点的那层不算，第二层算是第一层，带权路径长度为权值乘层数（以此类推）。
    有N个权值的哈夫曼树（最优二叉树）有（2N-1）个节点。 （14年第八题）

  9. 二叉排序树：左子树上的节点的数都小于根节点的数，右子树上的节点的数都大于根节点的数。使用中序遍历后可得，从小到大的有序数列。

  10. 树变森林，森林变树：左孩子，右兄弟。特指二叉树。 （书上165页）（14年20题） 

    树变森林：将右边的子树变为兄弟节点，放到同一高度。将左边子节点仍为子节点。
森林变树：将兄弟节点（同一平面上的节点）放在右子树上。将子节点仍为子节点放在左子树上。
（森林中的兄弟节点之间的连线去掉）

  11. 二叉树的k层最多有2的（k-1）次个节点。所有节点最多有（(2的k次）-1）个数。 （14年11，14，6题）
    假设有n0个叶子节点，度为2的节点有n2个。那么n0=（n2+1）。
    假设树高度为k，且仅有节点为0或2的节点，那么树的节点数最少有（2k-1）个。
    假设树高度为K，那么树的节点数最少有K。（树的节点数为k，树最高有K深）

  12. 队列是先进先出，只允许一端进入(插入)，另一端输出(删除)。
    栈为先进后出，仅允许一端进入(插入)，且同一端输出(删除)。

  13. 二叉树的遍历：从根节点开始看。例如先序遍历，在一棵树中先判断哪个节点为根结点输出，再判断左子结点。进入左子结点后，再在当前的树中判断哪个为根结点进行输出。如一个树的根左右均遍历完成。那么返回上一层。（书上147页）

  14. 最小生成树：有Kruskal算法和Prim算法。
    Kruskal算法：依次连接权值最小的边，不能形成回路，连接N-1条边。
    Prim算法：选一条边在它的直接相连的边中选取权值最小的边，不能形成回路，连接N-1条边。

  15. 有向拓扑排序：选择一个没有前驱的节点输出，再将此节点及指出的边删去。循环操作直至全部输出或无没有前驱的节点。
    注意：1，若节点全部输出，那么没有图中回路。 

    2，若节点未全部输出，且节点均有前驱节点那么，有回路。
3，可以判断有向图是否存在回路。

  16. 希尔排序：第一次：先选取增量D,D=length/2,分为D组，两两比较。 

     第二次：将D2,D2=D/2,分为D2组，两两比较。以此类推。
    注意：希尔排序不稳定。

  17. 快速排序：选取一个关键点(通常为第一个数)，与最后一个数进行比较，判断是否交换位置，再不断比较向中间收缩。有两指针 i , j。i , j其中必有一个指向关键字，排序完成后，关键点左边都是=关键点（由此分为左右两部分），在比较中数据相同时不交换。（不稳定）
    进行二次快速排序时需要将左右两部分都分别快速排序。

  18. 直接插入排序：将数表中的数一一放入排序中，每一次放入都与其中所有的数进行一一比较。由小到大排序。（书上244页）

  19. 归并排序：将两个有序序列归并成一个有序序列。首先可以将一个单独数看作一个有序序列，两个单独的数进行二路归并。
    两有序序列归并时，一一比较按由小到大排序。 以此类推。

  20. 基数排序：若最大的数为三位数，将8补为008。
    首先将个位按B0--B9来放置，个位是几就放置在相应的B中。个位放置结束后，将相应的数按一横行一横行来取出，
    十位按B0--B9来放置，十位是几就放置在相应的B中。十位放置结束后，将相应的数按一横行一横行来取出。 

                          以此类推，得出排好序的数列。

  21. 简单选择排序：在数表中遍历一遍，选出最小的数放入排序中并在数表中删除此数值。重复此操作。

  22. 折半插入排序：？？？？？？？？？？？？？

  23. 循环队列：队头是front,队尾是rear,循环队列的数组长度为m，队列长度为（rear-front+m）%m。

  24. 若树的度之和为N，那么它的结点数有（N+1）个，总结点数大于总度数。

  25. 深度优先遍历：先找到一个未被访问过的点，再访问它的未被访问过的点。一直到没有未访问的点，返回上一层，以此循环。
    头插：先访问路径代价大的数。
    尾插：先访问路径代价小的数。 （一条路走到死，走不通返回上一层再走）
    广度优先遍历：先找到一个未被访问过的点，再访问它的所有的未被访问过的连接点，再 “依次 ”访问它的所有的未被访问过的连接点，以此循环。

  26. 折半查找：先用两指针确定头节点，尾节点。再找出它的中间位置的数 (若为偶数选取左边位置) 与查找数值比较。
    若查找数值大：以中间位置的后一个数作为头节点，继续循环判断。
    若查找数值小：以中间位置的前一个数作为尾节点，继续循环判断。
    若与查找数值相同：成功查找到。
    如果头节点与指向中间位置的指针重合时，还没有找到查找的数，那么查找的数不存在。
    ！！！[(头节点+尾节点)/2]：找到中间位置。其中的 [ ]是选取前一个数。eg：[2.5]=2。

  27. B-树是平衡多叉树，根结点至少有两个子女。
    中间结点有[m/2]≤ k ≤ m的孩子，[m/2]-1≤ k ≤ m-1的关键字。
    所有的叶子结点都位于同一层。
    B-树的插入，删除操作始终在叶子节点处进行。 

       插入：按照排序树左小右大规则，在叶子节点处插入。
   删除：叶子节点直接删除。
  非叶子节点选择左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字代替它的位置。

    （删除节点＜要合并，插入＞要分裂）
    EG：在一个40阶的B-树中删除一个结点引起的结点的合并，那么它的右子树上的结点数是 : [20] 

                    [根]
            /       \
   [ 左子树]      [ 右 子 树 ]     （它的子树是[m/2]≤ k ≤ m之间）
                   /     |     \
                [子树1]  [2]· · ·[n]          （若删除子树1，会引起合并说明此时的右子树的子树数<[m/2]）
                                                 （说明之前的右子树的子树数目是[m/2]=20）

  28. 平衡二叉树的旋转：LL右单旋转，RR左单旋转，LR先左后右旋转，RL先右后左旋转。
    找到最低不平衡节点下两条线的左右，旋转时带上在连线上的三个点。

  29. 每查找长度为n，就有2的(n-1)次方个元素。折半查找！！！（16年填空4）

  30. 树变为二叉树：树的先序->二叉树的先序，树的后序->二叉树的中序。

  31. 线性表删除一个数据后，之后的每个数据都要向前移一个位置。

  32. 图的所有度数之和=图的边数的2倍。

  33. 线索二叉树：（Ichild，Itag，data，rtag，rchild) 

       对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n+1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。

    如果有指向的指针就放指针，如果没有指向的指针那么就放前后继节点。

  34. 表达式a(b+c)-d的后缀表达式是：abc+d-
    一般表达式均为中序，左右根。
    中序： [ a * ( b+c ) ] - d ； a * ( b + c ) ； （ b + c） 

                          左          根  右           左   根      右                        左    根   右
   后序：          a*( b+c )       d ， -       ；      a  ，( b + c )，*        ；   b  ，  c ， +
                左           右  根                左         右       根             左      右    根

    因此：后缀表达式为 a b c + * d -

  35. 满k叉树的性质：
    假设有e层，第e层上的节点数就是叶子节点的个数k的（e-1）次，树的总节点数k的（e-1）次/k-1。
    非叶子节点数nx=【k的（e-1）次/k-1】-n0，又因为kn0=k的e次，n0=（k-1）nx+1。

  36. 用筛选法建堆，堆均为完全二叉树。
    调整堆由下向上调整。首先找到最后一个叶子节点，找它的父节点。与它的父节点进行比较调整。
    所以用筛选法查找关键字从最后叶子节点的父节点开始。

  37. 建堆，先将所有的元素按完全二叉树的形式输入，再进行调整。