数据结构3: 树

ID: 9828

客观题

尝试: 1

已通过: 0

难度: 10

上传者:

bitworld

标签>

CSP

初赛

1.单选题 [GESP202406【6级】] 完全二叉树可以用数组存储数据。 {{ select(1) }}

正确
错误

2.单选题 [GESP202312【6级】] 下面有关树的存储，错误的是（）. {{ select(2) }}

完全二叉树可以用 list 存储
一般二叉树都可以用 list 存储，空子树位置可以用 None 表示
满二叉树可以用 list 存储
树数据结构，都可以用 list 存储

3.单选题 [NOIP提高组2016] 一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（）。

4.单选题 [CSP-J2019] 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i 处、右孩子位于下标2i+1 处），则该数组的最大下标至少为（）。

5.单选题 [GESP202312【6级】] 构造二叉树 [1,2,3,null,4] （）。 {{ select(5) }}

1(2()(4))(3)
1(2(3)())(4)
(1,2(3),(4))
(1,(2)(3),(4))

6.单选题 [GESP202312【6级】] 有关下面C++代码的说法，错误的是( )。

上列C++代码适用于构造各种二叉树
代码 struct BiNode 用于构造二叉树的节点
代码 BiTree(){root=Creat();} 用于构造二叉树
析构函数不可以省略

7.单选题 [NOIP普及组2008] 设 T 是一棵有 n 个顶点的树，下列说法不正确的是（）。 {{ select(7) }}

T 有 n 条边
T 是连通的
T 是无环的
T 有 n-1 条边

8.不定项选择题 [NOIP提高组2008] 设 T 是一棵有 n 个顶点的树，下列说法正确的是（）。 {{ multiselect(8) }}

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

9.不定项选择题 [NOIP提高组2018] 下列说法中，是树的性质的有（）。 {{ multiselect(9) }}

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

10.单选题 [GESP202406【7级】] 一颗 N 层的二叉树，至少有2N-1个节点。 {{ select(10) }}

正确
错误

11.单选题 [GESP样题【6级】] 任意二叉树都至少有一个结点的度是 2。 {{ select(11) }}

正确
错误

12.单选题 [GESP202403【6级】] 完全二叉树的任意一层都可以不满。 {{ select(12) }}

正确
错误

13.单选题 [GESP202312【7级】] 假设一棵完全二叉树共有N个节点，则树的深度为logN+1。 {{ select(13) }}

正确
错误

14.单选题 [NOIP普及组2006] 高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为（）。 {{ select(14) }}

15.单选题 [NOIP提高组2006] 高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为（）。 {{ select(15) }}

10
11
12
13
210 – 1

16.不定项选择题 [NOIP提高组2011/NOIP普及组2011] 如果根节点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度可能是（）. {{ multiselect(16) }}

10
11
12
2011

17.单选题 [NOIP普及组2015/NOIP提高组2015/CSP-J2020] 如果根的高度为1，具有61个结点的完全二叉树的高度为（）。 {{ select(17) }}

18.单选题 [CSP-S2021] 令根结点的高度为1，则一棵含有2021个结点的二叉树的高度至少为（）。 {{ select(18) }}

10
11
12
2021

19.单选题 [GESP202403【7级】] 一棵有N个节点的完全二叉树，则树的深度为⌊log(N)⌋+1 {{ select(19) }}

正确
错误

20.单选题 [CSP-J2023/GESP202312【7级】] 根节点的高度为1，一棵拥有 2023个节点的三叉树高度至少为（）。 {{ select(20) }}

21.单选题 [GESP样题【6级】] 在具有2N个结点的完全二叉树中，叶子结点个数为（）。 {{ select(21) }}

N/2
N−1
N
N+1

22.单选题 [NOIP普及组2005] 完全二叉树的结点个数为 11，则它的叶结点个数为（）。 {{ select(22) }}

23.单选题 [NOIP提高组2005] 完全二叉树的结点个数为 4 * N + 3，则它的叶结点个数为（）。 {{ select(23) }}

2 * N
2 * N - 1
2 * N + 1
2 * N - 2
2 * N + 2

24.单选题 [NOIP普及组2008/NOIP提高组2008] 完全二叉树共有 2*N-1 个结点，则它的叶节点数是（）。 {{ select(24) }}

N-1
N
2*N
2N-1

25.不定项选择题 [NOIP提高组2012] 一棵二叉树一共有19个节点，其叶子节点可能有（）个。 {{ multiselect(25) }}

26.填空题 [NOIP普及组2015] 一棵结点数为 2015 的二叉树最多有（）个叶子结点。 {{ input(26) }}

27.填空题 [NOIP普及组2016] 约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（①）个叶子结点；一棵结点数为2016 的二叉树最小的高度值是（②）。 {{ input(27) }}

28.单选题 [NOIP普及组2009] 一个包含 n 个分支结点（非叶结点)的非空二叉树，它的叶结点数目最多为： {{ select(28) }}

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

29.单选题 [NOIP提高组2009] 一个包含 n 个分支结点（非叶结点)的非空满 k 叉树，k>=1，它的叶结点数目为： {{ select(29) }}

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

30.单选题 [GESP202406【8级】/NOIP普及组2013] 已知一棵二叉树有10个节点，则其中最多有（）个节点有2个子节点。 {{ select(30) }}

31.单选题 [NOIP提高组2013] 已知一棵二叉树有 2013 个节点，则其中至多有（）个节点有 2 个子节点。 {{ select(31) }}

1006
1007
1023
1024

32.不定项选择题 [NOIP提高组2018] 2-3 树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。如果一棵2-3 树有10 个叶结点，那么它可能有（）个非叶结点。 {{ multiselect(32) }}

33.单选题 [NOIP普及组2004/NOIP提高组2004] 满二叉树的叶结点个数为 N，则它的结点总数为（）。 {{ select(33) }}

N
2 * N
2 * N – 1
2 * N + 1
2N – 1

34.单选题 [GESP202403【6级】] 一个有 124 个叶子节点的完全二叉树，最多有（）个结点。 {{ select(34) }}

35.单选题 [GESP202406【6级】/NOIP普及组2014] 一棵5层的满二叉树中节点数为（）。 {{ select(35) }}

36.单选题 [GESP样题【7级】] 深度为4的完全二叉树，结点总数最少有多少个？（） {{ select(36) }}

37.单选题 [NOIP普及组2010] 如果树根算第 1 层，那么一棵 n 层的二叉树最多有（）个结点 {{ select(37) }}

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

38.单选题 [NOIP普及组2018/NOIP提高组2018] 根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。 {{ select(38) }}

(k h+1 - 1) / (k - 1)
k h-1
k h
k h-1 / (k - 1)

39.单选题 [CSP-J2022] 一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。 {{ select(39) }}

8、18
10、18
8、19
10、19

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

2k
2k+1
⌊k/2⌋
⌊(k+1)/2⌋

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

42.单选题 [CSP-J2021] 如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为 5 的完全二叉树有（）种不同的形态？ {{ select(42) }}

43.填空题 [NOIP提高组2015] 结点数为 5 的不同形态的二叉树一共有_____种。（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。） {{ input(43) }}

44.填空题 [NOIP提高组2012] 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有____个不同的独立集。

45.单选题 [GESP202406【6级】/NOIP普及组2013] 二叉树的（）第一个访问的节点是根节点。 {{ select(45) }}

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

46.单选题 [NOIP提高组2013] 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（）是一个有序序列。 {{ select(46) }}

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

47.单选题 [GESP202312【8级】] 对有 n 个元素的二叉排序树进行中序遍历，其时间复杂度是（）。 {{ select(47) }}

O(1)
O(log(n))
O(n)
O(n2)

48.单选题 [GESP202406【7级】] 关于图的深度优先搜索和广度优先搜索，下列说法错误的是（）。 {{ select(48) }}

二叉树也是⼀种图。
二叉树的前序遍历和后序遍历都是深度优先搜索的一种。
深度优先搜索可以从任意根节点开始。
二叉树的后序遍历也是广度优先搜索的一种。

49.单选题 [GESP样题【6级】] 深度优先遍历算法的时间复杂度为O(NlogN)，其中N为树的节点数。 {{ select(49) }}

正确
错误

50.单选题 [NOIP提高组2011] 下图是一棵二叉树，它的先序遍历是（）。 {{ select(50) }}

ABDEFC
DBEFAC
DFEBCA
ABCDEF

51.单选题 [GESP202406【7级】] 对于如下图的二叉树，说法正确的是（）。

先序遍历是 132 。
中序遍历是 123 。
后序遍历是 312 。
先序遍历和后序遍历正好是相反的。

52.单选题 [GESP202406【7级】] 对于如下二叉树，下面访问顺序说法错误的是（）。

HDEBFIGCA不是它的后序遍历序列
ABCDEFGHI是它的广度优先遍历序列
ABDHECFGI是它的深度优先遍历序列
ABDHECFGI是它的先序遍历序列

53.单选题 [NOIP普及组2015] 前序遍历序列与中序遍历序列相同的二叉树为（）。 {{ select(53) }}

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

54.单选题 [NOIP提高组2015] 前序遍历序列与后序遍历序列相同的二叉树为（）。 {{ select(54) }}

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

55.单选题 [CSP-S2021] 前序遍历和中序遍历相同的二叉树为且仅为（）。 {{ select(55) }}

只有1个点的二叉树
根结点没有左子树的二叉树
非叶子结点只有左子树的二叉树
非叶子结点只有右子树的二叉树

56.单选题 [NOIP提高组2004/NOIP普及组2004] 二叉树 T，已知其前序遍历序列为 1 2 4 3 5 7 6，中序遍历序列为 4 2 1 5 7 3 6，则其后序遍历序列为（）。 {{ select(56) }}

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

57.单选题 [NOIP普及组2007] 已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），中根遍历是 4 2 6 5 1 7 3，则该二叉树的后根遍历是（） {{ select(57) }}

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

58.单选题 [NOIP普及组2008] 二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是 2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。 {{ select(58) }}

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

59.单选题 [CSP-J2023] 给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么? {{ select(59) }}

EDBGFCA
EDGBFCA
DEBGFCA
DBEGFCA

60.单选题 [GESP202403【6级】] 若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（）。 {{ select(60) }}

D, E, B, F, C, A
E, D, B, F, C, A
D, E, B, C, F, A
E, D, B, C, F, A

61.不定项选择题 [NOIP提高组2006/NOIP普及组2006] 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（） {{ multiselect(61) }}

3 2 1 4 6 5
3 2 1 5 4 6
2 3 1 5 4 6
2 3 1 4 6 5

62.不定项选择题 [NOIP提高组2007] 已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是 4 6 5 2 7 3 1，则该二叉树的可能的中根遍历是（） {{ multiselect(62) }}

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

63.不定项选择题 [NOIP提高组2008] 二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是 4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。 {{ multiselect(63) }}

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

64.单选题 [CSP-J2019] 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（）。 {{ select(64) }}

ABCDEFGHIJ
ABDEGHJCFI
ABDEGJHCFI
ABDEGHJFIC

65.单选题 [NOIP普及组2012] 如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是( )。 {{ select(65) }}

66.单选题 [GESP202312【7级】] 某二叉树T的先序遍历序列为： {A B D F C E G H} ，中序遍历序列为： {B F D A G E H C} ，则下列说法中正确的是( )。 {{ select(66) }}

T的度为1
T的高为4
T有4个叶节点
以上说法都不对

67.单选题 [GESP202403【7级】] 已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正确的是( )。 {{ select(67) }}

该树是平衡二叉树。
该树的高为4。
该树有4个叶节点。
以上说法都不对。

68.单选题 [CSP-S2022] 一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（）号。 {{ select(68) }}

69.单选题 [NOIP普及组2005] 二叉树 T 的宽度优先遍历序列为 A B C D E F G H I，已知 A 是 C 的父结点，D 是 G 的父结点，F 是 I 的父结点，树中所有结点的最大深度为 3（根结点深度设为 0），可知 F的父结点是（）。 {{ select(69) }}

无法确定
B
C
D
E

70.不定项选择题 [NOIP提高组2005] 二叉树 T 的宽度优先遍历序列为 A B C D E F G H I，已知 A 是 C 的父结点，D 是 G 的父结点，F 是 I 的父结点，树中所有结点的最大深度为 3（根结点深度设为 0），可知 E的父结点可能是（）。 {{ multiselect(70) }}

71.单选题 [NOIP普及组2010/NOIP提高组2010] 一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（）。 {{ select(71) }}

80.单选题 [GESP202406【6级】] 阅读以下二叉树的广度优先搜索代码，在如下的树中搜索数值 3时，采用深度优先搜索一共比较的节点数为（）

81.单选题 [GESP202403【6级】] 哈夫曼树是一种二叉树。 {{ select(81) }}

正确
错误

82.单选题 [GESP202406【6级】] 哈夫曼编码本质上是一种贪心策略。 {{ select(82) }}

正确
错误

83.单选题 [GESP202403【6级】/GESP202309【6级】] 哈夫曼编码的主要应用领域是有损数据压缩。 {{ select(83) }}

正确
错误

84.单选题 [GESP202312【6级】] 哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。 {{ select(84) }}

正确
错误

85.单选题 [GESP样题【6级】] 哈夫曼编码树中，两个频率相同的字符一定具有相同的哈夫曼编码。 {{ select(85) }}

正确
错误

86.单选题 [GESP202403【6级】] 使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。 {{ select(86) }}

正确
错误

87.单选题 [NOIP提高组2015/CSP-J2021] 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（）思想的算法 {{ select(87) }}

贪心
分治
递推
回溯

88.单选题 [GESP202403【6级】] 在构建哈夫曼树时，每次应该选择（）合并。 {{ select(88) }}

最小权值的节点
最大权值的节点
随机节点
深度最深的节点

89.不定项选择题 [NOIP提高组2015] 下列有关树的叙述中，叙述正确的有（）。 {{ multiselect(89) }}

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

90.单选题 [GESP样题【6级】] 如下图所示的哈夫曼树，按照哈夫曼编码规则，假设图中字符 C 的编码为0，则 E 的编码为（）。

1111
1010
1101
1001

91.单选题 [GESP202309【6级】] 某内容仅会出现 ABCDEFG ，其对应的出现概率为0.40、0.30、0.15、0.05、0.04、0.03、0.03，如下图所示。按照哈夫曼编码规则，假设 B 的编码为 11 ，则 D 的编码为（）。

10010
10011
10111
10001

92.单选题 [GESP202406【6级】] 对"classmycls"使用哈夫曼（Huffman）编码，最少需要（）比特。 {{ select(92) }}

93.单选题 [CSP-J2023] 假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 5%,9%,12%,13%,16%,45%。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码? {{ select(93) }}

1111,1110,101,100,110,0
1010,1001,1000,011,010,00
000,001,010,011,10,11
1010,1011,110,111,00,01

94.单选题 [NOIP普及组2011/NOIP提高组2011] 现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字"之"、 "呼"、 "者"、 "也"组成，它们出现的次数分别为 700、600、300、200。那么， "也" 字的编码长度是（）。 {{ select(94) }}

95.单选题 [CSP-J2022] 假设字母表{a,b,c,d,e} 在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度（）位。 {{ select(95) }}

1
2
2或3
3

96.单选题 [GESP202312【6级】] 对 hello world 使用霍夫曼编码（Huffman Coding），最少bit（比特）为（）。 {{ select(96) }}

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

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

98.单选题 [NOIP普及组2009] 表达式 a*(b+c)-d 的后缀表达式是： {{ select(98) }}

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

99.单选题 [NOIP提高组2009] 表达式 a*(b+c)-d 的后缀表达式是： {{ select(99) }}

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

100.单选题 [NOIP提高组2016] 表达式 a*(b+c)-d 的后缀表达形式为（）。 {{ select(100) }}

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

101.单选题 [NOIP普及组2017/NOIP提高组2017] 表达式a * (b + c) * d的后缀形式是()。 {{ select(101) }}

abcd*+*
abc+d
a*bc+*d
b+cad

102.单选题 [CSP-S2020] 表达式 a*(b+c)-d的后缀表达形式为（）。 {{ select(102) }}

答案：abc∗+d−
答案：−+∗abcd
答案：abcd∗+−
答案：abc+∗d−

103.单选题 [CSP-J2021] 表达式a*(b+c)d的后缀表达式为( )，其中和+是运算符。 {{ select(103) }}

**a+bcd
abc+d
abc+d**
a+bcd

104.单选题 [CSP-J2023] 后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是 {{ select(104) }}

((6-(2+3))*(3+8/2))^2+3
6-2+3*3+8/2^2+3
(6-(2+3))*((3+8/2)^2)+3
6-((2+3)*(3+8/2))^2+3

105.单选题 [CSP-J2022] 对表达式 a+(b-c)d 的前缀表达式为（），其中 +、-、 是运算符。 {{ select(105) }}

*+a-bcd
+a*-bcd
abc-d*+
abc-+d

106.单选题 [NOIP提高组2018] 表达式a * d - b * c 的前缀形式是（）。 {{ select(106) }}

答案：a d * b c * -
答案：- * a d * b c
答案：a * d - b * c
答案：- * * a d b c

107.单选题 [NOIP普及组2010/NOIP提高组2010] 前缀表达式" + 3 * 2 + 5 12 "的值是（） {{ select(107) }}

#CSPJKG73. 数据结构3: 树

还没有账户？

登录