树练习题(答案)

、

《树》练习题

一、单项选择题

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 D. 47 3、 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。（根为第0层） A. 3 B. 4 C. 5 D. 6 4、 '

5、

在一棵二叉树上第3层的结点数最多为（ ）（根为第0层）。 A. 2 B. 4 C. 6 D. 8

6、 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ ）。（若存放在R[0..n-1]则左孩子R[2i+1]） A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 7、 将含100个结点的完全二叉树，按照从上层到下层、同层从左到右的次序依次给它们编以从0开始的连续自然数，则编号为40的结点X的双亲的编号为( )。

B.20 C. 21 8、 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A. 24 B. 48 C. 72 D. 53 9、 >

10、

设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙

11、 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。 A. 中序 B. 前序 C. 后序 D. 层次序 12、 下面叙述正确的是（ ）。 A. 二叉树不是树

B. 二叉树等价于度为2的树 ？

C. 完全二叉树必为满二叉树

D. 二叉树的左右子树有次序之分

13、 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。 A. 不发生改变 B. 发生改变

C. 不能确定 D. 以上都不对

14、 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ ）。 A. 1 B. 2 C. 3 D. 4 15、 下列图示的顺序存储结构表示的二叉树是( )。

> 1 2 3 4 5 6 7 [ 9 10 11 12 0 8

A B C ABDEFCDEBF< D E A A$ F ACBFDEF CCBDEA. B. C. D.

16、 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足的条件是（ ）。

A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 17、 根据先序序列ABDEC和中序序列BDEAC确定对应的二叉树，该二叉树（ ）。 ;

A. 是完全二叉树但不是满二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不能确定

18、 对任何一棵二叉树T，设N0、N1、N2分别是度数为0、1、2的结点数，则下列判断正确的是（ ）。

A．N0＝N2＋1 B．N1＝N0＋1 C．N2＝N0＋1 D．N2＝N1＋1

二、判断题

1. 二叉树中每个结点的度不能超过2。 （1 ） 2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。 （1 ） }

3. 哈夫曼树的总结点个数（多于1时）不能为偶数。 4. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 5. 树的后序遍历与其对应的二叉树的中序遍历序列相同。 6. 根据任意一种遍历序列即可唯一确定对应的二叉树。 7. 满二叉树也是完全二叉树。 8. 哈夫曼树一定是完全二叉树。 9. 树的子树是无序的。 10.度小于等于2的有序树即为二叉树。

#

（1 ） （0 ） （0 ） （0 ） （1 ） （ 0） （0 ） （0 ）

三、填空题

1、 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_55__。 2、 在一棵二叉排序树上按 中序 遍历得到的结点序列是一个有序序列。 3、 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总

数为 2n 个，其中 n-1 个用于链接孩子结点， n+1 个空闲着。

4、 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0= n2+1。

k-1

5、 一棵深度为k的满二叉树的结点总数为 2 ，一棵深度为k的完全二叉树

kk

的结点总数的最小值为 2-1 ，最大值为 2 。（根的深度为1） 6、 由三个结点构成的二叉树，共有 5 种不同的形态。 7、 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点

h

数至少为 2+1 。（根的高度为1） 8、 ! 9、 对于一棵具有n个结点的二叉树，若一个结点的编号为i(0≤i≤n-1)，则它的左

孩子结点的编号为 2i+1 ，右孩子结点的编号为 2i+2 ，双亲结点的编号为 (i-1)/2 。

10、假设一棵二叉树的先序序列为ABCEDFG，中序序列为AECBFDG，则该二叉树的层序

遍历序列中结点E的直接前驱是结点 F 。

四、应用题

1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。

先序：ABDHIEJKCFLG 中序：HDIBJEKALFCG 后序：HIDJKEBLFGCA #

2. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。

后序：ACDBGJKIHFE

3．若有字符a,b,c,d,e,f,g,h的频度权值分别为（30，5，9，11,15，2，7，16），试为这组字符设计哈弗曼编码。

9559291472751530920113616 哈弗曼编码：a:01 b:00001 c:100 d:101 e:001 f:00000 g:0001 h:11 五、算法设计题

按照以下树的定义，完成数类中的以下成员函数的编写。 （1）void PreOrder(Node* r)); //先序遍历的递归算法

…

（2）void InOrder(Node* r)); //中序遍历的递归算法

（3）void PostOrder(Node* r)); //后序遍历的递归算法 （4）int High(Node* bt); //求二叉树高度的递归算法

#include #define MaxSize 100 struct Node{

（

Node *lChild; //左子树指针

Node *rChild; //右子树指针 DataType data; };

class BTree { private:

Node* root; public:

BTree(); //构造函数 ;

void PreOrder(Node* r)); //先序遍历的递归算法 void InOrder(Node* r)); //中序遍历的递归算法 void PostOrder(Node* r)); //后序遍历的递归算法 int High(Node* bt); //求二叉树高度的递归算法 int NodeNum(Node* bt); // 求二叉树结点数目 };

//二叉树先序遍历 递归算法

void BTree::PreOrder(Node* r) { $

if(r!=NULL) {

cout<data;

PreOrder(r->lChild); PreOrder(r->rChild); } }

//二叉树中序遍历 递归算法

void BTree::InOrder(Node* r,) { 、

if(r!=NULL) {

InOrder(r->lChildt); cout<data;

InOrder(r->rChild); } }

//二叉树后序遍历 递归算法

void BTree::PostOrder(Node* r,) { —

if(r!=NULL) {

PostOrder(r->lChild); PostOrder(r->rChild; cout<data; } }

//求二叉树的高度

int BTree::High(Node* r) { int lh,rh;

if(r == NULL) return 0; else {

lh = High(r->lChild); rh = High(r->rChild); if(lh>rh) return lh+1; else return rh+1; } }