选择题
1．在一棵高度为k的满二叉树中，结点总数为（ c ）
k-1 k kk
A．2B．2C．2-1 D．log2+1 2．高度为 K的二叉树最大的结点数为（ c ）。
kk-1kk-1
A．2 B．2 C．2 -1 D．2-1 1．已知一棵二叉树的先序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
2．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。
A．acbed B．decab C．deabc D．cedba
判断题
1. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。√ 2. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。√
1. 哈夫曼树无左右子树之分。×
2．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。√
填空题
1．8层完全二叉树至少有___128__个结点.
2. 拥有100个结点的完全二叉树的最大层数为__7__。
1．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是___4___。
2．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69__。
解答题
1. 由二叉树的中序序列及后序序列能唯一的建立二叉树，试对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。
2.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。【浙江大学 1996 六、 (8分)】 题1答案 题2答案 A A
B C B C
D E F D E F
G H G
若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。
二叉链表类型定义： typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
Status Similar(BiTree t1, BiTree t2)
/* 判断两棵二叉树是否相似的递归算法 */ {
if (!t1 && !t2) return TRUE;
else if (t1 && t2 && Similar(t1->lchild,t2->lchild) && Similar(t1->rchild,t2->rchild)) return TRUE; else return FALSE; }
6.43③ 编写递归算法，将二叉树中所有结点的左、右子树相互交换。
二叉链表类型定义： typedef struct BiTNode { TElemType data;
BiTNode *lchild, *rchild; } BiTNode, *BiTree;
void Exchange(BiTree &bt) { BiTree p;
if (bt!=NULL) { p=bt->lchild;
bt->lchild=bt->rchild; bt->rchild=p;
Exchange(bt->lchild); Exchange(bt->rchild); } }
