一、单项选择题（每题有且仅有一个正确选项）

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

• 4
• 5
• 6
• 7

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

• 1006
• 1007
• 1023
• 1024

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

• 10
• 11
• 12
• 13

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

• $2^n - 1$
• $2^n$
• $2^n + 1$
• $2^{n+1}$

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

• 2n + 1
• 2n-1
• n-1
• n+1

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

• (00，01，10，11)
• (0，1，00，11)
• (0，10，110，111)
• (1，01，000，001)

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

• 1
• 2
• 3
• 4

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

• 6
• 10
• 12
• 15

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

• 6
• 7
• 12
• 14

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

• 2k
• 2k+1
• k/2下取整
• (k+1)/2下取整

11.完全二叉树共有$2N-1$个结点，则它的叶节点数是（）。 {{ select(11) }}

• N-1
• N
• 2N
• 2N-1

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

• nk + 1
• nk-1
• (k+1)n-1
• (k-1)n+1

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

• 5
• 6
• 7
• 8

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

• 31
• 32
• 33
• 16

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

• $(k^{h+1}-1)/(k-1)$
• $k^{h-1}$
• $k^h$
• $k^{h-1}/(k-1)$

16.二叉树的（）第一个访问的节点是根节点。{{ select(16) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 以上都是

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

• 先序遍历
• 中序遍历
• 后序遍历
• 宽度优先遍历

18.前序遍历序列与中序遍历序列相同的二叉树为（）{{ select(18) }}

• 根结点无左子树的二叉树
• 根结点无右子树的二叉树
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

19.前序遍历序列与后序遍历序列相同的二叉树为（）。{{ select(19) }}

• 非叶子结点只有左子树的二叉树
• 只有根结点的二叉树
• 根结点无右子树的二叉树
• 非叶子结点只有右子树的二叉树

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

• ABDEFC
• DBEFAC
• DFEBCA
• ABCDEF

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

• ABC
• CBA
• ACB
• BAC

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

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

23.表达式a * d - b * c 的前缀形式是（）。{{ select(23) }}

• a d * b c * -
• - * a d * b c
• a * d - b * c
• - * * a d b c

24.前缀表达式 + 3 * 2 + 5 12 的值是（）。{{ select(24) }}

• 23
• 25
• 37
• 65

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

• 4 2 5 7 6 3 1
• 4 2 7 5 6 3 1
• 7 4 2 5 6 3 1
• 4 2 7 6 5 3 1

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

• 2
• 3
• 4
• 5

二、不定项选择题（每题有一个或多个正确选项，多选或少选均不得分）

27.设T是一棵有n个顶点的树，下列说法正确的是（）。 {{ multiselect(27) }}

• T是连通的、无环的
• T是连通的，有n-1条边
• T是无环的，有n-1条边
• 以上都不对

28.下列说法中，是树的性质的有（）。 {{ multiselect(28) }}

• 无环
• 任意两个结点之间有且只有一条简单路径
• 有且只有一个简单环
• 边的数目恰是顶点数目减1

29.下列有关树的叙述中，叙述正确的有（）。 {{ multiselect(29) }}

• 在含有n个结点的树中，边数只能是(n-1)条
• 在哈夫曼树中，叶结点的个数比非叶结点个数多1
• 完全二叉树一定是满二叉树
• 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先

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

• 4 2 1 7 5 3 6
• 2 4 1 7 5 3 6
• 4 2 1 7 5 6 3
• 2 4 1 5 7 3 6

31．如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（）。 {{ multiselect(31) }}

• 10
• 11
• 12
• 2011

31.一棵二叉树一共有19个节点，其叶子节点可能有（）个。 {{ multiselect(32) }}

• 1
• 9
• 10
• 11

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

• 5
• 6
• 7
• 8