第六章树和二叉树答案

第六章树与二叉树

一．选择题

1．下面关于二叉树的结论正确的是____________。

A．二叉树中，度为 0 的结点个数等于度为 2 的结点个数加 1。 B．二叉树中结点个数必大于 0。

C．完全二叉树中，任何一个结点的度，或者为 0，或者为 2。 D．二叉树的度是 2。

分析：该题目主要考查二叉树逻辑结构的特点。正确答案为 A。二叉树中叶

子结点的个数为 n0 ，度为 2 的结点的个数为 n2，度为 1 的结点个数为 n1， 树中结点总数为 n，则 n= n0+ n2+ n1。除根节点没有双亲外，每个结点都有 且仅有一个双亲，所以有 n-1= n1+ 2n2 作为孩子的结点，因此有 n0= n2+1。 二叉树中结点个数可以为 0，称为空树，所以 B 错。满二叉树中，任何一个 结点的度，或者为 0，或者为 2。完全二叉树中，任何一个结点的度，或者

为 0，或者为 1，或者为 2。所以 C 错。二叉树的度可以是 0、1、2。所以 D 错。

2．设 X 是树 T 中的一个非根结点，B 是 T 所对应得二叉树，在 B 中，X 是 其双亲的右孩子，下列结论正确的是____________。

A．在树 T 中，Ｘ是其双亲的第一个孩子。 B．在树

第六章 树和二叉树 试题

一、单项选择题

1. 树中所有结点的度等于所有结点数加（ ）。

A. 0 B. 1 C. -1

D. 2

2. 在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点

3. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。

A. 2 B. 1 C. 0 D. -1

4. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。

A. n B. n-1 C. n+1 D. 2*n

5. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），

最多具有（ ）个结点。

A. 2i B. 2i+1 C. 2i-1 D. 2n

6. 在一棵高度为h（假定根结点的层号为0）的完全二叉树中，

数据结构题集

第六章 树和二叉树

1. 请写出利用栈对二叉树进行先根次序遍历的非递归算法。

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法

{

InitStack(S);

Push(S,T); //根指针进栈

while(!StackEmpty(S))

{

while(Gettop(S,p)&&p)

{

visit(p->data);

push(S,p->lchild);

} //向左走到尽头

pop(S,p);

if(!StackEmpty(S))

{

pop(S,p);

push(S,p->rchild); //向右一步

}

}//while

}//PreOrder_Nonrecursive

2.编写递归算法，在二叉树中求位于先序序列中第K个位置的结点的值。

int c,k; //这里把k和计数器c作为全局变量处理

void Get_PreSeq(Bitree T)//求先序序列为k的结点的值

{

if(T)

{

c++; //每访问一个子树的根都会使前序序号计数器加1

if(c==k)

{

printf("Value is %d\n",T->data);

exit (1);

}

else

第六章 树和二叉树

一、单项选择题

1. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 2. 一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 3. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的( ) A．1/2倍 B．1倍 C．2倍 D．3倍 4. 树最适合用来表示( ) A.有序数据元素 B.无序数据元素

C.元素之间具有分层次关系的数据 D.元素之间无联系的数据 5. 二叉树中第5层上的结点个数最多为( ) A.8 B.15 C.16 D.32 6. 线索二叉树是一种__结构( ) A.逻辑 B.逻辑和存储 C.物理 D.线性

7. 设高度为h的二叉树上只有度为0

第四课 树和二叉树

一、选择题

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 参考答案：D

2．当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（ ）。

A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i/2] D．无法确定 参考答案：D

3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B．500 C．254 D．505 E．以上答案都不对 参考答案：E

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

A．5 B．6 C．7 D．8 参考答案：D

5．在下述结论中，正确的是（ ）。

①只有一个结点的二叉树的度为0； ②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 参考答案：D

6．设森林

一、选择题

1．对于先序遍历和中序遍历结果相同的二叉树为（ BF ）；对于先序遍历和后序遍历结果相同的二叉树为（ B ）

A.一般二叉树 B.只有根结点的二叉树 C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树 E.所有结点只有左孩子的二叉树 F.所有结点只有右孩子的二叉树。

2．下列关于哈夫曼树的叙述错误的是( D)。

A．哈夫曼树的根结点的权值等于所有叶结点的权值之和 B．具有n个叶结点的哈夫曼树共有2n-l个结点 C．哈夫曼树是带权外路径长度最短的二叉树 D．哈夫曼树一个结点的度可以是0、1或2

3．设T2是由树T转换得到的二叉树，则T中结点的后序序列是T2结点的( B )。 A．先序序列 B．中序序列 C．后序序列 D．层次序列 4．设有一个度为3的树，其叶结点数为n0，度为1的结点数为nl，度为2的结点数为n2， 度为3的结点数为n3，则n0与nl，n2，n3满足关系（ B ）。 A． n0 =n2+1 B．n0=

计算机科学与技术学院计算机科学与技术专业 3014216100（重修）李远四班

第六章 树和二叉树（一）

一、选择题

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

A. 5B. 6C. 7 D. 8 2. 下列有关二叉树的说法正确的是（）。

A. 二叉树的度为2 B. 一颗二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2

3. 若一颗二叉树具有10个度为2的结点，5个度为1的节点，则度为0的结点个数是（）。

A. 9B. 11C.15D. 不确定

4. 一颗具有n个结点的完全二叉树的高度（深度）是（）。

A.?logn?+1B. logn + 1C. ?logn?D.logn - 1

5.将有关二叉树的概念推广到三叉树，则一颗有244个结点的完全三叉树的高度为（）。

A.4B.5C. 6D. 7

6. 树的后根遍历序列等同于该树对应的二叉树的（）。

A.先序序列B.中序序列C. 后序序列D. 层次序列 7. n个结点的线索二叉树上含有的线索数为（）。

A. 2nB. n-1C. n+1D. n

遍历二叉树课程教案

授课方式 （请打√） 教学目的： （1）掌握树的各种术语，例如根、叶子、度、深度； （2）掌握二叉树的定义； （3）掌握二叉树的遍历方法； 理论课□ 讨论课□ 实验课□ 习题课□ 其他□ 课时 安排 授课题目：遍历二叉树 要求：（1）提高学生的认知能力； （2）培养学生自主学习和团结协作的能力； 教学重点及难点： 重点：（1）二叉树的定义； （2）二叉树的遍历方法。 难点：二叉树的遍历 教 学 基 本 内 容 遍历二叉树 一、二叉树的定义： 树基本定义： 树：包含N个结点的有穷集合；（N>0） 根：没有父母的结点； 叶子：没有孩子的结点或者度为0的结点； 度：某个结点孩子的个数； 深度：二叉树的层数 1.二叉树是每个结点的度都为2的有序树，它的特点是每个结点至多有两棵子树。 二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。 二叉树有5种基本形态： (a) (b) (c)

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的右

第六章 树和二叉树

一、选择题

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

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

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④

8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A．9 B．11 C．15 D．不确定

9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个

A．4 B．5 C．6 D．7 11．具有10个叶结点的二叉树中有（ ）个度为2的结点，

A．8 B．9 C．10