6.答案：本题利用栈的“后进先出”的特点，有如下几种情况： A进、A出、B进、B出、C进、C出，产生输出序列ABC A进、A出、B进、C进、C出、B出，产生输出序列ACB A进、B进、B出、A出、C进、C出，产生输出序列BAC A进、B进、B出、C进、C出、A出，产生输出序列BCA A进、B进、C进、C出、B出、A出，产生输出序列 CBA 不可能产生输出序列CAB。
四、应用题答案
1. 该算法的输出结果为：44 32 38 24 15 36 20 2. 该算法的输出结果为：15 12 8 5 130 30 3. 该算法的输出结果为：12 15 5 30 18 4. 该算法的输出结果为：23 78 56 19 34
第5章 树与二叉树
一、单选题
1. 树最适合用来表示（ ）。
A）有序数据元素 B）无序数据元素
C）元素之间具有分支层次关系的数据 D）元素之间无联系的数据
2. 树中所有结点的度等于所有结点数加（ ）。
A）1 B）0 C）-1 D）2 3.在一棵树中，（ ）没有前件（前驱）结点。
A）分支（树枝）结点 B）叶子结点 C）树根结点 D）空结点
4. 在一棵树中，每个结点最多有（ ）个前件结点。
A）0 B）1 C）2 D）任意多
5. 在一个具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。
A）n B）n+1 C）n -1 D）2n
6. 按照二叉树的定义，具有3个结点的二叉树，共有（ ）种。
A）3 B）4 C）5 D）6
7. 在一棵二叉树的二叉链表中，空指针域个数等于非空指针数域个数加（ ）。
A）2 B）1 C）-1 D）0
8. 在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。
A）2 B）2
i
i -1
C）2-1 D）2
i n
9. 在一棵深度为h的完全二叉树中，所含结点个数不小于（ ）。
A）2 B）2 C）2 –1 D）2 10. 深度为6的二叉树，最多有（ ）个结点。
A）32 B）64 C）63 D）20
21
h
h+1
h
h-1
11. 在一棵深度为h的完全二叉树中，所含结点个数不大于（ ）。
A）2 B）2 C）2 –1 D）2
12. 在一棵具有35个结点的完全二叉树中，该树的深度为（ ）。
A）5 B）6 C）7 D）8
13. 在一棵具有n个结点的完全二叉树中，树的分支结点的最大编号为（ ）。
A）?(n+1)/2? B）?(n - 1)/2? C）?n/2? D）?n/2? 14. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号为（ ）。
A）2i - 1 B）2i C）2i+2 D）2i+1 15. 在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点的编号为（ ）。
A）2i - 1 B）2i C）2i+2 D）2i+1
16. 在一棵完全二叉树中，对于编号为i（i>1）的结点，其双亲结点的编号为（ ）。
A）?(i+1)/2? B）?(i - 1)/2? C）?i/2? D）?i/2? 17. 在深度为5的满二叉树中，叶子结点的个数为（ ）。
A）15 B）16 C）32 D）31 18. 对一棵满二叉树，有m个树叶，n个结点，深度为h，则有（ ）。
A）n=h+m B）m=h - 1 C）n=2- 1 D）2n=2h+m 19. 在一非空二叉树的中序遍历序列中，根结点的右边（ ）。
A）只有右子树上的所有结点 B）只有右子树上的部分结点 C）只有左子树上的所有结点 D）只有左子树上的部分结点
20.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ）。
A）空或只有一个结点 B）完全二叉树
C）二叉排序树 D）高度等于其结点数的二叉树
21.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。
A）发生改变 B）不发生改变 C）不能确定 D）以上都不对 22.利用n个值生成的哈夫曼树中共有（ ）结点。
A）n B）n+1 C）2n D）2n - 1
23.利用3，6，8，12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（ ）。
A）38 B）58 C）29 D）55
24.利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。
A）6 B）5 C）4 D）3 25.依据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。
A）000,001,010,011,1 B）0000,0001,001,01,1 C）000,001,01,10,11 D）00,100,101,110,111 26. 依据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。
A）111,110,10,01,00 B）000,001,010,011,1 C）100,11,10,1,0 D）001,000,01,11,10
二、填空题
1. 数据的逻辑结构有线性结构和非线性结构之分，树(tree)属于 。
2. 树的固有特性为，一棵树是由 的，而子树又可由若干个 构成。 3. 一个结点的子树数称为该结点的 。
4. 在树中，所有结点中的 称为树的度。
h
h
h+1
h
h-1
22
5.对于一棵具有n个结点的树，该树中所有结点的度之和为 。
6.在一棵树中， 结点没有前件结点，其余每个结点有并且只有一个 结点，可以有任意多个 结点。
7. 在树中，结点的子树的根，称为该结点的 ，相应地，该结点称为孩子的 。
8. 在树中，各结点的层的最大值，称为树的 。
9. 如果树中任一结点的各棵子树规定 是有次序的，即不能互换位置，则称该树为有序树，否则称为无序树。
10. n（n≥0）棵互不相交的树的集合，称为 。 11. 依据二叉树的定义，二叉树共有 基本形态。
12. 假设一棵完全二叉树的深度为k，由完全二叉树的定义知，它的k - 1层，是深度为 k - 1的 。
13.一棵深度为5的完全二叉树中结点数最少为 个，最多为 个。 14.设一棵完全二叉树共有700个结点，则在该二叉树中有 个叶子结点。 15.对一棵二叉树，一个结点的编号为i，若它的左孩子结点存在，则其编号为 ；若右孩子结点存在，则其编号为 ；若双亲结点存在，则编号为 。
16.在一棵二叉树中，第6层上的结点数最多为 。
17.假设一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。 18.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0= 。 19.一棵二叉树的第i层最多有 个结点；一棵有n (n>0)个结点的满二叉树， 共有 个叶子结点和 个非叶子结点。（提示：假设有n个结点的满二叉树高度为h，则有n=2–1，即h=log2(n?1) ，第h层的结点为叶结点，前h -1层的结点
为非叶结点）
20.结点最少的树为 ，结点最少的二叉树为 。 21. 存储二叉树，通常有 结构和 结构。
22.二叉链表是二叉树最常用的存储结构。通过二叉链表结点的 可以立即找到它的左、右孩子，但不能直接找到它的 。
23. 遍历一棵二叉树，就是按照某种规则去访问二叉树的每个结点，而且每个结点 。
24.在遍历二叉树时，如果限定先左子树后右子树，根据访问根结点的次序，则有3种遍历方法，分别称为 。
25. 从树中一个结点到另一个结点之间的 构成这两个结点之间的路径，路径上的 称为路径长度。
26.对一棵具有n个结点的二叉树，对应二叉链表中的指针总数为 个，其中 个用于指向孩子结点， 个指针空闲着。
27. 树中所有叶子结点的带权路径长度之和称为树的 。
28. 哈夫曼（Huffman）树，又称最优二叉树，是一类 最短的二叉树。 29.若由3,6,8,12,10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 ，带权路径长度为 。
30.已知一棵二叉树的先序和中序遍历序列如下： 先序遍历序列：A，B，C，D，E，F，G，H，I，J 中序遍历序列：C，B，A，E，F，D，I，H，J，G
则其后序遍历序列为： 。
h
23
31.已知一棵二叉树的中序遍历和后序遍历序列如下： 中序遍历序列：C，B，D，E，A，G，I，H，J，F 后序遍历序列：C，E，D，B，I，J，H，G，F，A
则其先序遍历序列为： 。
32.已知一棵二叉树的先序和后序遍历序列如下： 先序遍历序列：A，B，D，E，C，F 后序遍历序列：D，E，B，F，C，A
则其中序遍历序列为： 。
33.有7个带权结点，其权值分别为3，7，8，2，6，10，14，以它们为叶子，生成一棵哈夫曼树，则带权路径长度为 ，高度为 ，双分支结点数为 。
三、简答题
1. 简述树的定义。 2. 简述二叉树的定义。
3. 简述树与二叉树的主要差别。 4. 什么是完全二叉树？
5. 简述采用顺序编号的完全二叉树所具有的性质（一般二叉树的性质除外）。 6. 简述先序遍历二叉树的递归定义。
四、算法设计
1.设以二叉链表为二叉树的存储结构，结点的结构如下图所示，其中data为整数。试设计一个算法void change(BiTree r),使当结点的左孩子的值域的值大于右孩子的值域的值时，则交换其左、右子树。
lchild data rchild
2.设计一个算法int count(BiTree r,datatype x)，统计出二叉树中大于给定值x的结点个数，该统计值由函数返回。
3.设计一个算法void preserve(BiTree r,datatype a[],int n)，对具有n个结点的二叉树进行中序遍历，并把遍历得到的结点值序列保存到数组中。
参考答案
一、单项选择题
1.C 2.C 3.C 4.B 5.B 6.C 7.A 8.B 9.D 10.C 11.C 12.B 13.D 14.B 15.D 16.D 17.B 18.C 19.A 20.D 21.B 22.D 23.D 24.C 25.D 26.C
二、填空题
24
1. 非线性结构 2. 若干子树构成，更小的子树 3. 度 4. 最大的度
5. n - 1 6. 根，前件（或双亲），后件（或孩子） 7. 孩子，双亲 8. 深度或高度 9. 从左至右 10. 森林 11.5种 12. 满二叉树 13. 16，31 14. 350 15. 2i，2i+1，i/2或 ?i/2? 16. 32 17. 5，18 18. n2+1 19. 2
i-1
，2的[log2(n?1)]-1次幂，2的[(log2(n?1) )-1]次幂减1，即叶结点数
减1
20. 只有一个结点的树，空的二叉树
21. 顺序存储，链式存储 22. 左、右孩子指针，双亲
23. 仅被访问一次 24. 先序遍历、中序遍历和后序遍历 25. 分支， 分支数目 26. 2n，n -1，n+1 27. 带权路径长度 28. 带权路径长度
29. 4，87 30.（C，B，F，E，I，J，H，G，D，A） 31.（A，B，C，D，E，F，G，H，I，J）
32.（D，B，E，A，F，C）or (D, B, E, A, C, F) 33. 131，5，6
三、简答题
1. 答案：树（Tree）是n ( n ≥ 0 )个结点的有限集T。当n=0时，称为空树；当 n>0 时， 该集合满足如下条件：
①有且仅有一个特定的称为根（root）的结点；
②其余的结点可分为m（m ≥ 0）个互不相交的子集T1，T2，...，Tm，其中每个子集本身又是一棵树，并称其为根的子树（SubTree）。
2. 答案：二叉树是n（n ≥ 0）个结点的有限集，它或者是空集（n = 0），或者是由一个根结点和两棵互不相交的且分别称为根的左子树和右子树的二叉树组成。
3. 答案：树与二叉树的主要差别为：树的结点个树至少为1，而二叉树的结点个数可以为0；树中结点的最大度没有限制，而二叉树结点的最大度为2；树的结点没有左、右之分，而二叉树的结点有左、右之分。
4. 答案：一棵深度为K、有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
5. 答案：采用顺序编号的完全二叉树具有以下性质（一般二叉树的性质除外）： ①若i=1，则结点i是二叉树的根，无双亲；如果i>1，则该结点的父结点编号为 ?i/2?。 ②若2i ≤ n，则结点i的左孩子是结点2i；若2i > n，则结点i无左孩子。
③若2i+1 ≤ n，则结点i的右孩子是结点2i+1；若2i+1 > n ，则结点i无右孩子。
6. 答案：先序遍历二叉树的递归定义为：若二叉树为空，则遍历结束；否则，执行下列步骤：先访问根结点，然后遍历根的左子树，最后遍历根的右子树，并且在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后右子树。
四、算法设计
1. 当r二叉树中每个结点的左孩子的值大于右孩子的值时，交换左右子树。
void change(BiTree r)
25