全国计算机等级考试四级复习纲要：图的概念
②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。
二叉树转换为森林的步骤是:
①森林第一棵树的根就是二叉树的根;
②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点……，以此类推。
五、图
图的概念
图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个(直接)前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素(即双亲结点)相关。而在图中，任意两个数据元素之间均有可能相关。
图(graph)是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:
G=(V，E)
其中，V是非空的顶点集合，即
V={v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝
E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对(每个无序对(x，y)是两个对称序偶和的简写形式)的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。
快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2，移动次数最多也是n(n-1)/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。
6.常用排序方法的性能比较如下表所示:
常用排序方法的性能比较
排序方法 平均时间 最坏情况的时间 辅助存储
冒泡法、直接选择法、直接插入法 O(n2 ) O(n2 ) O(1)
快速排序 O(nlog2 n) O(n2 ) O(log2 n)
堆排序 O(nlog2n) O(nlog2 n) O(1)
归并排序 O(nlog2 n) O(nlog2 n) O(n)
注:在上表中，我们将n(n-1)/2也记为O(n2 )。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。
七、检索
1.顺序检索
检索又称为查找。顺序检索是将待查找的关键码值与线性表中个结点的关键码值逐一比较，直到找到所需的记录，检索成功;或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素，则最多检索次数为n，最少检索次数为1。
2.二分法检索
二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动，设线性表有n个元素，则最多的检索次数为大于log 2 n的最小整数，最少的检索次数为1。
3.分块检索
分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于(或小于，与此类推)前一块最大关键值。为加快查找，还要建立一个索引表，表中给出每一块的最大关键值和指向块内第一个结点位置的指针。分块检索分两步进行，先查索引表，确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法;在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速。
4.散列表检索
根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为k，则该记录的存储位置可用散列函数H来计算H=H(k)。常用来产生的散列函数的方法是除余法，即取H(k)=k mod p设散列表长度为n，取p为小于n的最大素数。一般说来，关键码值的集合比散列表存储位的数目大得多，这正是体现散列表的优势所在，但同时带来了冲突问题，即不同的关键值经散列函数计算，可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法，就是在发生冲突时，从H(k)以后的位置逐一探测，直至找到一个空位置，将新记录插入;在检索时，如果H(k)中不是所需关键值的记录，也是从H(k)往下逐一搜索，直到找到所需关键值或查找失败为止。应注意查找次序是:H(k)，H(k)+1，H(k)+2，…n-1，0，1，2，…，H(k)-1即在n-1以后，又从0开始，因为在位置上是循环的。双重散列技术是对线性探测法的改进。它使用两个散列函数H1和H2。对关键值k，计算H1(k)，求得0到n-1之间的一个散列地址;若在这个地址上冲突，下一个被探测的地址为(H1(k)+H2(k))mod n，关于选择H2的方法在此不做讨论。