第8节树

您的姓名：



一、单项选择题（共26题，每题5分，共计130分;每题有且仅有一个正确选项）

1.已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。

A.4

B.5

C.6

D.7

2.已知一棵二叉树有2013个节点，则其中至多有（）个节点有2个子节点。

A.1006

B.1007

C.1023

D.1024

3.如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。

A. 10

B. 11

C. 12

D. 13

4.如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。

A.2^(n) - 1

B.2^(n)

C.2^(n) + 1

D.2^(n+1)

5.一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为（）:

A.2n + 1

B.2n-1

C.n-1

D.n+1

6.最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码（）。

A.(00，01，10，11)

B.(0，1，00，11)

C.(0，10，110，111)

D.(1，01，000，001)

7.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、200。那么，“也”字的编码长度是（）。

A. 1

B. 2

C. 3

D. 4

8.一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i ，则其左孩子位于下标2i 处、右孩子位于下标(2i+1)处)，则图中所有结点的最大下标为（）。

A. 6

B. 10

C. 12

D. 15

9.一棵二叉树如右图所示，若采用二叉树链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（）。

A. 6

B. 7

C. 12

D. 14

10.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。

A.2k

B.2k+1

C.k/2下取整

D.(k+1)/2下取整

11.完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1

B. N

C. 2*N

D. 2N-1

12.一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数目为（）:

A) nk + 1

B) nk-1

C) (k+1)n-1

D. (k-1)n+1

13.如果根的高度为1，具有61个结点的完全二叉树的高度为（）。

A.5

B.6

C.7

D.8

14.一棵具有5层的满二叉树中结点数为（）。

A.31

B.32

C.33

D.16

15.根节点深度为 0，一棵深度为 h 的满 k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。

A.(k^(h+1)-1)/(k-1)

B.k^(h-1)

C.k^h

D.k^(h-1)/(k-1)

16.二叉树的（）第一个访问的节点是根节点。

A.先序遍历

B.中序遍历

C.后序遍历

D.以上都是

17.二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（）是一个有序序列。

A.先序遍历

B.中序遍历

C.后序遍历

D.宽度优先遍历

18.前序遍历序列与中序遍历序列相同的二叉树为（）

A.根结点无左子树的二叉树

B.根结点无右子树的二叉树

C.只有根结点的二叉树或非叶子结点只有左子树的二叉树

D.只有根结点的二叉树或非叶子结点只有右子树的二叉树

19.前序遍历序列与后序遍历序列相同的二叉树为（）。

A.非叶子结点只有左子树的二叉树

B.只有根结点的二叉树

C.根结点无右子树的二叉树

D.非叶子结点只有右子树的二叉树

20.右图是一棵二叉树，它的先序遍历是（）。

A. ABDEFC

B. DBEFAC

C. DFEBCA

D. ABCDEF

21.如果一棵二叉树的中序遍历是 BAC ，那么它的先序遍历不可能是（）。

A.ABC

B.CBA

C.ACB

D.BAC

22.表达式a*(b+c)-d 的后缀表达形式为（）。

A. abcd*+-

B. abc+*d-

C. abc*+d-

D. -+*abcd

23.表达式a * d - b * c 的前缀形式是（）。

A. a d * b c * -

B. - * a d * b c

C. a * d - b * c

D. - * * a d b c

24.前缀表达式 + 3 * 2 + 5 12 的值是（）。

A. 23

B. 25

C. 37

D. 65

25.二叉树T，已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号，以下同)，中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。

A. 4 2 5 7 6 3 1

B. 4 2 7 5 6 3 1

C. 7 4 2 5 6 3 1

D. 4 2 7 6 5 3 1

26.一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（）。

A. 2

B. 3

C. 4

D. 5

二、不定项选择题（共7题，每题5分，共计35分;每题有一个或多个正确选项，多选或少选均不得分）

1.设T是一棵有n个顶点的树，下列说法正确的是（）。【多选题】

A. T是连通的、无环的

B. T是连通的，有n-1条边

C. T是无环的，有n-1条边

D. 以上都不对

2.下列说法中，是树的性质的有（）。【多选题】

A. 无环

B. 任意两个结点之间有且只有一条简单路径

C. 有且只有一个简单环

D. 边的数目恰是顶点数目减1

3.下列有关树的叙述中，叙述正确的有（）。【多选题】

A.在含有n个结点的树中，边数只能是(n-1)条

B.在哈夫曼树中，叶结点的个数比非叶结点个数多1

C.完全二叉树一定是满二叉树

D.在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先

4.二叉树T，已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号，以下同)，后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。【多选题】

A. 4 2 1 7 5 3 6

B. 2 4 1 7 5 3 6

C. 4 2 1 7 5 6 3

D. 2 4 1 5 7 3 6

5.．如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（）。【多选题】

A. 10

B. 11

C. 12

D. 2011

6.一棵二叉树一共有19个节点，其叶子节点可能有（）个。【多选题】

A.1

B.9

C.10

D.11

7.2-3 树是一种特殊的树，它满足两个条件:(1)每个内部结点有两个或三个子结点;(2)所有的叶结点到根的路径长度相同。如果一棵2-3 树有10 个叶结点，那么它可能有（）个非叶结点。【多选题】

A. 5

B. 6

C. 7

D. 8

第8节 树

第8节树