第6章 树
（2008年1月）
8、树的先根序列等同于与该树对应的二叉树的（ ） A、先序序列 B、中序序列 C、后序序列 D、层序序列
21、假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。 27、已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF， (1) 画出该二叉树的二叉链表存储表示; (2) 写出该二叉树的后序序列。 (1) (2)
32、已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题： (1) 设二叉树T如图所示,写出执行f32(T)的返回值; (2) 简述算法f32的功能。 int f32(BinTree T) {
int m, n; if(! T)
return 0; else{
m= f32(T–>lchild); n = f 32(T–>rchild); if(m>n)return m +1; else return n+1; } } (1) (2)
（2008年10月） 7、已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ） A、 0 B、 1 C、 48 D、 49
21、假设用
前序序列： 后序序列：
（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的功能。