清华大学严蔚敏版数据结构考研要点(精华版).doc

1、1、数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合 C=A,B,C, 。数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系( 关系) 称为逻

2、辑结构。 数据元素之间的逻辑结构有四种基本类型，如图1-3 所示。 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。2、顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。在 C 语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。3、 C 语言中用带指针的

3、结构体类型来描述typedef struct Lnode ElemType data; /*数据域，保存结点的值 */struct Lnode *next; /*指针域*/LNode; /*结点的类型 */4、循环队列为空：front=rear 。 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。5、性质 1：在非空二叉树中，第 i 层上至多有 2i-1 个结点 (i1) 。性质 2：深度为 k 的二叉树至多有 2k-1 个结点（k1) 。性质 3：对任何一棵二叉树，若其叶子结点数为 n0，度为 2 的结点数为 n2，则n0=n2+1。一棵深度为 k 且有 2k-1

4、个结点的二叉树称为满二叉树(Full Binary Tree)。完全二叉树的特点：若完全二叉树的深度为 k ，则所有的叶子结点都出现在第 k 层或k-1 层。对于任一结点，如果其右子树的最大层次为 l，则其左子树的最大层次为 l 或 l+1。性质 4：n 个结点的完全二叉树深度为： 2n +1。性质 5：若对一棵有 n 个结点的完全二叉树(深度为 2n+1)的结点按层（从第 1 层到第 2n +1 层)序自左至右进行编号,则对于编号为 i（1 in) 的结点： 若 i=1：则结点 i 是二叉树的根，无双亲结点；否则，若 i1，则其双亲结点编号是 i/2 。 如果 2in：则结点 i 为叶子结点

5、，无左孩子；否则，其左孩子结点编号是 2i。 如果 2i+1n：则结点 i 无右孩子；否则，其右孩子结点编号是 2i+1。6、线索二叉树：设一棵二叉树有 n 个结点，则有 n-1 条边(指针连线) ， 而 n 个结点共有2n 个指针域(Lchild 和 Rchild) ，显然有 n+1 个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。7、 Huffman 树：具有 n 个叶子结点(每个结点的权值为 wi) 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵 WPL 值最小的树，称这棵树为 Huffman树(或称最优树) 。8、完全无向图：对于无向图，若图中顶

6、点数为 n ，用 e 表示边的数目，则 e 0，n(n-1)/2 。具有 n(n-1)/2 条边的无向图称为完全无向图。完全有向图：对于有向图，若图中顶点数为 n ，用 e 表示弧的数目，则 e0，n(n-1) 。具有 n(n-1)条边的有向图称为完全有向图。生成树、生成森林：一个连通图(无向图) 的生成树是一个极小连通子图，它含有图中全部n 个顶点和只有足以构成一棵树的 n-1 条边，称为图的生成树关于无向图的生成树的几个结论：1) 一棵有 n 个顶点的生成树有且仅有 n-1 条边；2) 如果一个图有 n 个顶点和 小于 n-1 条边，则是非连通图；3) 如果多于 n-1 条边，则一定有环；

7、4) 有 n-1 条边的图不一定是生成树。9、最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。 最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n 个城市之间最多可以建 n(n-1)/2 条线路，如何选择其中的 n-1 条，使总的建造费用最低?10、 工程完成最短时间：从起点到终点的最长路径长度(路径上各活动持续时间之和) 。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的关键。 11、查找方法比较顺序查找 折半查找 分块查找

8、ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表12、 在随机情况下，二叉排序树的平均查找长度 ASL 和(n)(树的深度)是等数量级的。二叉排序树(Binary Sort Tree 或 Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。(1) ：若左子树不为空，则左子树上所有结点的值(关键字) 都小于根结点的值；(2) ：若右子树不为空，则右子树上所有结点的值(关键字) 都大于根结点的值；(3) ：左、右子树都分别是二叉排序树。结论：若按中序遍历一棵二叉排序树，

9、所得到的结点序列是一个递增序列。13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。：左子树和右子树深度之差的绝对值不大于 1；：左子树和右子树也都是平衡二叉树。平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。平衡二叉排序树上进行查找的平均查找长度和2n 是一个数量级的，平均时间复杂度为O(2n)。四种平衡化旋转，其正确性容易由“遍历所得中序序列不变 ”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以 a 为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点

10、而失衡，仅需对失衡子树做平衡化旋转处理。14、 一棵 m 阶 B_树，或者是空树，或者是满足以下性质的 m 叉树： 根结点或者是叶子，或者至少有两棵子树，至多有 m 棵子树； 除根结点外，所有非终端结点至少有 m/2 棵子树，至多有 m 棵子树； 所有叶子结点都在树的同一层上； 每个结点应包含如下信息：(n，A 0，K 1，A 1，K 2，A 2， ，K n，A n)其中 Ki(1in)是关键字，且 Kilength; i+) L-R0=L-Ri; j=i-1; /* 设置哨兵 */while( LT(L-R0.key, L-Rj.key) ) L-Rj+1=L-Rj;j-; /* 查找插入位

11、置 */L-Rj+1=L-R0; /* 插入到相应位置 */ =折半插入排序当将待排序的记录 Ri 插入到已排好序的记录子表 R1i-1中时，由于 R1, R2 , Ri-1已排好序，则查找插入位置可以用 “折半查找 ”实现，则直接插入排序就变成为折半插入排序。从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为 O(n2) 。排序示例：设有一组关键字 30, 13, 70, 85, 39, 42, 6, 20，采用折半插入排序方法排序的过程 算法实现 void Binary_insert_sort(Sqlist *L) int i, j, low

12、, high, mid ;for (i=2; ilength; i+) L-R0=L-Ri; /* 设置哨兵 */ low=1 ; high=i-1 ; while (lowR0.key, L-Rmid.key) )high=mid-1 ;else low=mid+1 ; /* 查找插入位置 */for (j=i-1; j=high+1; j-)L-Rj+1=L-Rj; L-Rhigh+1=L-R0; /* 插入到相应位置 */= 2-路插入排序排序示例：设有初始关键字集合49, 38, 65, 13, 97, 27, 76 ，采用 2-路插入排序的过程例：设有关键字集合49, 38, 65,

13、 97, 76, 13, 27, 49 ，采用表插入排序的过程=希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。排序示例 设有 10 个待排序的记录，关键字分别为 9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是 5, 3, 1，希尔排序的过程：算法实现先给出一趟希尔排序的算法，类似直接插入排序。void shell_pass(Sqlist *L, int d)/* 对顺序表 L 进行一趟希尔排序, 增量为 d */ int j, k ;for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 设置监视哨兵 */k=j-

14、d ;while (k0 k=k-d ; L-Rk+j=L-R0 ;void shell_sort(Sqlist *L, int dk, int t)/* 按增量序列 dk0 t-1,对顺序表 L 进行希尔排序 */ int m ;for (m=0; mlength; j+) /* 共有 n-1 趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序 */ if (LT(L-Rk+1.key, L-Rk.key ) ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if (flag=TRUE) break ;算法分析:时间复杂度:最好情况(正序 )：比较次数： n-1；移动次数：0；