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

１、数据(Daｔa） ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（Ｄａta Eleｍenｔ） ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项（Data　Ｉteｍ）。数据项是对客观事物某一方面特性的数据描述。
　 　　　数据对象（Ｄａta　Objecｔ):是性质相同的数据元素的集合,=｛‘A’,’B’，’C，…｝ 。
数据结构（Dａｔa Ｓtｒucｔurｅ）:是指相互之间具有（存在）一定联系(关系)的数据元素的集合。元素之间的相互联系（关系）称为逻辑结构。数据元素之间的逻辑结构有四种基本类型,如图1—３所示。
① 集合:结构中的数据元素除了“同属于一个集合”外，没有其它关系。
② 线性结构:结构中的数据元素之间存在一对一的关系。
③　树型结构:结构中的数据元素之间存在一对多的关系。
④　图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
2、顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、Ｃ语言中用带指针的结构体类型来描述
ｔｙpｅdef 　struct　 Lｎｏde　
{ EleｍＴｙpe　 ｄaｔa；　 ／＊数据域,保存结点的值　*/
stｒｕcｔ　 Ｌnｏde *neｘt； 　 　/＊指针域*/
}ＬNoｄe；　 　 /＊结点的类型　＊/
4、循环队列为空:ｆｒont=reaｒ 。　　
循环队列满：（rear+1）％ＭAX_QＵＥUE_SIＺE　＝ｆronｔ．
５、性质1：在非空二叉树中,第ｉ层上至多有2i—１个结点（i≧１）。
性质2：深度为k的二叉树至多有2k—１个结点(ｋ≧1） 。
性质３：对任何一棵二叉树，若其叶子结点数为ｎ0，度为2的结点数为n２,则ｎ0=ｎ2+１．
一棵深度为k且有２ｋ-1个结点的二叉树称为满二叉树（Ｆulｌ Ｂｉｎａｒy Ｔreｅ)。
完全二叉树的特点:若完全二叉树的深度为k　，则所有的叶子结点都出现在第k层或k-，如果其右子树的最大层次为l，则其左子树的最大层次为l或l＋1。
性质4：n个结点的完全二叉树深度为：ë㏒２nû +1.
性质5：若对一棵有n个结点的完全二叉树(深度为└㏒２ｎ┘＋１）的结点按层(从第1层到第ë㏒２ｎû　+１层）序自左至右进行编号，则对于编号为
i（1≦i≦n）的结点：
⑴ 若i=1：则结点ｉ是二叉树的根,无双亲结点；否则，若i＞1，则其双亲结点编号是　ëi／2û 。
⑵ 如果2i>n:则结点ｉ为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
⑶ 如果2ｉ+1〉n：则结点i无右孩子；否则,其右孩子结点编号是２ｉ+１。
6、线索二叉树：设一棵二叉树有n个结点，则有ｎ—1条边（指针连线）　， 而ｎ个结点共有2n个指针域（Lcｈｉld和Rcｈilｄ) ，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息．
７、Huffmａn树：具有n个叶子结点(每个结点的权值为wi)　的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵ＷPL值最小的树,称这棵树为
Hufｆmaｎ树(或称最优树) 。
8、完全无向图：对于无向图,若图中顶点数为ｎ ,用e表示边的数目，则ｅ　Î［0，n（n—１）/2］ ．具有n（n—１）/２条边的无向图称为完全无向图.
完全有向图:对于有向图,若图中顶点数为ｎ ，用e表示弧的数目,则eÎ［０,n（n-1）］　。具有n（ｎ－1）条边的有向图称为完全有向图。
生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图,它含有图中全部n个顶点和只有足以构成一棵树的ｎ-1条边,称为图的生成树
关于无向图的生成树的几个结论：
１） 一棵有n个顶点的生成树有且仅有n—1条边；
2) 如果一个图有n个顶点和小于n-１条边，则是非连通图；
3） 如果多于ｎ－1条边,则一定有环;
　4）　有n－1条边的图不一定是生成树。
9、最小生成树(Ｍｉnimum Sｐanning Tree) ：带权连通图中代价最小的生成树称为最小生成树.　
最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路,边的权值表示建