数据结构第6章二叉树答案

1、第 6 章树和二叉树一、下面是有关二叉树的表达，请判断正误每题1 分，共 10分71.假设二叉树用二叉链表作存贮结构， 那么在 n 个结点的二叉树链表中 只有 n1 个非空指针域。X 2. 二叉树中每个结点的两棵子树的高度差等于 1。V 3. 二义树中每个结点的两棵子树是有序的。X 4. 二义树中每个结点有两棵非空子树或有两棵空子树。X 5. 二叉树中每个结点的关键字值大于其左非空子树假设存在的话所有结点的关键字值，且小于其右非空子树假设存在的话所有结点的关键字 值。应当是二叉排序树的特点X 6. 二义树中所有结点个数是 2k-l-l, 其中 k 是树的深度。应 2i- 1X 7. 二叉树中所

2、有结点，如果不存在非空左子树， 那么不存在非空右子 树。 X 8. 对于一棵非空二叉树，它的根结点作为第一层，那么它的第i 层上 最多能有 2i1 个结点。应 2i-lV 9. 用二叉链表法 link-rlink 存储包含 n 个结点的二叉树，结点 的 2n 个指针区域中有 n+1 个为空指针。正确。用二义链表存储包含n个结点的二义树，结点共有2n个链域。山于 二叉树中， 除根结点外， 每一个结点有且仅有一个双亲， 所以只有 n-l 个结点的链 域 存放指向非空子女结点的指针，还有 n+1个空指针。即有后继链接的指针仅 nT 个。V 10. K01 年计算机系研题 具有 12个结点的完全二义树

3、有 5个度 为 2 的结点。最快方法：用叶子数 =n/2=6, 再求 n2=n0-l=5二、填空每空 1分，共 15 分1. 由 3 个结点所构成的二叉树有 5 种形态。2. 【计算机研 2000 一棵深度为 6的满二义树有 nl+n2 二 0+ n2= n0- 1=31个分支结点和 26-1 =32 个叶子。注：满二叉树没有度为 1 的结点，所以分支结点数就是 ?二度结点数。3. 一棵具有 2 5 7个结点的完全二叉树，它的深度为9 o注：用 log2 n +1 二 8. xx +1=94. 【全国专升本统考题】设一棵完全二义树有 700 个结点，那么共有 350 个叶子结点。答：最快方法：

4、用叶子数 =n/2=3505. 设一棵完全二义树具有 1000个结点，那么此完全二义树有 500 个叶子结 点，有 499 个度为 2 的结点，有 1 个结点只有非空左子树，个结点只有非空右子树。答：最快方法：用叶子数=n/2=500 , n2=n0-l=499o另外，最后一结点 为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二义树的特点决定不可能 有左空右不空的情况，所以非空右子树数 =0.6. 【严题集6.731 一棵含有n个结点的k义树，可能到达的最大深度 为n , 最小深度为2。答：当01 单义树时应该最深，深度=n 层；当k二n-l n-1 X树时应 该最浅，深度=2 层

5、，但不包括n二0或1时的特例情况。教材答案是“完全 k 叉树,未定量。7. 【96程试题11二义树的根本组成局部是：根N 、左子树L 和右子树R o因而二义树的遍历次序有六种。最常用的是三种：前序法即按 L R次序, 后序法即按L R N次序和中序法也称对称序法，即按 L NR次序。这三种 方法相互之间有关联。假设一棵二义树的前序序列是BEFCGDH,中序序列是FEBGCHD.那么它的后序序列必是F E G H D CBo解：法1:先由条件画图，再后序遍历得到结果；法2:不画图也能快速得出后序序列，只要找到根的位置特征。山前序先确定root,山中序先确定左子树。例如，前序遍历BEFCGDH中，

6、根结点在最前面，是B; 那么后序遍历中B-定在最后面。法3:递归计算。如B在前序序列中第一，中序中在中间可知左右子树上 有 哪些元素，那么在后序中必为最后。如法对 B的左右子树同样处理，那么问题得 解。8? 【全国专升本统考题】中序遍历的递归算法平均空间复杂度为 0 (n) o答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度 k+1, 包 括叶子的空域也递归了一次。9.【计算机研2001 用5个权值 3, 2, 4, 5, 1构造的哈夫曼(Huffman)树的 带权路径长度是33。解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 WPL= (4 + 5 +3) X2+ (1 +

7、 2) X3 二 33(15)B注：两个合并值先后不同会导9)致编 码不 同，即 哈夫 曼编 码不 唯一)三、单项选择题 ( 每题 1 分，共 11 分)(C ) 1.不含任何结点的空树(A) 是一棵树 ;(B) 是一棵二义树;义树(C) 是一棵树也是一棵二义树(D)既不是树也不是二答：以前的标答是B,因为那时树的定义是nNI(C ) 2.二叉树是非线性数据结构，所以(A) 它不能用顺序存储结构存储； 储结构存储；(B) 它不能用链式存(C)顺序存储结构和链式存储结构都能存储;(D) 顺序存储结构和链式存储结构都不能使用(C ) 3.K01年计算机研题?具有n(n>0)个结点的完全二叉树

8、的深度为。(A) Iog2(n) ( B) Iog2(n) (C) Iog2(n) +1(D) Iog2(n)+I注 1： x 表示不小于 x 的最小整数; x 表示不大于 x 的最大整数，它们与 含 义不同！注2：选(A)是错误的。例如当n为2的整数幕时就会少算一层。似乎Iog2(n) +1 是对的？(A )4.把一棵树转换为二义树后，这棵二叉树的形态 是。(A)唯一的(B)有多种(C)有多种，但根结点都没有左孩子(D)有多种，但根结点都没有右孩子最确切的解答，把相应编号写在答卷的对应栏内。树是结点的有限集合，它A根结点，记为T。其余的结点分成为m mO个B的集合Tl, T2,，Tm,每个集

9、合乂都是树，此时结点 T称为Ti的父结 点，Ti 称为T的子结点iWiWm 。一个结点的子结点个数为该结点的C。供选择的答案个A :有0个或1个有1个或1个以上有0个或多个有且只有1B:互不相交允许相交允许叶结点相交允许树枝结点相交C:权维数次数或度序答案：ABC=1, 1, 36.【95程P13】从供选择的答案中，选出应填入下面表达？内的最确切的解答，把相应编号写在答卷的对应栏内。二叉树A。在完全的二义树中，假设一个结点没有B，那么它必定是叶结点。每棵树都能惟一地转换成与它对应的二义树。由树转换成的二义树里，一个结点的左子女是'在原树里对应结点的 C ,而'的右子女是它在原树

10、里对应 结点的D。供选择的答案A :是特殊的树 不是树的特殊形式是两棵树的总称 有是只 有二个根结点的树形结构B: 左子结点 右子结点 左子结点或者没有右子结点兄弟C? D: 最左子结点最右子结点最邻近的右兄弟最邻近的左兄弟最左的兄弟 最右的兄弟答案：A 二B 二C 二D答案: ABCDE = 2, 1, 1, 3四、简答题每题 4 分，共 20 分1.【严题集6. 2】一棵度为2的树与一棵二义树有何区别？答：度为 2的树从形式上看与二义树很相似， 但它的子树是无序的， 而二义 树 是有序的。即，在一般树中假设某结点只有一个孩子，就无需区分其左右次序，而 在 二叉树中即使是一个孩子也有左右之分

11、。C 的结点类型定义如下：struct nodechar data;struct node *lchild, rchild;；c 算法如下：void traversal(struct node *root)if (root)printf( c -,>rdoaotd);traversal(root->lchild);printf (c , roo->t datd);traversal(root->rch 订 d);2. KOI年计算机研题II设如以下图所示的二义树B的存储结构为二叉链表，root为根 指针,结点结构为 :( lchild, data, rchild) 。其中 lchild, rchild 分别为指 向左右孩子的指 针，d