ch6习题及答案
习题6解答
判断题：
1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。( ╳ )
2.二叉树就是结点度为2的树。( ╳ )( (哈工大2000年研究生试题)
3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。( ╳ ) (陕西省1998年自考试题)
4.当k≥1时，高度为k的二叉树至多有21 k个结点。( ╳ )
5.完全二叉树的某结点若无左孩子，则它必是叶结点。 (√)(中科院软件所1997年研究生试题)
6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。( ╳ )
7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。( ╳ )
8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。(√)
(哈工大2000年研究生试题)
9.中序线索二叉树的优点之一是便于在中序下查前驱结点和后继结点。(√)
10.将一棵树转换成二叉树后，根结点没有左子树，( ╳ )
(北邮1999年研究生试题。)
11.由树转换成二叉树，其根结点的右子树总是空的。(√)
12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。( ╳ )
13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( ╳ )
14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。( ╳ )
15.霍夫曼树一定是满二叉树。( ╳ )
16.树的度是树内各结点的度之和。( ╳ )
17.由二叉树的结点构成的集合可以是空集合。(√)
18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( ╳ )
选择题：
19.树最适合用来表示( C )。
A．有序数据元素 B. 无序数据元素
C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( D )。
A. 4
B. 5
C. 1
D. 3
21.下列有关二叉树的说法正确的是( B )。
(南京理工大学2000年研究生试题。)
A．二叉树的度为2 B. 一棵二叉树度可以小于2
C．二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2 22.以下说法错误的是( B )。
A．二叉树可以是空集 B. 二叉树的任一结点都可以有两棵子树
C．二叉树与树具有相同的树形结构 D. 二叉树中任一结点的两棵子树有次序之分
23.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( B )个。
A．15 B. 16 C. 17 D.47
24. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组]中，结点R[i]若有左子女，则左子女是结点( B )。
A．R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] (参见严蔚敏《(c语言版)数据结构》P.124 ~ 125，二叉树的性质，性质5)
25.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是( B )。
A．a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙26.以下说法正确的是( C )。
A．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。
B．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。
C．在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(提示：后继结点应为遍历右子树时访问的第一个结点，该后继结点或为叶子结点，则其无子女；或为仅有右子树，则其也是最多只能有一个子女；若有两个子女，则它本身已不是后继。) D．在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点。
27.以下说法错误的是( B )。
A．存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。
B. 二叉树是树的特殊情形。
C. 由树转换成二叉树，其根结点的右子树总是空的。
D. 在二叉树只有一棵子树的情况与也要明确指出该子树是左子树还是右子树。
28.将下图的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向( C )。
A．A，，A
A
先序中序后序遍历二叉树B D
C X E
Y
29.在N个结点的线索二叉树中，线索的数目为( C )。
A．N-1 B. N C. N+1 D. 2N
(参见严蔚敏《(c语言版)数据结构》P.126 & P.132)
30.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有( D )个结点。
(全国2001年自考题)
A．13 B. 12 C. 26 D. 25
(参见严蔚敏《(c语言版)数据结构》P.147)
31.下面几个符号串编码集合中，不是前缀编码的是( B )。
A．{0，10，110，1111} B. {11，10，001，101，0001}
C．{00，010，0110，1000} D. {b，c，aa，ac，aba，abb，abc}
32.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( D )。
A. 23
B. 37
C. 46
D. 44
33.树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论( A )是正确的。
A．树的先根遍历序列与其对应的二叉树先序遍历序列相同。
B. 树的后序遍历序列与其对应的二叉树后序遍历序列相同。
C. 树的先根遍历序列与其对应的二叉树中序遍历序列相同。
D. 以上都不对
34.在一棵具有n个结点的二叉树第i层上，最多具有( C )个结点。
A．2i B. 21+i C. 21-i D. 2n
(参见严蔚敏《(c语言版)数据结构》P.123)
35.给定一个整数集合{3，5，6，9，12}，下列二叉树哪个是该整数集合对应的霍夫曼（Huffman）树。（ C ）
填空题：
36.具有n个结点的二叉树，采用二叉链表存储，共有 n+1 个空链域。(重庆大学2000年研究生试题)
37.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为 2n 个，其中 n-1 个用于链接孩子结点， n+1 个空闲着。
38.二叉树的线索化实质是将二叉链表中的___空指针____改为___线索___________。
(陕西省1998年自考题)
39.一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为 n-(n-1)/k 。
40.在下图所示的树中，结点H的祖先为 A、D、G 。
41.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是 借用二叉树的有关算法实现树的有关操作 。
42.对于一个具有n 个结点的二叉树，当它为一棵 完全 二叉树时具有最小高度，即为 ⎣⎦1log 2+n ，当它为一棵单支树具有 最大 高度，即为 n 。(注：树
的深度有时称为高度，不同的体系所用的名词可能会有差别。)
43.设只包含根结点的二叉树高度为0，则高度为k 的二叉树最大结点数为 2k+1-1 ，最小结点数为 k+1 。(提示：请注意，这里关于树的高度的定义与通常的高度定义有不同！)
44. 8层完全二叉树至少有 128 个结点，拥有100个结点的完全二叉树的最大层数为 7 。
(西南交大2000年研究生试题。)
45.二叉树通常有 顺序 存储结构和 链式 存储结构。
46.二叉树有不同的链式存储结构，其中最常用的是 二叉链表 与 三叉链表 。
47.一棵左右子树均不空的二叉树在先序线索化后，其空指针域有 1 个。
48.线索二叉树的左线索指向其 前驱 ，右线索指向其 后继 。
(哈工大2000年研究生试题)
49.用树的孩子兄弟表示法存储，可以将一棵树转换成 二叉树 。
(重庆大学2000年研究生试题)
50.遍历一棵二叉树包括访问 根结点 、遍历 左子树 和遍历 右子树 三个方面。
51.已知树的广义表形式为A{B[E ，F]，C ，D[G （H ，I ）]}，则该树的度为__3____，从根开始的前序遍历所得序列为_A 、B 、E 、F 、C 、D 、G 、H 、I____.
52.森林定义为 m(m>=0)棵互不相交的树 的集合。
简答题
53.分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下A B D E F G C H I
发表评论