内部资料20112011年年3 3月计算机等级考试月计算机等级考试二级公共基础知识培训讲义二级公共基础知识培训讲义理工大楼理工大楼91591513月二级公共基础知识讲义(1.6树与二叉树)二级Access考试介绍一、考试方式一、考试方式1笔试：90 分钟，满分100 分，其中含公共基础知识部分30分2上机操作：90 分钟，满分100 分二、笔试题型及分值（根据考试大纲及往年试题二、笔试题型及分值（根据考试大纲及往年试题) 1选择题70 分（每小题2分，共3 5题）2填空题30 分（每空2 分，共15题）三、上机操作三、上机操作1基本操作（30 分）2简单应用（40 分）3综合应用（30 分）23月二级公共基础知识讲义(1.6树与二叉树)我们的目标通过二级考试通过二级考试33月二级公共基础知识讲义(1.6树与二叉树)基础知识部分：30分设有10道选择题和5道填空题 43月二级公共基础知识讲义(1.6树与二叉树)第一章 数据结构与算法1.1 算法1.2 数据结构的基本概念1.3 线性表及其顺序存储结构1.4 栈和队列1.5 线性链表1.6 树与二叉树1.7 查找技术1.8 排序技术53月二级公共基础知识讲义(1.6树与二叉树)1.6 树与二叉树1.6.1 树的基本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。 63月二级公共基础知识讲义(1.6树与二叉树)1.6.2 二叉树及其基本性质二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 73月二级公共基础知识讲义(1.6树与二叉树)二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分； 83月二级公共基础知识讲义(1.6树与二叉树)满二叉树 满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。 93月二级公共基础知识讲义(1.6树与二叉树)103月二级公共基础知识讲义(1.6树与二叉树)113月二级公共基础知识讲义(1.6树与二叉树)完全二叉树 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 123月二级公共基础知识讲义(1.6树与二叉树)满二叉树与完全二叉树（5）具有n个结点的完全二叉树的深度为log2n+1； （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)； 若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）； 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 133月二级公共基础知识讲义(1.6树与二叉树)1.6.3 二叉树的存储结构在计算机中，二叉树存储结构采用链式存储结构。 对于满二叉树与完全二叉树可以按层序层序进行顺序存储。 143月二级公共基础知识讲义(1.6树与二叉树)1.6.4 二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。 153月二级公共基础知识讲义(1.6树与二叉树) 1. 前序遍历（DLR） 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）访问根结点 （2）前序遍历左子树 （3）前序遍历右子树 注意的是：遍历左右子树时仍然采用前序遍历方法。 例：如图二叉树， 则前序遍历结果是：A B D E C F 163月二级公共基础知识讲义(1.6树与二叉树) 2. 中序遍历（LDR） 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树。 注意的是：遍历左右子树时仍然采用中序遍历方法。 例：如图二叉树， 则中序遍历结果是：D B E A F C 173月二级公共基础知识讲义(1.6树与二叉树)3. 后序遍历（LRD）后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。即： 若二叉树为空则结束返回，否则： （1）后序遍历左子树， （2）后序遍历右子树 （3）最后访问根结点。 注意的是：遍历左右子树时仍然采用后序遍历方法。 例：如图二叉树， 183月二级公共基础知识讲义(1.6树与二叉树)例:A B D E C F G D B E A F G C D E B G F C A前序遍历：中序遍历：后序遍历：193月二级公共基础知识讲义(1.6树与二叉树)历年考题【2005年4月填空第1题】（1）某二叉树中度为2的结点有18个，则该二叉树中有_个叶子结点。【2005年4月填空第4题】（4）一棵二叉树第六层（根结点为第一层）的结点数最多为_个。【2007年4月选择第7题】（7）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为A）n+1 B）n-1 C）2n D）n/2203月二级公共基础知识讲义(1.6树与二叉树)历年考题【2007年4月填空第1题】（1）在深度为7的满二叉树中，度为2的结点个数为 。 【2007年9月选择第8题】（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A)219 B)221 C)229 D)231【2008年4月填空第2题】（2）深度为5的满二叉树有 个叶子结点。213月二级公共基础知识讲义(1.6树与二叉树)【2006年4月选择第6题】（6）对下列二叉树进行后序遍历的结果为A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCA223月二级公共基础知识讲义(1.6树与二叉树)【2007年4月选择第6题】（6）对下列二叉树进行前序遍历的结果为A）DYBEAFCZX B）YDEBFZXCAC）ABDYECFXZ D）ABCDEFXYZ233月二级公共基础知识讲义(1.6树与二叉树)【2007年9月填空第4题】（4）对下列二叉树进行中序遍历的结果为 【4】 。243月二级公共基础知识讲义(1.6树与二叉树)2008.9(1)对下列二叉树进行中序遍历的结果是对下列二叉树进行中序遍历的结果是 【1】 。253月二级公共基础知识讲义(1.6树与二叉树)P39 练习题填空第2小题设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点 。263月二级公共基础知识讲义(1.6树与二叉树)二叉树的遍历 模拟题已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A) cedbaB) acbedC) decabD) deabc273月二级公共基础知识讲义(1.6树与二叉树)