全国计算机四级考试复习纲要二（4）

会计考友

②抹线：抹去原二叉树中所有结点与其右孩子的连线;
' `4 N7 z# }3 W  a% n③旋转：将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。
6 H  V4 O5 Q/ ?* E& r9.二叉树与森林之间的转换
森林转换为二叉树的步骤是：
①将森林中的每棵树转换为二叉树;
②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。
* y! j% G% V  R. B3 G. M二叉树转换为森林的步骤是：
; l9 {0 u; ]; ^( A①森林第一棵树的根就是二叉树的根;
: `% u( u4 \) b' `5 A②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点……，以此类推。
五、图
" N! n# j, L# p; p% }: G图的概念
7 S; _% |- H( ]图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个（直接）前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素（即双亲结点）相关。而在图中，任意两个数据元素之间均有可能相关。
) ]. O3 U6 [7 D0 ~图（graph）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为：
G=（V，E）
7 c  Y+ [% G" ~$ Q) I1 w) g其中，V是非空的顶点集合，即
4 Z) i: C) t+ K5 c, t( uV=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝
1 h/ a' B3 J# S+ X, q) {; b4 p) dE是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对（每个无序对（x，y）是两个对称序偶和的简写形式）的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。

会计考友

对于一个图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。
( F, Q! M( l- U3 B3 d5 |* C9 n2.直接选择排序
3 c/ Y2 l8 o1 b8 o% s# m直接选择排序的基本思想是在表的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.归并排序
" |2 D8 X* n" O4 e, H归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组……，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。

会计考友

5.快速排序
  C% X3 F. S8 V/ m6 G1 I/ z快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为（n-1）+（n-2）+…+1=n（n-1）/2，移动次数最多也是n（n-1）/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。
6.常用排序方法的性能比较如下表所示：
$ f5 t+ Q3 e  t$ Y5 e/ t9 D常用排序方法的性能比较
排序方法 平均时间 最坏情况的时间 辅助存储
! Z0 b3 C& Z! d4 b  j; r冒泡法、直接选择法、直接插入法 O（n2 ） O（n2 ） O（1）
1 G3 F# s( c" e1 P快速排序 O（nlog2 n） O（n2 ） O（log2 n）
0 l! z# F5 w! }3 W! h! j6 L堆排序 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.二分法检索
. J% _! v- ]' l! ]6 R+ O二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动，设线性表有n个元素，则最多的检索次数为大于log 2 n的最小整数，最少的检索次数为1。

会计考友

3.分块检索
分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于（或小于，与此类推）前一块最大关键值。为加快查找，还要建立一个索引表，表中给出每一块的最大关键值和指向块内第一个结点位置的指针。分块检索分两步进行，先查索引表，确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法;在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速。
2 p6 M4 E! Y6 a' U/ I* X0 d4 d4.散列表检索
& e* G  R7 R" t' V/ h根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为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的方法在此不做讨论。