数据结构复习2011.docVIP

主要知识点 1.1数据结构有逻辑结构和物理（存储）结构之分。逻辑结构描述了数据元素的逻辑表示及元素之间的逻辑关系，与计算机无关。物理结构描述了数据元素的存储表示以及元素之间逻辑关系的存储表示。 1.2 算法的基本特性之有穷性，程序≠算法。 1.3 算法的效率分析，包括时间效率和空间效率。算法的优劣不取决于算法的长短，而取决于算法的时间复杂度。 2.1 线性表的两种基本物理结构——顺序表与链表的特点： 顺序表（顺序存储结构的线性表）存放在一片连续的存储空间中； 链表（链式存储结构的线性表）以结点为基本存储单位，结点之间可不连续； 顺序表与链表的优缺点互补。顺序表的优点是可随机存取，存取速度快＝O(1)； 链表的优点是插入和删除操作效率高，借助于指针运算而避免了作大量的元素移动，适用于经常需要进行插入和删除操作的线性表。 2.2 循环单链表的首结点和尾结点的判定 设p指向某结点，则p==head-next —— p是首结点 　　　　　　　　　p-next==head —— p是尾结点 3.1 栈和队列是操作受限的特殊线性表，可以是顺序结构也可以是链表结构。特点：先进后出，先进先出。 例题： 1. 设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是___________________。2 3 5 4 1 2. 设有一个栈，元素的进栈次序为A，B，C，D，E，下列( C )是不可能的出栈序列。 A) A，B，C，D，E　　　　B) B，C，D，E，A C) E，A，B，C，D　　　　D) E，D，C，B，A 4.1 广义表的元素、长度及深度 广义表的元素可以是单个元素（原子），也可以是嵌套的广义表（子表）。当广义表GL非空时，称第一个元素ai为表头，其余元素合称为表尾。 广义表表达式中括号的最大嵌套层数称为广义表的深度。 例，A=(a,b,(c,d),(e,(f,g))) 长度＝4，即该广义表有4个元素，前2个是原子，后2个是子表，最后一个元素是个嵌套子表。 深度为3 。 B=(( )) 长度＝1 4.2 广义表的两个基本操作 head(GL) 获取表头，GL是广义表或子表的指针，返回表头的指针； tail(GL) 获取表尾，GL是广义表或子表的指针，返回表尾的指针。 例题： 1. 对于广义表gl=(a,b,(c,d))，取出原子c的运算可如下： 　tail(gl) 得　*(b,(c,d))　记作p1； 　tail(p1)　得　*(c,d)　　记作p2； 　head(p2)　得　*c 上述三步操作可表示成：head(tail(tail(gl))) 5.1二叉树的性质 (1)在二叉树的第k（k≥1）层上最多有2k-1个结点。 (2)深度为k（k≥1）的二叉树上至多有2k-1个结点。 (3)任意一棵二叉树中，若叶子结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。 (4)含有n个结点的二叉树的深度至少为「log2(n+1)］。 例题： 已知一棵完全二叉树第4层右端上有6个叶子，则整棵树至多／至少有多少个结点？ 解：由题意，该二叉树有5层。根据性质1，第4层上应有23=8个结点，已知有6个叶子，故第5层上至少有2×2-1=3个结点，至多有2×2=4个结点。 由性质2，整棵树至少有15+3=18个结点，至多有15+4=19个结点 5.2 二叉树先序、中序、后序遍历 例题： 设p(x)、m(x)、b(x)分别表示结点x在先序遍历、中序遍历及后序遍历中的序号。 现有两个结点A和B，且A是B的祖先，试问，下面哪些关系是成立的？ 　p(A)p(B) p(A)p(B) m(A)m(B) m(A)m(B) b(A)b(B) b(A)b(B) 5.3 哈夫曼树特性：结点个数＝2n-1 （n为叶子数） 7.1 无向图特性：对于具有n个顶点的无向图，至多有n(n-1)/2条边。无向连通图的生成树具有n-1条边。 7.2 有向图的入度和出度： 在邻接矩阵中，第i行中的有效值数是结点i的出度，第i列上的有效值数是结点i的入度。 在邻接表中，结点i的邻接矩链表中的结点个数是结点i的出度。 7.3 邻接矩阵与邻接表的存储空间：邻接矩阵的存储容量只取决于顶点个数；而邻接表的存储容量跟顶点个数和边数都有关。 7.4 连通分量是无向图中的极大连通子图，强连通分量是有向图中的极大强连通子图。 7.5 DFS和BFS 7.6 最小生成树的Prim算法和Kruskal算法的时间复杂度 ： Prim——O(n2 )　　　　　n为顶点数 Kruskal——O(eloge)　　　e为边数 7.7 有向图的拓扑排序