树和二叉树 - 习题

第六章 树和二叉树

一、单项选择题

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和度为2的结点，则此类二叉树中所包含的结点数至 少为( ) A.2h B.2h-1 C.2h+1 D.h+1

8. 在一棵非空二叉树的中序遍历序列中，根结点的右边 ( ) A.只有右子树上的所有结点 B. 只有右子树上的部分结点 C.只有左子树上的所有结点 D.只有左子树上的部分结点

9. 一棵二叉树的广义表表示为a(b(c,d)e(,f(g))),则得到的中序遍历序列为( ) A.a,b,c,d,e,f,g B.c,b,d,a,e,g,f C.c,d,b,g,f,e,a D.a,b,e,c,d,f,g

10. 任何一颗二叉树的叶结点在先序，中序和后序遍历中的相对次序( ) A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

11. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为( ) A.|_(n+1)/2_| B. |_(n-1)/2_| C. ?n/2?

D. |_n/2_|

12. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则右孩子结点的编号为( ) A.2i B.2i-1 C.2i+1 D.2i+2

13. 在一棵完全二叉树中，对于编号为i的结点(i>1)，其双亲结点的编号为( ) A. |_(i+1)/2_| B. |_(i-1)/2_| C. ?i/2?

D. |_i/2_|

14. 按照二叉树的定义，具有3个结点的二叉树有__种( ) A.3 B.4 C.5 D.6

15. 深度为5的二叉树至多有__个结点( ) A.16 B.32 C.31 D.10 16.利用n个值生成的哈夫曼树中共有___个结点( ) A.n B.n+1 C.2n D.2n-1

17. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为( A)

A.55 B.29 C.58 D.38 二、填空题

1．对于一棵具有n个结点的树，该树中所有结点的度数之和为 ________个。

2．一棵深度为8完全二叉树第8层有7个结点，则共有______个结点，其中度为1的结点有_______个，度为0的结点有_______个，度为2的结点有______个，编号最大的非叶子结点是______，编号最小的叶子结点是______。

3．一棵深度为6的完全二叉树的第6层有6个结点，则叶子结点有 个。

4．在一棵三叉树中，假定双分支结点数为5个，三分支结点数为6个，单分支结点数为6个，则叶子结点数为____个。

5．指出树和二叉树的三个主要差别

____________________________,__________________________,__________________________________. 三、应用题

1．如图所示的二叉树，回答以下问题。

（1）分别写出该二叉树的先序遍历序列，中序遍历序列，后序遍历序列 （2）画出该二叉树对应的森林。

abdgehicf 2．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，回答以下问题； （1）画出该二叉树

（2）给出后序遍历序列。 (3) 将此二叉树还原成森林

3.有一份电文中 0使用5个字符：a、b、c、d、e,它们的出现频率依次为4,7,5,2,9,

（1）试画出对应的哈夫曼树，（按左子树根结点的权小于等于右子树根结点的权构造） （2）求出每个字符的哈夫曼编码 （3）求出按出现的频率为权的WPL 四、算法设计题

1． 设以二叉链表为二叉树的存储结构， lchild data rchild 其中data为整数，试设计一个算法void change(BiTree *r)，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左右子树。

2． 设计一个算法，对具有n个结点的二叉树进行中序遍历，把遍历得到的结点值序列保存 到数组中void preserve(BiTree *r,ElemType a[],int n)。

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