作业-树和二叉树

1、作业-树和二叉树树（树根结点的高度为1）一、选择题3.以下说法错误的是（）。A.完全二叉树上结点之间的父子关系可由它们 编号之间的关系来表达B.在三叉链表上，二叉树的求双亲操作很容易 实现C.在二叉链表上，求根以及求左、右孩子等操 作很容易实现D.在二叉链表上，求双亲操作的时间性能很好4.以下说法错误的是（）。A. 一般在哈夫曼树中，权值越大的叶子离根结 点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的 哈夫曼树共有2n-1个结点D.若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼 树5 .深度为6的二叉树最多有（）个结点。A. 64

2、B. 63 C. 32 D. 316 .将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（）。A. 10B. 11 C. 41 D. 207 .设深度为k的二叉树上只有度为0和度为2 的结点，则这类二叉树上所含结点总数最少（）个。A. k+l B. 2k C. 2k-1 D. 2k+18 .下列说法中正确的是（）。A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为 2C.任何一棵二叉树中的每个结点的度肯定等于2D.任何一棵二叉树中的每个结点的度都可以小于29 . 一棵二叉树满足下列条件：

3、对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（）遍历方式就可以得到这棵二叉树所有结点的递减序列。A.前序 B.中序 C.后序 D.层次10 .如图6-1所示的二叉树的中序遍历序列是 ()。A. abcdgef B. dfebagcC. dbaefcgD. defbagcVM 11 .已知某二叉树的后序遍历序列是 deach中 序遍历序列是deabq它的前序遍历序列是（）。A. acbed B. baedc C. dceab D.cedb12 .某二叉树的前序遍历的结点访问顺序是 abdgcefhdgbaechf则其后序遍历的结点访问顺序

4、是（）A. bdgcefha B. gdbecfha C. bdgechfaD. gdbehfca13.在图6-2中的二叉树中，（c杯是完全二叉树。14 .树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据15 .哈夫曼树的带权路径长度是（）。A.所有结点权值之和B.所有叶结点带权路径长度之和C.带权结点的值D.除根以外所有结点权值之和16 .设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点。A. 6B. 7 C. 8 D. 1117 .已知完全二叉树有26个结点，则整棵二叉 树有（）个度为1的结点。A. 0B.

5、1C. 2 D. 1318 .已知如图6-3所示的哈夫曼树，那么电文 CDAA的编码是（）。A. 110100 B. 11011100 C. 010110111D. 1111110019 .在n个结点的完全二叉树中，对任一结点i（1< i< n）,i的左孩子可能是（）。A. i/2 B. 2i+1 C. 2i D.都不是20 .已给出图6-3所示的二叉树，A, B, C, D的权值分别为7, 5, 2, 4, 则该树的带权路径长度为（）。A. 46B. 36C. 35 D.都不是21 .下列叙述中正确的是（）。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二

6、叉树中必有度为2的结点D.二叉树中结点最多有两棵子树，并且有左右 之分22.图6-4所示的几种结构中属于树形结构的是 (b)。二、判断题(标红色的是错误的)2 .树和二叉树之间最主要的差别是： 二叉树的结点的子树要区分为左右子树， 即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。3 .若有一个结点是某二叉树子树的中序遍历序 列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一 个结点。4 .二叉树具有两个子女的父结点，在中序遍历 序列中，它的后继结点最多只能有一个子女。5 .在二叉树中，具有一个子女的父结点， 在中序遍历中，它没有后继的子女结点。6 .已知二叉树的前

7、序遍历和后序遍历序列不能 惟一地确定这棵树。三、填空题1 .树(及一切树形结构)是一种分支层次 结构。在树中，H 结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的双亲O2 . 一棵树上的任何结点(不包括卞K本身)称为根的 子孙。若B是A的子孙，则称A是B的祖先。3 .二叉树第i(i>0)层上至多有2i-1个结点。4 .深度为k(k>0)的二叉树至多有 2k-1个结点。5 .对任何二叉树，若度为2的节点数为n2,则叶子数 n0=_n2+1 o6 .满二叉树上各层的节点数已达到了二叉树可 以容纳的 最大值。满二叉树也是 完全 二叉树，但反之不7 .具有n个结点的完

8、全二叉树的深度为 10g2n 取整+1。8 .二叉树通常有 J顿序:存储结构和链式:存储结构两类存储结构。9 .每个二叉链表还必须有一个指向根结点的指针，该指针具有标识二叉链表的作用。10 .对二叉链表白访问只能从 t指针开始。11 .二叉树有不同的链式存储结构，其中最常用 的是二叉链表与三叉链表。12 .具有100个结点的完全二叉树的深度是713 .在 先序遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。14 .若一棵二叉树的叶子数为n,则该二叉树中左、右子树皆非空的结点个数为n-1 o15 . 一棵树的形状如图6-5所示,它的根结点是 A ,叶结点是_E, J, K,G, L, O, P, Q, R, N, I,结点H的度是3,这棵树的度是4这棵树的深度是 5结点F的儿子结点是J, K,结点G的父结点是 C?18.含有2n个结点的二叉树高度至少是_n+1,至多是_2n 仅含根结点的二叉树高度为1）。四、应用题1 .分别写出图6-7所示二叉树的前序、中序和后 序序列。3I I答：前序：ABCDEF、中序：CBEFDA和后序:CFEDBA2 .已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG 和DECBHGFA ,试画出这棵二 叉树，并写出其前序遍历序列。答：前序遍历序列：ABCDEFGH3 .设某密码电文由8个字母组成，a,b,c,d,e,f