数据结构第5章树和二叉树答案

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ）

【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) E F G D B A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

第六章 习题

一、选择题

1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A 、4 B、5 C、6 D、 7

2、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。

A、 15 B、16 C、17 Ｄ、47

3、假定一棵三叉树的结点数为50，则它的最小高度为（ ） A、 3 B、4 C、5 D、6

4、在一棵二叉树上第5层的结点数最多为（ ） A、8 B、 16 C、 15 D、32

5、用顺序存储方式将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[I]若有子树，则左子树是结点（ ）

A、R[2I+1] B、R[2I] C、R[I/2] D、R[2I-1] 6、在一棵具有k层的满三叉树中，结点总数为（ ） A、（3k-1）/2 B、3k-1 C、（3k-1）/3 D、3k

7、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) B D E F G A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

实验六：二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。

五、实验步骤

六、测试数据

1、输入数据：2.2*（3.1+1.20）-7.5/3

正确结果：6.9

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) B D E F G A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

数据结构考研试题精选及答案

第6章 树和二叉树

部分答案解释如下。

12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以

1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所

以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B

都不全。由本题可解答44题。

47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索

为空（无后继），共2个空链域。

52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1

个空链域。

部分答案解释如下。

6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。

19．任何结点至多只有左子树的二叉树的遍历就不需要栈。

24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1

（2i+1<=n）

37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右

孩子。

38 . 新插入的结点都是叶子结点

数据结构考研试题精选及答案

第6章 树和二叉树

部分答案解释如下。

12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以

1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所

以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B

都不全。由本题可解答44题。

47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索

为空（无后继），共2个空链域。

52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1

个空链域。

部分答案解释如下。

6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。

19．任何结点至多只有左子树的二叉树的遍历就不需要栈。

24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1

（2i+1<=n）

37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右

孩子。

38 . 新插入的结点都是叶子结点

第6章树和二叉树自测卷解答姓名班级

题号 题分 得分 一 10 二 15 三 11 四 20

五 20 六 24 总分 100 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）

（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字

值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）

（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）

（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中

有n+1个为空指针。

（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于

一、基础知识题

6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】 设度为m的树中度为0,1,2,?,m的结点数分别为n0, n1, n2,?, nm，结点总数为n，分枝数为B，则下面二式成立 n= n0+n1+n2+?+nm (1) n=B+1= n1+2n2 +?+mnm+1 (2)

由(1)和(2)得叶子结点数n0=1+

即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8

6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1

由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.

注：解本题时要使用以上公式

2008信息与计算科学专业数据结构习题

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）

A．5 B．6 C．7 D．8 4. 在下述结论中，正确的是（ ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④

5. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右