第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、假设用<x,y>表示树的边（其中x是y的双亲），已知一棵树的边集为
{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>}，该树的度是                    。
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、已知二叉树如下：
请画出该二叉树对应的森林。

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