全国计算机等级考试四级复习纲要二[4]

文章作者 100test 发表时间 2007:03:10 18:40:43
来源 100Test.Com百考试题网

②抹线:抹去原二叉树中所有结点与其右孩子的连线.

③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。

9.二叉树与森林之间的转换

森林转换为二叉树的步骤是:

①将森林中的每棵树转换为二叉树.

②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。

二叉树转换为森林的步骤是:

①森林第一棵树的根就是二叉树的根.

②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树.③二叉树右子树的根结点作为余下树中第一棵树的根结点……，以此类推。

五、图

图的概念

图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个（直接）前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素（即双亲结点）相关。而在图中，任意两个数据元素之间均有可能相关。

图（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中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。来源：www.examda.com

对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集（vertexset）和边集（edgeset）所组成。针对图G，顶点集和边集可分别记为V（G）和E（G）。边集E（G）允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E（G）为有向边的集合，则称此图为有向图（digraph），若边集E（G）为无向边的集合，则称此图为无向图（undigraph）。

六、排序

1.直接插入排序

直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1 2 3 … （n-1）=n（n-1）/2。在插入时，元素的移动次数最多为1 2 3 … （n-1）=n（n-1）/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。

2.直接选择排序

直接选择排序的基本思想是在表的n个元素中，经过n-1次比较得到其最大值（或最小值，下同），这就排好了第一个元素.再经过n-2次比较得到余下元素中的最大值，这就排好了第二个元素…直到比较1次后排好第n-1个元素，第n个元素的位置也就自然确定了。所需的比较次数为（n-1） （n-2） 1=n（n-1）/2。所需移动次数最多也为n（n-1）/2。如果表中元素排好序，也需要比较n（n-1）/2次，而移动次数为0。

3.冒泡排序

冒泡排序的基本思想是将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过n-1次比较后，将确定出最大（或最小）元素的位置，这称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。第一趟扫描的比较次数是n-1，第二趟扫描的比较次数是n-2……，总的比较次数是（n-1） （n-2） …… 1=n（n-1）/2。如果恰好表中元素按反序排列，则需要移动的次数为3×n（n-1）/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了.当然，移动次数也是0。

4.归并排序

归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组……，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。

5.快速排序