数据结构题目收录（六）

1、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。

• A：h
• B：2h-1
• C：2h+1
• D：h+1

解析

结点最少的情况为：除根结点层只有一个结点外，其他h-1层均有两个结点，结点总数为2(h-1)+1=2h-1。

答案：B

2、设二叉树有2n各结点，且m

• A：n个度为0
• B：2m个度为0
• C：2m个度为1
• D：2m个度为2

解析

由二叉树的性质1可知$n_0=n_2+1$，结点总数=2n=$n_0+n_1+n_2$=$n_1+2n_2+1$，则$n_1=2(n-n_2)-1$，所以$n_1$为奇数，说明该二叉树中不可能有2m个度为1的结点。

答案：C

3、设二叉树只有度为0和度为2的结点，其结点个数为15，则该二叉树的最大深度为（）。

• A：4
• B：5
• C：8
• D：9

解析

第一层有一个结点，其余h-1层上各有两个结点，节点总数=1+2(h-1)=15，h=8。

答案：C

4、高度为h的完全二叉树最少有（）个结点。

• A：$2^h$
• B：$2^h+1$
• C：$2^{h-1}$
• D：$2^h-1$

解析

高度为h的完全二叉树中，第1层~第h-1层构成一个高度为h-1的满二叉树，为$2^{h-1}-1$。第h层至少有一个结点，所以最少的结点个数=($2^{h-1}-1$)+1=$2^{h-1}$。

答案：C

5、一棵有124个叶子结点的完全二叉树，最多有（）个结点。

• A：247
• B：248
• C：249
• D：250

解析

在非空的二叉树当中，由度为0和2的结点数的关系$n_0=n_2+1$可知$n_2$=123；总结点数n=$n_0+n_1+n_2=247+n_1$，其最大值为248（$n_1$的取值为1或0，当$n_1=1$时结点最多）。注意，由完全二叉树总结点数的奇偶性可以确定$n_1$的值，但不能根据$n_0$来确定$n_1$的值。

答案：B

6、已知一棵有2011个结点的树，其叶结点个数是116，该树对应的二叉树中无右孩子的结点个数是（）。

• A：115
• B：116
• C：1895
• D：1896

解析

采用特殊值法求解。二叉树中仅有前115个叶结点有右孩子结点，其余1896个结点均无右孩子结点。

答案：D

7、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。

• A：39
• B：52
• C：111
• D：119

解析

第6层有叶结点，完全二叉树的高度可能为6或7，显然树高为7时结点最多。完全二叉树与满二叉树相比，只是在最下一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。若第6层上有8个叶结点，则前6层为满二叉树，而第7层缺失了8*2=16个叶结点，故完全二叉树的结点个数最多为$2^7-1-16=111$。

答案：C

8、对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（）。

• A：31
• B：16
• C：15
• D：10

解析

二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1~5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，共需要存储单元的数量为1+2+4+8+16=31。

答案：A

9、在下列关于二叉树遍历的说法中，正确的是（）。

• A：若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
• B：若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
• C：若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
• D：若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点

解析

二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针走到底的结点，设用p指示。若结点p不是叶子结点（其左子树非空），则前序遍历的最后一个结点在它的左子树中，A、B错；若结点p是叶子结点，则前序与中序遍历的最后一个结点就是它，C正确。若中序遍历的最后一个结点p不是叶子结点，它还有一个左子女q，结点q是叶子结点，那么结点q是前序遍历的最后一个结点，但不是中序遍历的最后一个结点，D错。

答案：C

10、设n,m为一棵二叉树上的两个结点，在后序遍历时，n在m前的条件是（）。

• A：n在m右方
• B：n是m祖先
• C：n在m左方
• D：n是m子孙

解析

后序遍历的顺序是LRN，若n在N的左子树，m在N的右子树，则在后序遍历的过程中n在m之前访问；**若n是m的子孙，设m在N的位置，则n无论是在m的左子树还是在右子树，在后序遍历的过程中n都在m之前访问，其他都不可以。**C要成立，要加上两个结点位于同一层。

答案：D

学海无涯苦作舟