15[填空题]对右图二叉树进行中序遍历的结果为(　　)。

　　参考解析：ACBDFEHGP

　　【分析】中序遍历的原则是先遍历左子树，然后访问根结点，最后遍历右子树。因此本题中遍历结果是ACBDFEHGP。

　　16[填空题]在深度为7的满二叉树中，度为2的结点个数为(　　)。

　　参考解析：63

　　【分析】满二叉树的定义是除最后一层外，每一层上的所有结点都有两个子结点(即每一层上的结点数均达到最大值)。第l层(根结点在第l层)拥有的结点数是20=1，第2层拥有的结点数是21=2，第3层拥有的结点数是22=4，……，第n层拥有的结点数是2n-1。在深度为7的满二叉树中，叶子结点全部在第7层，其余结点都是2度结点。在满二叉树中，第7层拥有的结点数是27-1=64。二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以度为2的结点个数为64—1=63。

　　17[单选题]对右下图二叉树进行后序遍历的结果为(　　)。

　　参考答案：D

　　参考解析：后序遍历的方法是：若二叉树为空，则结束返回。否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。本题后序遍历左子树的结果是DEB，后续遍历右子树的结果是FC，最后根是A，所以后续遍历的结果是DEBFCA。因此本题的正确答案是D。

　　18[单选题]在深度为7的满二叉树中，叶子结点的个数为(　　)。

　　参考答案：C

　　参考解析：在满二叉树中每层的结点数都达到最大值， 而且叶子结点全部出现在最底层。第l层(根结点所在的层)有20个结点，第2层有21个结点，……第n层有2n-1个结点。在深度为7的满二叉树中，第7层有2 7-l=64个结点(全部是叶子结点)、在深度为7的满二叉树中，共有27—1=127个结点、因此本题的正确答案是C

　　19[填空题]在深度为7的满二又树中，度为2的结点个数为________。

　　参考解析：63

　　【分析】满二叉树的定义是除最后-层外，每-层上的所有结点都有两个子结点(即每-层上的结点数均达到最大值)。第l层(根结点在第l层)拥有的结点数是20=1，第2层拥有的结点数是21=2，第3层拥有的结点数是22=4，……，第n层拥有的结点数是2n-1。在深度为7的满二叉树中，叶子结点全部在第7层，其余结点都是2度结点。在满二叉树中，第7层拥有的结点数是27-1=64。二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以度为2的结点个数为64—1=63。

　　20[单选题]一棵二叉树中共有70个叶子结点与80个度为1的结点，该二叉树中的总结点数为(　　)

　　A.219B.221C.229D.231

　　参考答案：A

　　参考解析：二叉树具有这样一个性质：在任意-颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。本题告知，叶子结点有70个，那度为2的结点就有69个，度为l的结点有80个，这颗二叉树共有70+69+80=219个结点。因此本题的正确答案是A。

　　21[单选题]对右图二叉树进行前序遍历的结果为(　　)

　　A.DYBEAFCZX

　　B.YDEBFZXCA

　　C.ABDYECFXZ

　　D.ABCDEFXYZ

　　参考答案：C

　　参考解析：前序遍历(DLR)的基本思想是：先访问根结点，后前序遍历dzq-树，再前序遍历右子树。本题根结点是A，前序遍历左子树得到的序列为BDYE，前序遍历右子树得到的序列为CFXZ，所以对本题二叉树进行前序遍历的结果为ABDYECFXZ。因此本题的正确答案是C。

　　22[单选题]一棵度数为4的树，它的4度结点有l个，3度结点有2个，2度结点有3个，l度结点4个，问它的叶子结点有多少个?(　　)。

　　参考答案：D

　　参考解析：

　　23[填空题]设一棵二叉树的中序遍历结果为DBEACF，前序遍历结果为ABDECF，则后序遍历结果为________。

　　参考解析：

　　DEBFCA【分析】我们可以根据前序遍历的结果ABDECF，确定第l个元素A是根结点，再看中序遍历的结果DBEACF，A前面的DBE应该在左子树，A后面的FC应该在右子树。根据前序遍历的结果和中序遍历的结果，我们可以推导出：A是根结点，B是A的左结点，D是B的左结点，E是B的右结点.C是A的右结点，F是C的右结点，画出的二叉树如图1.17所示。对图进行后序遍历的结果为DEBFCA。

　　总结：先根据前序遍历或后序遍历的结果，确定根结点，根据根结点确定左右予树上的结点，再根据两种遍历画出对应的二叉树，最后遍历二叉树得到第三种遍历结果。

　　24[填空题]树是-种简单的________(线性月)线性)结构，在树中，所有数据元素之间的关系具有明显的________特性。

　　参考解析：非线性

　　25[填空题]一棵二叉树第六层(根结点为第-层)的结点数最多为________个。

　　参考解析：

　　32【分析】根据二叉树的性质，我们可以得出一棵二又树第n层(根结点为第-层)的结点数最多为2n-1个，因此第6层的结点数最多为25=32个，总结：二叉树第1层只有一个根结点(20)，第2层最多只有两个结点(21)，第3层最多只有4个结点(22)，……，第n层最多为有2n-1个结点(不是2n个)。考生还需要了解一棵深度(高度)为n的二叉树最多拥有的结点总数是2n-1(20+21+22+…+2n-1=2n-l).这种类型的试题不要死记硬背，有时是2n-1，有时是2n-l，所以考生最好采用我们介绍的方法来推导。

　　26[单选题]在表示树的多重链表中，除了要存储结点的值和多个指针之外，还必须需要存储(　　)。

　　参考答案：A

　　27[单选题]具有8个结点的完全二：叉树中编号为4的结点的右子结点的编号为(　　)。

　　参考答案：C

　　28[填空题]拥有奇数个结点的完全二叉树中有4个内部结点(非叶子结点)，请问它的叶子结点数是________。

　　参考解析：5

　　【分析】由于完全二叉树是自上而下、自左而右的从l开始连续编码的，因此完全二又树要么不存在-度结点(当结点个数为奇数个时)，要么存在一个-度结点，而且唯-的一个-度结点就是最后编号为n(n为偶数)的叶子结点的父结点。而在二叉树中零度结点个数总比二度结点个数多l，因此拥有4个二度结点的二叉树的叶子结点的个数是4+1=5。

　　总结，设n为完全二叉树的结点数，n0为叶子结点数，nl为度为1的结点数，n2为度2的结点数，则n=n0+nl+n2,n0=n2+1。若n为奇数，则nI=0;若n为偶数，则nl=l(注意-定要是完全二又树)。

　　29[填空题]一棵二又树第六层(根结点为第一层)的结点数最多为(　　)个。

　　参考解析：32

　　30[填空题]某--y.树中度为2的结点有l8个，则该--y.树中有(　　)个叶子结点。

　　参考解析：19

　　【分析】在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。

　　31[填空题]拥有奇数个结点的完全二叉树中有4个内部结点(非叶子结点)，请问它的叶子结点数是(　　)。

　　参考解析：5

　　32[填空题]设一棵二叉树的中序遍历结果为DBEACF，前序遍历结果为ABDECF，则后序遍历结果为(　　)。

　　参考解析：DEBFCA

　　图1.17

　　33[填空题]树是一种简单的(　　)(线性月}线性)结构，在树中，所有数据元素之间的关系具有明显的(　　)特性。

　　参考解析：非线性、层次

　　[填空题]设一棵完全二叉树共有700个结点，则在该二叉树中有(　　)个叶子结点。

　　参考解析：350

　　相关推荐：

　　2015年9月计算机等级考试成绩查询时间通知

　　2015计算机二级公共基础知识考前冲刺练试题汇总

　　2015计算机二级公共基础知识精选选择题专项练习

　　2015计算机二级《公共基础知识》精选选择题90道