}，该树的度是 。 26、由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列： 后序序列：
（2009年1月）
7、高度为5的完全二叉树中含有的结点数至少为( ) A、16 B、17 C、31 D、32
8、已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A、5 B、8 C、11 D、18
9、下列所示各图中是中序线索化二叉树的是( )
21、在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有_________棵。
28、假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；
(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。 (1) (2)
31、假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { DataType data;
struct node * lchild, * rchild; //左右孩子指针 } * BinTree ;
阅读下列算法，并回答问题：
(1)已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值； (2)简述算法f31的功能。 int f31 ( BinTree T) { int d;
if ( ! T) return 0;
d = f31 ( T - > lchild) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else
return d; (1) (2)
（2009年10月）
9、已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ ） A、FEDCBA B、ABCDEF C、FDECBA D、FBDCEA
10、已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点
的个数分别为7，3，5，l，2，则与F对应的二叉树的右子树中的结点个数为（ ） A、2 B、3 C、8 D、11
21、任意一棵完全二叉树中，度为1的结点数最多为________。
27、由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。
已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。
（2010年1月）
10、下列数据结构中，不属于二叉树的是（ ） A、B树 B、AVL树 C、二叉排序树 D、哈夫曼树
21、用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)
树，该树的带权路径长度为_________。 26、假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。
已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。
34、已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{
ElmType data；
struct Node *lchild，*rchild； }*BiTree；
请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。 （2010年10月）
7、若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( )
A、树中没有度为2的结点 B、树中只有一个根结点 C、树中非叶结点均只有左子树 D、树中非叶结点均只有右子树 8、若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A、n B、 C、 +1 D、n/2
19、3个结点可以组成___________种不同树型的二叉树。
20、用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。
28、已知二叉树如下：
请画出该二叉树对应的森林。 34、已知二叉树的定义如下： typedef struct node{
int data;
struct node *lchild, *rchild; }*Bitptr；
编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）； （2011年1月）
7、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ ）
A、结点均无左孩子的二叉树 B、结点均无右孩子的二叉树
C、高度为n的二叉树 D、存在度为2的结点的二叉树
8、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ ） A、4 B、5 C、7 D、8
21、一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是________________。 31、假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data;
struct node*Ichild, *rchild; ∥左右孩子指针 } *BinTree； 阅读下列程序。 void f31(BinTree T) {
InitStack(S); ∥ 初始化一个堆栈S while (T || !StackEmpty(S) {
while (T) {
Push(S,T); T=T->lchild; }
if (!StackEmpty(S)) {
T=Pop(S); printf(“%c”,T->data); T=T->rchild; } } }
回答下列问题：
(1)已知以T为根指针的二叉树如图所示， 请写出执行f31(T)的输出结果： (2)简述算法f31的功能。
参
（2008年1月） 8、A 21、499 27、(1) root A
B ^ C
^ D ^ E ^ F ^
^ H ^ ^ I ^
(2)DHEBIFCA 32、 (1)4
(2)求二叉树的深度（高度） （2008年10月） 7、D 21、3 26、
前序序列：GHIJ 后序序列：HJIG （2009年1月） 7、A 8、C 9、A 21、4
100 28、(1)
1 0
54 46
0 1 0 1
26 28 21 25
b d 0 1 0 1 10 11 12 13 f h e 0 1
5 7
a 0 1
2 3
c g
(2)各字符的编码见下表
a b c d e f g 0101 10 01000 11 011 000 01001 31、 (1)3
(2)求二叉树双孩子结点的个数。 （2009年10月） 9、A 10、D 21、1个 27、eatst
（2010年1月） 21、WPL=219 26、GCFABD 34、
int SumNodes(BiTree T) {
if (T==NULL)//或!T return(0); else return(SumNodes (T->lchild)+ SumNodes (T->rchild)+1); }
（2010年10月） 7、B 8、A 19、5
20、WPL=33 28、 e g k a
b c d f h j 34、
int f34(Bitptr t) {
int leftdep,rightdep; if (t==NULL) return(0); else
h 001 { leftdep=f34(t->lchild); rightdep=f34(t->rchild); }
if (leftdep>rightdep) return(leftdep+1); else return(rightdep+1); }
（2011年1月） 7、C 8、B
21、最左孩子指针域leftmostchild==NULL 31、
(1)CBEDFAGH
(2)非递归中序遍历二叉树
