天津大学 - 数据结构第六章 - 树与二叉树 - 作业1

计算机科学与技术学院计算机科学与技术专业 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 8. 引入二叉线索树的目的是（）。

A.加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便插入与删除 C.为了能方便的找到双亲 D. 使二叉树的遍历结果唯一

9. 若度为m的哈夫曼树种，其叶结点个数为n，则非叶结点的个数为（）。 A. n-1 B. ?n/m?-1 C. ?(n-1)/(m-1)? D. ?n/(m-1)?-1

10. 下面几个符号串编码集合中，不是前缀编码的是（）。 A．{00,01,10,11}B. {0,1,00,11}C. {0,10,110,111}D. {1,01,000,001}

数据结构作业（第六章树与二叉树（一））第1页共7页

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

二、判断题

1. 二叉树是度为2的有序树。( )

2.给定一棵树，可以找到唯一一颗二叉树与之对应。( ) 3. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )

4. 一颗有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i

6. 在中序线索二叉树中，每一个非空的线索均指向其祖先结点。( )

三、填空题

1. 二叉树由_____________，____________，______________三个基本单元组成。 2. 已知一棵度为3的树有2个度为1的结点，3个度为2的节点，4个度为3的节点，则该树有__________个叶子结点。

3. 深度为k的完全二叉树至少有____________结点，至多有___________个结点。 4.在完全二叉树中，编号为i和j的两结点处于同一层的条件是______________。 5.设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的节点数分别为n1，n2，n3，则二叉树B的左子树中有__________个结点，右字数中有__________个结点。

6.一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_________；编号是i的结点所在的层次号是____________（根所在的层次号规定为1层）。

7. 已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是_____________________。

8. 线索二元树的左线索指向其______________，右线索指向其_______________。 9. 一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为__________________。

10. 数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_______________，带权路径长度WPL为_______________。

四、应用题

1. 一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进

数据结构作业（第六章树与二叉树（一））第2页共7页

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

行编号，求：

1）各层的结点的数目是多少？

2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？

4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？

2. 设一颗二叉树的先序、中序遍历序列分别为：先序序列：ABDFCEGH；中序序列：BFDAGEHC。 1）画出这棵二叉树。

数据结构作业（第六章树与二叉树（一））第3页共7页

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

2）画出这棵二叉树的后序线索树。 3）将这课二叉树转换成对应的树或森林。

数据结构作业（第六章树与二叉树（一））第4页共7页

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

3. 设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，试为这4个字母设计哈夫曼编码树。

4. 二叉树采用二叉链表存储：

1） 编写计算整个二叉树高度的算法。 2） 编写计算二叉树最大宽度的算法。

数据结构作业（第六章树与二叉树（一））第5页共7页

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

5. 在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并给出统计树中具有度为1的结点数目的算法。

数据结构作业（第六章树与二叉树（一））第6页共7页

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

6. 设后序线索树中结点构成为（Ltag，Lchild，Data，Rchild，Rtag）。其中Ltag，Rtag值为0时，Lchild、Rchild为当前节点的左儿子与右儿子，否则分别问直接前驱、直接后继的线索。请写出在后序线索树上找给定结点p的直接前驱q的算法。

数据结构作业（第六章树与二叉树（一））第7页共7页

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