练习题1-6章（含答案）

为CBAEDF,则后序遍历的结果为（ c ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定

24. 线索二叉树是一种（ c ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 25．n个结点的线索二叉树上含有的线索数为（ c ）

A．2n B．n－l C．n＋l D．n 26．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ c ）

【南开大学 2000 一、2】

A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树

27．下述编码中哪一个不是前缀码（ b ）。

A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）

28．下面几个符号串编码集合中，不是前缀编码的是（ b ）。

A

．

{0,10,110,1111}

B．{11,10,001,101,0001} C．{00,010,0110,1000} 二、应用题

G 1、将下列由三棵树组成的森林转换为二叉树。（只要求给 J H I 出转换结果）

A B D E F K L M N O

P C

44. 森林转为二叉树的三步：

A B C E D G H （１）连线（将兄弟结点相连，各树的根看作兄弟）； F I KO （２）切线（保留最左边子女为独生子女，将其它子女分枝切P N L J M 掉）；

O （３）旋转（以最左边树的根为轴，顺时针向下旋转45度）。 其实经过（１）和（２），已转为二叉树， 执行（３）只是为了与平时的二叉树的画法一致。

2、已知二叉树的先序序列: CBHEGAF, 中序序列:

HBGEACF, 试构造该二叉树

3、已知一个森林的先序序列和后序序列如下，请构造出该森林。

先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK

4、、定一组数列（15,8,10,21,6,19,3）分别代表字符

A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，

画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。 三、算法设计题：

1. 二叉树的创建 2. 求叶子个数

3. 求总的结点个数 4. 求树的深度 5. 对树进行层次遍历

6. 进行查询特定元素等算法。