国家二级C语言公共基础知识要点及历年真题

c.树具有明显的层次关系，即树是一种层次结构。 d.数的最大层次称为树的深度。

第5页，共 26 页

f.在树中，叶子结点没有子树。

A E B F C G H D I K L J 如左图中， 1、A 为根结点； 2、E、F、J、H、K、L、 M 为叶子结点。 3、树中A、I 都有 3 个子 结点，故树的度为 3。 M 4、 整个树中， 总共分为4 层，故树的深度为 4。 树形表示法 二叉树 6.2 二叉树及其基本性质

1．什么是二叉树：

二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点： a.非空二叉树只有一个根结点；

b.每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

由以上特点可以看出，在二叉树中，每一个结点的度最大为2。 2．二叉树的基本性质：(重要)

a.在二叉树的第 k 层上，最多有 2k-1(k>=1)个结点。

b.深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。 c.在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比深度为 2 的结点多一个。

d.具有 n 个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取 log2n 的整数部分。

A、 第四层中，最多有 24-1=23=8 个结点。 B、树的深度为 4，最多有 24-1=16-1=15 个

结点。 C、度为 0 的结点有 8 个， 度为2 的结点有7

个。

3．满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

a.满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的 结点数都达到最大值，即在满二叉树的第k 层上有 2k-1 个结点，且深度为 m 的满二叉树有 2m-1 个结点。

b.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。 完全二叉树还具有以下性质：

a.具有 n 个结点的完全二叉树的深度为log2n] +1。 完全二叉树

满二叉树 非满二叉树 6.3 二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。 6.4 二叉树的遍历：(重要)

在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍

第6页，共 26 页

历。

a.前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。 b.中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。 c.后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。

F 1 5 F C 2 E 6 2 C G 7 6 E F 9 C 4 8 G E 8 A 3 D 4 1 A 4 D A 1 D 3 G 7 H 5 B 5 H 8 P 9 3 B 7 H 9 P B 2 P 6 前序：FCADBEGHP 中序：ACBDFEHGP 后序：ABDCHPGEF

注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾， 而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。

历届的考题：

1、在深度为 7 的满二叉树中，叶子结点的个数为()[2006.4]

A)32 B)31 C)64 D)63 2、对下图 1 所示二叉树

图 1 图 2 进行中序遍历的结果是________。[2006.9]

A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG

3、对如下图 2 所示二叉树，进行后序遍历的结果为()[2006.4]

A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA

4、某二叉树中，度为 2 的结点有 18 个，则该二叉树中有___个叶子结点。[2005.4] 5、一棵二叉树第六层（根结点为第一层）的结点数最多为____个。[2005.9]

1.7 查找技术

7.1 顺序查找：

顺序查找的方法是：用被查元素与线性表中的元素逐一比较， 直到找出相等的元素， 则查找成功；或者找遍

所有元素都不相等，则查找失败。

顺序查找的优点： 对线性表的元素的逻辑次序无要求 （不必对元素进行排序） ， 对线性表的存储结构无要求(顺

序存储、链接存储皆可)。

顺序查找的效率很低，但在以下情况下，只能采用顺序查找：

a.如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 b.即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 7.2 二分法查找：

第7页，共 26 页