第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 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、0B、1
C、48
D、49
21、假设用<x,y>表示树的边（其中x是y的双亲），已知一棵树的边集为{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>}，该树的度是。
26、由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序
列和后序序列。
前序序列：后序序列：
（2009年1月）
7、高度为5的完全二叉树中含有的结点数至少为(      )A 、16B 、17C 、31D 、32
8、已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为(      )A 、5B 、8C 、11D 、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={T 1，T 2，T 3，T 4，T 5}，各棵树T i (i=1，2，3，4，5)中所含结
点的个数分别为7，3，5，l ，2，则与F 对应的二叉树的右子树中的结点个数为（  　）A 、2B 、3C 、8D 、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 、        +1D 、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
的功能。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。