第 6 章
习题
1 、 填空题
1 、深度为 k 的二叉树共有 2 k-1 个结点，该二叉树为 二叉树。
2 、二叉树在二叉链表方式下，p 指向二叉树的一个结点，p 结点无右孩子
的条件是 。
3 、每个二叉链表必须有一个指向 结点的指针，该指针具有标识二
叉链表的作用。
4 、有 m 个叶结点的哈夫曼树上结点的数目是 。
5 、哈夫曼树是带权路径长度 的树，通常权值较大的结点离根
。
6 、设一棵二叉树中只有叶子结点和左、右子树都非空的结点，如果叶子 结点的个数是 m ，则左、右子树都非空的结点个数是 。
1 、如果结点 A 是结点 B 的双亲，而且结点 B 有 4 个兄弟，则结点 A 的度 是（ ）。
A ．2 B ．3 C ．4 D ．5
2 、用顺序存储结构将完全二叉树的结点逐层存储在数组 B[ n] 中，根结点 从 B[ 1]开始存放，若结点 B[i]有子女，则其左孩子的结点应是（ ）。
A ．B[ 2i-1] B ．B[ 2i + 1 ] C ．B[ 2i] D ．B[i/ 2]
3 、以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中 （n > 0 ），空链域的个数为（ ）。
A ．2 n-1 B ．n-1 C ．n + 1 D ．2 n + 1
4 、在一棵非空的二叉树的中序遍历序列中，其根结点的右边（ ）。
A ．只有右子树上的所有结点 B ．只有左子树上的所有结点
C ．只有右子树上的部分结点 D ．只有左子树上的部分结点 5 、在如图 6 . 2 5 所示的二叉树中，不是完全二叉树的是（ ）。
A ． B ． C ． D .
图 6.25 选择题 5 的附图
6 、二叉树以二叉链表存储，若指针 p 指向二叉树的根结点，经过运算 s = p ; while （s-> r child ）s = s-> r child 后，则( )
A ．s 指向二叉树的最右下方的结点 B ．s 指向二叉树最左下方的结
点
C ．s 指向根结点 D ．s 为 NULL
3 、 判断题
1 、二叉树也是树。 ( )
2 、已知二叉树的先序序列和后序序列，则可以唯一确定一株二叉树。
( )
3 、 完 全 二 叉 树 中 ，若 一 个 结 点 没 有 左 孩 子 ，则 它 必 须 是 叶 子 。 ( )
4 、 在 结 点 数 多 于 1 的 哈 夫 曼 树 中 没 有 度 为 1 的 结 点 。 ( )
5 、若一个结点是某二叉树先序遍历序列的最后一个结点，则它必是该二 叉树中序遍历序列中最后一个结点。
（ ）
4 、 应用题
1 、试分别画出具有 3 个结点的无序树和 3 个结点的二叉树的所有不同形
态。
2 、已知一棵度为 k 的树中有 n 1个度为 1 的结点，n 2 个度为 2 的结点， … ， n k 个度为 k 的结点，试问该树中有多少个叶结点。
3 、找出所有满足下列条件的二叉树： （ 1 ）先序遍历和中序遍历序列相同； （2 ）后序遍历和中序遍历序列相同； （3 ）先序遍历和后序遍历序列相同。
4 、分别画出图 6 . 2 6 所示二叉树的二叉链表和顺序存储结构。
5 、写出对图 6 . 2 7 所示二叉树进行先序、中序、后序遍历的结点序列，并 画出该二叉树的先序线索二叉树。
6 、已知一株二叉树的中序遍历序列为 ABCDE FG ，后序遍历序列为
BDCAFGE ，写出该二叉树的先序遍历序列。
B 
C A F 
E 
D I
图 6.26 二叉树 图 6.27 二叉树
7 、将图 6 . 2 8 所示的森林转换成二叉树。
G
J
A
H
B
C
N
K L
E
F
I
M
D
图 6.28 森林
8 、给定权值 7 ，1 4 ，3 ，3 2 ，5 ，1 2 ，构造相应的哈夫曼树。
5 、 算法设计题
1 、 编写一算法求中序线索二叉树中某一结点 p 的前驱结点。 2 、 编写一算法交换二叉树中所有结点的左、右子树。
评论0