复习—树の习题_3.下列关于二叉链表的说法中,错误的是( )。 a.任何-株二叉树都可以用二叉链表存储

摘选了部分客观题，明天考试，砸瓦鲁多！

1.讨论树、森林和二叉树的关系，目的是为了（ ）

答案是：借助二叉树上的运算方法去实现对树的一些运算
记住就行…

---

2.度为二的树就是二叉树。（ X ）

二叉树的两个特点：
1.度数不大于二
2.左右子树不能交换

---

3.完全二叉树一定存在度为1的结点。（ X ）

举一个满二叉树的例子…

---

4.二叉树共有4种基本形态。（ X ）

5种形态：空树、只有根结点、根结点+左子树、根结点+右子树、根结点+左右子树

---

5.霍夫曼树的结点个数不能是偶数。（ √ ）

因为Huffman 树里面没有度数为1的结点
所以总结点数=2*n₂+1，一定是奇数咯

---

6.二叉树只能用二叉链表表示。（ X ）

可以顺序存储，也可以使用二叉链表、三叉链表

---

7.下述编码中哪一个不是前缀码(B)
A.(00,01,10,11)
B.(0,1,00,11)
C.(0,10,110,111)
D.(1,01,000,001)

前缀码的定义是：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。

---

8.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。

可以画出该二叉树
----C
—/
–E
-/ -\
D—B
-------\
--------A

前序即为cedba

---

9.由3 个结点可以构造出多少种不同的二叉树？（ ）

答案：5种

b_n=[1/(n+1)]X(2n)!/n!^2
所以b₃=4X5÷4=5

---

10.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

画出二叉树
借了张图…

所以后序遍历结果为：CBEFDA

---

11.引入二叉线索树的目的是（A）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一

基本定义咯记住…

---

12.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）
A.都不相同
B.完全相同
C.先序和中序相同，而与后序不同
D.中序和后序相同，而与先序不同。

因为不管是先、中、后序遍历，改变的只有每个根结点和其子树结点间顺序的关系
单单对于叶子结点来说，每个叶子结点的顺序是不会变的。

---

13.一棵二叉树高度为h,所有结点的度或为0或为2，则这棵二叉树最少有(B)结点
A.2h
B.2h-1
C.2h+1
D.h+1

最少的情况就是除了根结点外每层只有两个结点，来保证上一层只有一个结点度数为2。
所以共有2h-1个结点

---

14.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：()
A.0
B.1
C.2
D.不确定

另外补充：前序和后续线索化都是1，中序是2。

---

15.利用二叉链表存储树，则根结点的右指针是（ C ）。
A.指向最左孩子
B.指向最右孩子
C.空
D.非空

注意题目，是用二叉链表存储树，也就是左孩子-右兄弟表示法
根结点没有兄弟，所以为空。

---

16.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A.250
B.501
C.254
D.512

可知道最后一个结点编号为1001，其父结点为500.
所以整个树只有500个内部结点（分支结点）其余都为叶子结点

所以叶子结点数=1001-500=501

---

17.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）
A.9
B.11
C.15
D.不确定

n₀=n₂+1 该公式对于任何非空二叉树都适用。

---

18.给定一棵树，可以找到唯一的一棵二叉树与之对应。( √ )

左孩子右兄弟得出的是唯一的…

---

19.用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。( X )

因为需要指针指的只有n-1个元素，所以空指针为n+1个

---

20.二叉树中序线索化后，不存在空指针域。( X )

前序遍历，后序遍历有1个
中序遍历有两个，第一个结点无前驱，最后一个结点无后继。

---

21.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( X )

总是以层次遍历的顺序遍历结点。

---

22.二叉树的遍历只是为了在应用中找到一种线性次序。( √ )

所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。
由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

---

23.对于有N个结点的二叉树，其高度为log2n。( X )

应该为log₂n(下取整) +1

---

24.设有13个值组成赫夫曼树，则该赫夫曼树共有 25 个结点。

Huffman tree 只有度数为0和2的结点
且这13个值都应该是叶子结点（度为0）所以n₂=n₀-1=12

共有25个结点

---