1数据（Data ）:是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并 被计算机程序处理的符号的总称。

数据元素（Data Element ）:是数据的基本单位，在程序中通常作为一个整体来进行考虑和 处理。

一个数据元素可由若干个 数据项（Data Item ）组成。

数据项是数据的不可分割的最小单位。

数 据项是对客观事物某一方面特性的数据描述。

数据对象（Data Object ）:是性质相同的数据元素的集合，是数据的一个子集。

如字符 集合 C={ ‘ A , 'B'。

，' C,…}数据结构（Data Structure ）:是指相互之间具有（存在）一定联系（关系）的数据元素的集合。

元素 之间的相互联系（关系）称为逻辑结构。

数据元素之间的逻辑结构有四种基本类型，如图 1-3所示。

① ② ③ ④ 2、链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑 结构，而算法的实现依赖于所采用的存储结构。

在C 语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

3、 C 语言中用带指针的结构体类型来描述 typ edef struct Lnode { ElemType data;/*数据域，保存结点的值struct Ln ode *n ext;/* 指针域 */}LNode;/*结点的类型 */4、 循环队列为空：fron t=rear 。

循环队列满：（rear+1）%MAX_QUEUE_SIZE =front 。

5、 性质1:在非空二叉树中，第i 层上至多有2i-1个结点（i 仝1）。

性质2：深度为k 的二叉树至多有2k-1个结点（k 仝1）。

性质3:对任何一棵二叉树，若其叶子结点数为 n 0,度为2的结点数为n 2,则n o = n 2+1。

一棵深度为 k 且有2k-1个结点的二叉树称为满二叉树（Full Bin ary Tree ）。

完全二叉树的特点：若完全二叉树的深度为k ,则所有的叶子结点都出现在第k 层或k-1集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

线性结构：结构中的数据元素之间存在一对一的关系。

树型结构：结构中的数据元素之间存在一对多的关系。

图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

顺序结构：数据元素存放的地址是连续的 ；*/层。

对于任一结点，如果其右子树的最大层次为I，则其左子树的最大层次为I或1+1。

$ ◎奁-I I -①①还原成森林图6-22二义树还原成森林的过程6、 线索二叉树：设一棵二叉树有 n 个结点，则有n-1条边（指针连线），而n 个结点共有2n 个指针域（Lchild 和Rchild ），显然有n+1个空闲指针域未用。

则可以利 用这些空闲的指针域来存放结点的直接前驱和直接后继信息。

7、 Huffman 树：具有n 个叶子结点（每个结点的权值为 w i ）的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵 WPL 值最小的树，称这棵树为Huffman 树（或 称最优树）。

性质5:若对一棵有n 个结点的完全二叉树（深度为 哋2n 」+1）的结点按层（从第1层到 第吨2n +1层）序自左至右进行编号，则对于编号为i （1 W i w n ）的结 点：若i=1：则结点i 是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是 i/2 。

如果2i>n :则结点i 为叶子结点，无左孩子；否则，其左孩子结点编号是 2i 。

如果2i+1>n :则结点i 无右孩子；否则，(DI'片\致①①、•、't (?)宀扫）淼林（h ）淼林中每操树 对应的二叉树（c ）森林对应的二叉树 图6-21森林转换成二叉榊的过程j'、/(© 0 (M / * /y(町二义树（时去连线后)(\1W7-2Z 搖Sunk 汕 ff 注构追斌小生峨M 的过*V@ @ L?)③®⑧③③(⑥②③ (壬)(工 厂Hi第-步-口:a <7!I £8> (Th$ A ③③e II图矗上亏lluffnu»nW 的掏造过稈U) CS'f (j<* -----厂〔 ③G) d).r.n).些•一、1< T R )〔/■\i0 O Cs'ii j i •厂厂mn(3) ◎③ d)8、完全无向图：对于无向图，若图中顶点数为n 具有n(n-1)/2条边的无向图称为完全无向图。

完全有向图：对于有向图，若图中顶点数为 n ，用e 表示弧的数目，则e [0，n(n-1)]。

具有n(n-1)条边的有向图称为完全有向图。

生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部个顶点和只有足以构成一棵树的 n-1条边，称为图的生成树关于无向图的生成树的几个结论：1) 2) 3) 4)，用e 表示边的数目， 则e [0, n(n-1)/2]。

一棵有n 个顶点的生成树有且仅有 n-1条边；如果一个图有n 个顶点和小于n-1条边，则是非连通图； 如果多于n-1条边，则一定有环； 有n-1条边的图不- 1定是 生成树。

9、最小生成树(Minimum Spanning Tree):带权连通图中代价最小的生成树称为最小生成树。

最小生成树在实际中具有重要用途，如设计通信网。

设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。

n 个城市之间最多可以建n (n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低 ?3-=<、1 ------ ! I一 (<■> J11H7-21 rc pE.HQ tr小G 皿Hf 的i?lV('' 1))小3丿yE V. 115 jT —:―'<|*>EJi7-；5带如向團及购離阵11、查找方法比较12、在随机情况下，二叉排序树的平均查找长度 ASL 和log (n)(树的深度)是等数量级的。

二叉排序树(Bi nary Sort Tree 或Bin ary Search Tree)的定义为：二叉排序树或者是空树， 是满足下列性质的二叉树。

(1) :若左子树不为空，则左子树上所有结点的值 (2) :若右子树不为空，则右子树上所有结点的值 (3) :左、右子树都分别是二叉排序树。

结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。

13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。

⑴：左子树和右子树深度之差的 绝对值不大于1;顺序查找 折半查找 分块查找ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表顺序存储结构顺序存储结构!厂〕r fvO©(v ＞输出Vi图几23有向图的拓扑卅JP 过程10、工程完成最短时间：从起点到终点的最长路径长度 度最长的路径称为关键路径，关键路径上的活动称为关键活动。

(路径上各活动持续时间之和)。

长 关键活动是影响整个工程的/• 20 60 7 10 6500 00 罚 70 00ffi 8 g30 40 Qo ao B 008 CO 35 ™00QO TO 20 QO DGh 15 80 ™ ™关键。

存储结构顺序存储结构线性链表线性链表或者(关键字)都小于根结点的值; (关键字)都大于根结点的值;⑵：左子树和右子树也都是平衡二叉树。

平衡因子(Balanee Factor):二叉树上结点的左子树的深度减去其右子树深度称为该结 点的平衡因子。

平衡二叉排序树上进行查找的平均查找长度和log O(log 2n)。

四种平衡化旋转，其正确性容易由 遍历所得中序序列不变”来证明。

并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a 为根结点的平衡二叉排序树的深度相同。

所以，在平衡二叉排序树上因插入结点而失衡， 仅需对失衡子树做平衡化旋转处理。

m 叉树：根结点或者是叶子，或者至少有两棵子树，至多有 m 棵子树； 除根结点外，所有非终端结点至少有 m/2棵子树，至多有 m 棵子树；所有叶子结点都在树的同一层上；每个结点应包含如下信息：(n, A o , K 1 , A 1 , K 2, A 2,…，K n , A n )其中氏(1 w i 是关键字，且 K i <K +1 (1 W i 琲)n A i (i=0, 1,…，n)为指向孩子结点的指针，且 A i-1所指向的子树中所有结点的关键字都小于K , A i 所指向的子树中所有结点的关键字都大于K i ； n 是结点中关键字的个数，且m/2 -1 w n, n+1为子树的棵数。

根据m 阶B_W 的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外, 所有非终端结点至少有m/2棵子树，…，第h 层上至少有m/2 h-2个结点。

在这些结点中： 根结点至少包含1个关键字，其它结点至少包含 m/2 -1个关键字，设s= m/2，则总的关键字数目n 满足：SQ 因此有：h W 1+ log s ((n+1)/2)=1 + log m/2((n+1)/2)即在含有n 个关键字的B_M 上进行查找时，从根结点到待查找记录关键字的结点 的路径上所涉及的结点数不超过1+ g m/2 ((n+1)/2)。

15、m 阶B +树。

它与的主要不同是叶子结点中存储记录。

在 B +树中，所有的非叶子 结点可以看成是索引，而其中的关键字是作为 分界关键字”用来界定某一关键字的记录所 在的子树。

一棵 m 阶B "树与m 阶B_树的主要差异是： ⑴ 若一个结点有n 棵子树，则必含有 n 个关键字；⑵所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结 点按关键字的大小从小到大顺序链接；⑶ 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大 最小)关键字。

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。

是从关键字空间到存储地址空间的一种映象。

可写成：addr(a i )=H(k i ),addr(ai )是a i 的地址，k i 是a i 的关键字。

由记录的关键字确定记录在表中的地址，并将记录放入此地址，例1 :设散列表长为7,记录关键字组为：15, 14, 28, 26, 56, 23,散列函数：H(key)=key MOD2n 是一个数量级的，平均时间复杂度为14、一棵m 阶B_树，或者是空树，或者是满足以下性质的 ⑴ ⑵ ⑶ ⑷16、哈希函数：哈希函数是一种映象， 其中i 是表中一个元素， 哈希表：应用哈希函数， 样构成的表叫哈希表。