7.【96程试题1】二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历 次序有六种。最常用的是三种:前序法(即按NLR次序),后序法(即按LRN次序)和中序 法(也称对称序法,即按LNR次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH,中序序列是 FEBGCHD,则它的后序序列必是 FEGHDCB 解:法1:先由已知条件画图,再后序遍历得到结果; 法2:不画图也能快速得出后序序列,只要找到根的位置特征。由前 序先确定root,由中序先确定左子树。例如,前序遍历 BEFCGDH中 根结点在最前面,是B;则后序遗历中B一定在最后面。 法3:递归计算。如B在前序序列中第一,中序中在中间(可知左 右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同 样处理,则问题得解 8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为On) 答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次 9.【计算机研2001】用5个权值吕3,24,5,1}构造的哈夫曼( Huffman)树的带权路径长度是 解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33 (注:两个合并值先后不同会导致编码不同,即哈夫曼编码不唯一) (注:合并值应排在叶子值之后) (注:原题为选择题:A.32 B.33 D.15) 三、单项选择题(每小题1分,共11分) C)1.不含任何结点的空树 A)是一棵树 B)是一棵二叉树; (c)是一棵树也是一棵二叉树; D)既不是树也不是二叉树 答:以前的标答是B,因为那时树的定义是n≥1 (C)2.二叉树是非线性数据结构,所以 (A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储 (c)顺序存储结构和链式存储结构都能存储;(D)顺序存储结构和链式存储结构都不能使用 (C)3.〖01年计算机研题〗具有nn>0)个结点的完全二叉树的深度为 (A)log2(n)1 (B)Llog2(n)J(C)Llog2 (n)H1 (D)log2(n)+l 注1:x表示不小于x的最小整数:Lx表示不大于x的最大整数,它们与门]含义不同! 注2:选(A)是错误的。例如当n为2的整数幂时就会少算一层。似乎log(m)+1是对的? (A)4.把一棵树转换为二叉树后,这棵二叉树的形态是 A)唯一的 (B)有多种 (c)有多种,但根结点都没有左孩子(D)有多种,但根结点都没有右孩子 5.【94程P11】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在 答卷的对应栏内。 树是结点的有限集合,它Δ根结点,记为T。其余的结点分成为m(m≥0)个B2 7. 【96 程试题 1】 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历 次序有六种。最常用的是三种：前序法（即按 N L R 次序），后序法（即按 L R N 次序）和中序 法（也称对称序法，即按 L N R 次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH，中序序列是 FEBGCHD，则它的后序序列必是 F E G H D C B 。 解：法 1：先由已知条件画图，再后序遍历得到结果； 法 2：不画图也能快速得出后序序列，只要找到根的位置特征。由前 序先确定 root，由中序先确定左子树。例如，前序遍历 BEFCGDH 中， 根结点在最前面，是 B；则后序遍历中 B 一定在最后面。 法 3：递归计算。如 B 在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对 B 的左右子树同 样处理，则问题得解。 8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为 O(n) 。 答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度 k+1，包括叶子的空域也递归了一次。 9. 【计算机研 2001】 用 5 个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 WPL＝（4＋5＋3）×2＋（1＋2）×3=33 (15) (9) (6) （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) （注：合并值应排在叶子值之后） 1 2 （注：原题为选择题：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15） 三、单项选择题（每小题 1 分，共 11 分） （ C ）1． 不含任何结点的空树 。 （Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 答：以前的标答是 B，因为那时树的定义是 n≥1 （ C ）2．二叉树是非线性数据结构，所以 。 （Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用 （ C ）3. 〖01 年计算机研题〗 具有 n(n>0)个结点的完全二叉树的深度为 。 (Ａ) log2(n) (Ｂ) log2(n) (Ｃ) log2(n) +1 (Ｄ) log2(n)+1 注 1：x 表示不小于 x 的最小整数； x表示不大于 x 的最大整数，它们与[ ]含义不同！ 注 2：选（A）是错误的。例如当 n 为 2 的整数幂时就会少算一层。似乎log2(n) +1是对的？ （ A ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 。 （Ａ）唯一的 （Ｂ）有多种 （Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 5. 【94 程 P11】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在 答卷的对应栏内。 树是结点的有限集合，它 A 根结点，记为 T。其余的结点分成为 m（m≥0）个 B