树 - Problem Detail - lizikid

ID: 19

Type: Objective

Difficulty: 9

Uploaded By:

Tags>

初赛选择题

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

4
5
6
7

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

1006
1007
1023
1024

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

10
11
12
13

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

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

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

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

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

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

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

1
2
3
4

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

{{ select(8) }}

6
10
12
15

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

{{ select(9) }}

6
7
12
14

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

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

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

N-1
N
2*N
2N-1

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

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

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

5
6
7
8

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

31
32
33
16

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

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

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

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

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

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

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

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

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

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

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

{{ select(20) }}

ABDEFC
DBEFAC
DFEBCA
ABCDEF

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

ABC
CBA
ACB
BAC

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

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

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

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

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

23
25
37
65

二叉树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

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

2
3
4
5