第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节树