1、数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。
① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 ② 线性结构：结构中的数据元素之间存在一对一的关系。 ③ 树型结构：结构中的数据元素之间存在一对多的关系。
④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。 2、顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、C语言中用带指针的结构体类型来描述 typedef struct Lnode
{ ElemType data; /*数据域，保存结点的值 */ struct Lnode *next; /*指针域*/ }LNode; /*结点的类型 */ 4、循环队列为空：front=rear 。
循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。
5、性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。 性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。
性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。 完全二叉树的特点：若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1
层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。
性质4：n个结点的完全二叉树深度为：?㏒2n? +1。
性质5：若对一棵有n个结点的完全二叉树(深度为└㏒2n┘+1)的结点按层（从第1层到
第?㏒2n? +1层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结点：
⑴ 若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是 ?i/2? 。 ⑵ 如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。 ⑶ 如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。
6、线索二叉树：设一棵二叉树有n个结点，则有n-1条边(指针连线) ， 而n个结点共有
2n个指针域(Lchild和Rchild) ，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。
7、Huffman树：具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵，但在所有的
这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树) 。
8、完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e ?[0，n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。
完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e?[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。
生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树 关于无向图的生成树的几个结论：
1) 一棵有n个顶点的生成树有且仅有n-1条边；
2) 如果一个图有n个顶点和小于n-1条边，则是非连通图； 3) 如果多于n-1条边，则一定有环； 4) 有n-1条边的图不一定是生成树。 9、最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。 最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n个城市之间最多可以建n?(n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低?
10、工程完成最短时间：从起点到终点的最长路径长度(路径上各活动持续时间之和) 。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的
关键。
11、查找方法比较
ASL 表结构
顺序查找 最大
有序表、无序表 顺序存储结构
折半查找 最小 有序表
分块查找 两者之间 分块有序表 顺序存储结构
存储结构
线性链表
顺序存储结构
线性链表
12、在随机情况下，二叉排序树的平均查找长度ASL和㏒(n)(树的深度)是等数量级的。 二叉排序树(Binary Sort Tree或Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。
(1) ：若左子树不为空，则左子树上所有结点的值(关键字)都小于根结点的值； (2) ：若右子树不为空，则右子树上所有结点的值(关键字)都大于根结点的值； (3) ：左、右子树都分别是二叉排序树。
结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。 ⑴：左子树和右子树深度之差的绝对值不大于1； ⑵：左子树和右子树也都是平衡二叉树。
平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。
平衡二叉排序树上进行查找的平均查找长度和㏒2n是一个数量级的，平均时间复杂度为O(㏒2n)。
四种平衡化旋转，其正确性容易由“遍历所得中序序列不变”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。 14、一棵m阶B_树，或者是空树，或者是满足以下性质的m叉树： ⑴ 根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；
⑵ 除根结点外，所有非终端结点至少有?m/2?棵子树，至多有m棵子树； ⑶ 所有叶子结点都在树的同一层上； ⑷ 每个结点应包含如下信息：
(n，A0，K1，A1，K2，A2，… ，Kn，An)
其中Ki(1≤i≤n)是关键字，且Ki 因此有： h≦1+ ㏒s((n+1)/2)=1+㏒?m/2?((n+1)/2) 即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ ㏒?m/2?((n+1)/2) 。 15、m阶B+树。 它与B_树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是： ⑴ 若一个结点有n棵子树，则必含有n个关键字； ⑵ 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接； ⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 16、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成：addr(ai)=H(ki) ，其中i是表中一个元素，addr(ai)是ai的地址， ki是ai的关键字。 哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。 哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。 例1 ：设散列表长为7，记录关键字组为：15, 14, 28, 26, 56, 23，散列函数：H(key)=key MOD