计算机2级C语言笔试部分 分为数据结构、软件工程、数据库、面向(2)

该树的深度为3 子树

在树中

以某结点的一个子结点为根构成的树称为该结点的一棵子树

2、二叉树基本性质

二叉树具有以下几个性质： 性质1：在二叉树的第k层上 最多有2k-1（k≥1）个结点；

性质2：深度为m的二叉树最多有2m-1个结点； 性质3：在任意一棵二叉树中

度为0的结点（即叶子结点）总是比度为2的结点多一个

性质4：具有n个结点的二叉树 其深度至少为［log2n］+1

其中［log2n］表示取log2n的整数部分

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

满二叉树是指这样的一种二叉树：除最后一层外 每一层上的所有结点都有两个子结点 在满二叉树中

每一层上的结点数都达到最大值

即在满二叉树的第k层上有2k-1个结点 且深度为m的满二叉树有2m－1个结点

完全二叉树是指这样的二叉树：除最后一层外

每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点

对于完全二叉树来说

叶子结点只可能在层次最大的两层上出现：对于任何一个结点 若其右分支下的子孙结点的最大层次为p 则其左分支下的子孙结点的最大层次或为p 或为p+1

完全二叉树具有以下两个性质：

性质5：具有n个结点的完全二叉树的深度为［log2n］+1

性质6：设完全二叉树共有n个结点 如果从根结点开始

按层次（每一层从左到右）用自然数1 2

......

n给结点进行编号

则对于编号为k（k=1 2

......

n）的结点有以下结论： ①若k=1

则该结点为根结点 它没有父结点；若k>1

则该结点的父结点编号为INT（k/2）

②若2k≤n

则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）

③若2k+1≤n

则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点

考点8 二叉树的遍历 在遍历二叉树的过程中 一般先遍历左子树 再遍历右子树

在先左后右的原则下 根据访问根结点的次序

二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历

（1）前序遍历：先访问根结点、然后遍历左子树 最后遍历右子树；并且 在遍历左、右子树时 仍然先访问根结点 然后遍历左子树 最后遍历右子树 A B D E C F

（2）中序遍历：先遍历左子树、然后访问根结点 最后遍历右子树；并且 在遍历左、右子树时 仍然先遍历左子树 然后访问根结点 最后遍历右子树

D B E A C F

（3）后序遍历：先遍历左子树、然后遍历右子树 最后访问根结点；并且 在遍历左、右子树时 仍然先遍历左子树 然后遍历右子树 最后访问根结点 D E B F C A

考点9 顺序查找

查找是指在一个给定的数据结构中查找某个指定的元素 从线性表的第一个元素开始

依次将线性表中的元素与被查找的元素相比较

若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等 则表示查找失败 例如

在一维数组[21 46 24 99 57 77 86]中

查找数据元素98

首先从第1个元素21开始进行比较 与要查找的数据不相等

接着与第2个元素46进行比较 以此类推

当进行到与第4个元素比较时 它们相等

所以查找成功

如果查找数据元素100 则整个线性表扫描完毕 仍未找到与100相等的元素 表示线性表中没有要查找的元素

在下列两种情况下也只能采用顺序查找： （1）如果线性表为无序表

则不管是顺序存储结构还是链式存储结构 只能用顺序查找

（2）即使是有序线性表 如果采用链式存储结构 也只能用顺序查找

考点10 二分法查找 二分法查找 也称拆半查找

是一种高效的查找方法

能使用二分法查找的线性表必须满足两个条件：

在本书中 为了简化问题 而更方便讨论

\有序\是特指元素按非递减排列 即从小到大排列 但允许相邻元素相等 下一节排序中

有序的含义也是如此

顺序查找法每一次比较 只将查找范围减少1 而二分法查找 每比较一次

可将查找范围减少为原来的一半 效率大大提高

对于长度为n的有序线性表 在最坏情况下

二分法查找只需比较log2n次 而顺序查找需要比较n次

考点11 排序

冒泡排序法和快速排序法都属于交换类排序法

用顺序存储结构；线性表是有序表

（1）冒泡排序法 首先

从表头开始往后扫描线性表 逐次比较相邻两个元素的大小 若前面的元素大于后面的元素 则将它们互换

不断地将两个相邻元素中的大者往后移动 最后最大者到了线性表的最后 然后

从后到前扫描剩下的线性表 逐次比较相邻两个元素的大小 若后面的元素小于前面的元素 则将它们互换

不断地将两个相邻元素中的小者往前移动 最后最小者到了线性表的最前面

对剩下的线性表重复上述过程 直到剩下的线性表变空为止 此时已经排好序

在最坏的情况下

冒泡排序需要比较次数为n（n－1）/2

（2）快速排序法

任取待排序序列中的某个元素作为基准（一般取第一个元素） 通过一趟排序

将待排元素分为左右两个子序列

左子序列元素的排序码均小于或等于基准元素的排序码 右子序列的排序码则大于基准元素的排序码 然后分别对两个子序列继续进行排序 直至整个序列有序

二级C语言公共基础知识之 软件工程