数据结构 树和二叉树习题

第六章 习题

一、选择题

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的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ） A、29 B、 37 C、46 D、44

8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ） A、 不发生改变 B、 发生改变 C、不能确定 D 、以上都不对

9、设a,b为一棵二叉树上的两个结点，在中序遍历中，a 在b 前面的条件是（ ） A、a 在b的右方 B、a 在b的左方 C、a 是b的祖先 D、a 是b的子孙 10、在N个结点的线索二叉树中，线索的数目为（ ） A、N-1 B、 N C、N+1 D、2N

11、如下图所示的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向（ ） A、A，D B、B，C C、D，A D、C，A A / \\ B D / / \\ C X E / Y

13、某二叉树中序序列为ABCDEFG ，后序序列为BDCAFGE，则前序序列是（ ） A、EGFACDB B、EACBDGF C、EAGCFBD D、上面都不对 二、填空题 1、假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（ ），树深度为（ ），终端结点的个数为（ ），单分支结点个数为（ ），双分支结点个数为（ ），三分支结点个数为（ ），C结点的双亲为（ ），其孩子结点为（ ）和（ ）结点。 2、其带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（ ）

1

3、若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点，则它必然是该子树后根遍历中的（ ）个结点。

4、哈夫曼树是带权路径长度（ ）的树，通常权值较大的结点离根（ ） 5、线索二叉树的左线索指向其（ ），右线索指向其（ ） 6、树在计算机内的表示方式有（ ），（ ），（ ）。

7、设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知的结点数分别为n1,n2,n3，则二叉树B的左子树中有（ ）个结点，二叉树B的右子树中有（ ）个结点。

8、若一个二叉树的叶子结点是某子树的中序遍历中的最后一个结点，则它必是该子树的（ ）序遍历中的最后一个结点。

9、用一维数组存放一棵完全二叉树：ABCDEFGHIJKL，则后序遍历该二叉树的结点的序列为 （ ）。 三、综合题

1、设F={T1,T2,T3}是森林，试画出对应的二叉树，其森林如下图：

A C G H B D E F I J K

2、如下图所示的二叉树：

（1）写出对它们进行先序，中序，后序遍历时得到的结点序列。 （2）画出它们的先序线索二叉树和后序线索二叉树。

A B C D E F G H

I 2

3、如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和 BDCAIFJGHE,请画出该森林。

4、假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各个字母在电文中出现的概率为5%，25%，4%，7%，9%，12%，30%，8%，试为这8个字母设计哈夫曼编码。

5、若一棵二叉树，左右子树均有三个结点，其左子树的先序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 6、已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树。

7、以数集{2，5，7，9，13}为权值构造一棵哈夫曼树，并计算带权路径长度。

3

本文来源：https://www.bwwdw.com/article/biqo.html