练习及参考答案
一 选择题：
1
2
3
4
5
6
7
8
9
10
C
C
B
B
B
C
B
D
A
D
11
12
13
14
15
D
C
B
B
B
1.下列说法正确的是（c）。
      A．二叉树中任何一个结点的度都为2.＿
      B.二叉树的度为2
      C.一棵二叉树的度可小于2
      D.任何一棵二叉树中至少有一个结点的度为2
2.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n＞0），空链域的个数为（:C )。
    A. 2n-1  B. n-1    C. n+1    D. 2n+1
3.线索化二叉树中，某结点*p没有孩子的充要条件是（B)。
    A. p->lchild=NULL    B. p->ltag二1且p->rtag=1
    C. p -> ltag=0        D. p->lchild=NULL且p->ltag=1
4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B)。
  A. 3      B. 4      C. 5        D. 1
5.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2，…，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1。这是按（B)编号的。
  A.中序遍历序列    B.先序遍历序列．  C.后序遍历序列    D.层次顺序
6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（C)个。
  A. n-1      B. n      C. n＋1    D. n＋2
7.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C)。
  A. 500      B. 501    C. 490        D. 495
8.设森林F中有3棵树，第一，第二，第三棵树的结点个数分别为N1，N2和 N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D)。
  A. N1          B.  N1＋N2        C. N2        D. N2＋ N3
  9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A)。
      A.不发生改变    B发生改变    C.不能确定      D:以上都不对
  10.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D)。
      A. cbed      B. decab    C. deabc    D. cedba
  11.若一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为dgbaechf,则后序遍霎
历的结果为（D）。
      A. gcefha    B. gdbecfha    C. bdgaechf    D. gdbehfca
  12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满
足（B）。
  A.所有的结点均无左孩子          B.所有的结点均无右孩子
  C.只有一个叶子结点              D．是一棵满二叉树
13.引人线索二叉树的目的的是（A
      A:加快查结点的前驭或后继的速度；
      B.为了能在二叉树中方便地进行插人与侧除；
      C.为了能方便地到双亲；
      D.使二叉树的遍历结果唯－；
    14:设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点
数至少为（B)。
        A. 2h      2h-1      C. 2h＋1      D. h＋1
    15.一个具有567个结点的二叉树的高h为（D）。“
        A. 9          B: 10          C: 9～566之间      D. 10 ～ 567之间
16.给定一个整数集合{3，5，6，7，9｝，与该整数集合对应的哈夫曼树是图中的（B）
      A                      B                C              D
二，判断题
1
2
3
4
5
6
7
8
9
10
×
√
×
×
√
×
先序中序后序遍历二叉树
×
×
√
×
11
12
13
14
15
16
17
18
19
20
√
×
√
×
×
×
√
×
×
√
1．二叉树是树的特殊形式。（√）
    2.由树转换成二叉树，其根结点的右子树总是空的。（√）
    3.先根遍厉，棵树和先序遍历与该树对应的二叉树，其结果不同。（x）
    4.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（x）
    5.完全二叉树中，若一个结点没有左孩子，则它必是叶子。（√）
    6.对于有N个结点的二叉树，其高度为「 log, N」＋1（х）
    7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（х）
    8.若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后
序遍历序列中的第一个结点。（х）
    9.不使用递归也可实现二叉树的先序、一中序和后序遍历。（√）
    10.先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（x）
11.先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（√）
12.在后序线索二叉树中，在任何情况下都能够很方便地到任意结点的后继。（x）
13.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（√）
14.在哈夫曼编码中，出现频率相同的字符编码长度也一定相同（x）
15.用一维数组存放二叉树时，总是以先序遍历存储结点。（x）
16.由先序序列和后序序列能唯一确定一棵二叉树。（x）
17.由先序序列和中序序列能唯一确定一棵二叉树。（√）
18.对一棵二叉树进行层次遍历时，应借助于一个栈。（x）
19.完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（x）
20.满二叉树一定是完全二叉树，反之未必。（√）
三 问答题
1.一棵度为2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？
答：度为2 的树至少有一个节点的读为2,二叉树的度不一定为2；该树不空，二叉树空以空；
树分为有序树和无序树，二叉树是有序的；二叉树有左右孩子，而树没有；二叉树度为0～２，而树的度是大于等于０
区别：度为2的树有二个分支，没有左右之分；二叉树也有两个分支，但有左右之分，且左右不能交换。
2.对于图5.38所示二叉树，试给出：
（1）它的顺序存储结构图。
 
A
B
C
D
E
F
∧
∧
∧
G
∧
∧
H
(2)二叉链表存储结构示意图
3双亲数组表示法：
A
-1
1
B
0
2
C
0
3
D
2
4
E
2
5
F
1
6
G
1
7
H
5
8
I
2
9
J
4
10
K
4
11
M
3
12
N
8
4. 无孩子且无兄弟结点是叶结点。
5
6.证明：在结点数多于1的哈夫曼树中不存在度为1的结点。
在哈夫曼树 的构造过程中，每次都是由两个权最小的结点构成一个父结点，即任一父结点都有两个子结点，故命题成立。
7. 证明：在哈夫曼树中有n个叶结点，则树一共有2n-1结点。
证明：在二叉树中n0=n2+1，即n2= n0 -1而 n1=0, 这里n0 =n
      则总结点=n0+n2=n+n-1=2n-1
8.证明由二叉树的先序序列 和中序序列可以惟一的确定一棵二叉树。
先序序列的一个结点必然是根结点，而此根结点又将中序序列分成两部分，分别是其左子树和右子树结点，这样递归查，必然可完成以确定一棵二叉树。
9.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m个结点，问，该树共有多少个叶子结点？多少个非终端结点？
答：设总结点数为n,该树中共引出的边有：
      n1 +2*n2+……+m*nm,故结点数n= n1 +2*n2+……+m*nm+1
      非终端结点数：s=n1 +n2+……+nm
叶子结点    p=n-s= n1 +2*n2+……+m*nm+1- n1 +n2+……+nm
                =n2+……+(m-1)*nm
  10.在具有n(n>1)个结点的树中，深度最小的那棵树的度是多少？它共有多少叶子和非叶子结点?深度最大的那棵树的度是多少？它共有多少叶子和非叶子结点?
答：深度最小的那棵树的度是2， n-1个叶子和1个非叶子结点。
深度最大的那棵树的度是n， 1个叶子和n-1个非叶子结点。
11.设度为h的二叉树上只有度为0 和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。
结点数最大值：2h-1
最小值:2h-1
12.    求表达式(a+b*(c-d)-e/f的波兰式（前缀式）和逆波兰式（后缀式）
  -+a*b-cd/ef
  abcd-*+ef/-
13.画出和下面已知序列对应的树
  树 的先根次序访问次序为：GFKDAIEBCHJ
  树 的后根次序访问次序为：DIAEKFCJHBG
解：根据树与二叉树的转换关系以及树和二叉树的遍历定义可以推知，树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同；树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同。故可按二叉树的规则建立二叉树，然后转换成树。
二叉树：
   
13.画出和下面已知序列对应的森林
  森林的先根次序访问次序为：ABCDEFGHIJKL
  森林的后根次序访问次序为：CBEFDGAJIKLH
解：根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推知，森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同。
先画出二叉树→森林
15.画出和下面已知序列对应的树T
  二叉树的层次访问次序为：ABCDEFGHIJKL
  二叉树的中序访问次序为：CBEFDGAJIKLH
16.假设用于通信的电文字符集{a,b,c,d,e,f,g,}中的字母构成，这7个字母在电文中出现的概率分别为{0.31，0.16，0.10，0.08，0.11，0.20，0.04}

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