首页 › 题库 › 信息学奥赛 › 1.1 树与二叉树

信息学奥赛-提高级 题库

共 49 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 树与二叉树 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?

A
7
B
8
C
9
D
10
答案与解析
正确答案:B

满线段树结构为:  

[0,15]分为[0,7]和[8,15];  

[0,7]分为[0,3]和[4,7];  

[8,15]分为[8,11]和[12,15];  

[0,3]分为[0,1]和[2,3]。  

查询[3,11]时,需访问[0,15]、[0,7]、[8,15]、[0,3]、[4,7]、[8,11]、[2,3]、[3,3],共8个节点。 

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

将字符串“cat”“car”“cart”“case”“dog”“do”插入一个空的Trie树(前缀树)中,构建完成的Trie树(包括根节点)共有多少个结点?

A
8
B
9
C
10
D
11
答案与解析
正确答案:D

按Trie树构建规则,依次插入各字符串,统计节点总数。

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

如果一棵二叉搜索树的后序遍历序列是2,5,4,8,12,10,6,那么该树的前序遍历是什么?

A
6,4,2,5,10,8,12
B
6,4,5,2,10,12,8
C
2,4,5,6,8,10,12
D
12,8,10,5,2,4,6
答案与解析
正确答案:A

二叉搜索树性质为“树根左子树点权≤树根点权,右子树点权≥树根点权,且左右子树也为二叉搜索树”。  

后序遍历最后一个数为根节点6;  

左子树节点为2、5、4,根为4(左子树2,右子树5);  

右子树节点为8、12、10,根为10(左子树8,右子树12);  

前序遍历为6,4,2,5,10,8,12。

题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

在一棵以结点1为根的树中,结点12和结点18的最近公共祖先(LCA)是结点4,下列哪个结点的LCA组合是不可能出现的?

A
LCA(12,4)=4
B
LCA(18,4)=4
C
LCA(12,18,4)=4
D
LCA(12,1)=4
答案与解析
正确答案:D

因树以1为根,1是所有节点的祖先,LCA(12,1)应为1,而非4。

题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

假设有一颗h层的完全二叉树,该树最多包含( )个节点?

A
2h−1
B
2(h+1)−1
C
2h
D
2h+1
答案与解析
正确答案:A

第一层1,第二层2,第h层2h-1,加起来2h-1

题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?(  )

A
4个结点的树
B
6个结点的树
C
7个结点的树
D
8个结点的树
答案与解析
正确答案:C

考虑一条链的情况下,如果树的结点是偶数个数,那么中间的两个点都可以是重心,所以必须是奇数个结点的树。

题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。

A
95
B
96
C
97
D
98
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

令根结点的高度为 1,则一棵含有 2021 个结点的二叉树的高度至少为( )。

A
10
B
11
C
12
D
2021
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
9 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

前序遍历和中序遍历相同的二叉树为且仅为( )。

A
只有 1 个点的二叉树
B
根结点没有左子树的二叉树
C
非叶子结点只有左子树的二叉树
D
非叶子结点只有右子树的二叉树
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
10 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

设根节点深度为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)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

设G是有n个结点、m条边(n≤m)的连通图,必须删去G的( )条边,才能使得G变成一棵树。

A
m-n+1
B
m-n
C
m+n+1
D
n-m+1
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
12 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

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

A
6
B
7
C
12
D

14

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
13 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

前序遍历序列与后序遍历序列相同的二叉树为( )。

A
非叶子结点只有左子树的二叉树
B
只有根结点的二叉树
C
根结点无右子树的二叉树
D
非叶子结点只有右子树的二叉树
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
14 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

如果根的高度为1,具有61个结点的完全二叉树的高度为( )。(2015年提高组)

A
5
B
6
C
7
D
8
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了( )思想的算法。

A
贪心
B
分治
C
递推
D
回溯
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
16 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

设G是有6个结点的完全图,要得到一棵生成树,需要从G中删去( )条边。

A
6
B
9
C
10
D
15
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
17 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

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

A
1006
B
1007
C
1023
D
1024
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
18 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

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

A
先序遍历
B
中序遍历
C
后序遍历
D
宽度优先遍历
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
19 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

右图是一棵二叉树,它的先序遍历是( )。

A
ABDEFC
B

DBEFAC

C

DFEBCA

D

ABCDEF

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
20 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第 100 号结点的父结点是第( )号。

A
95
B
96
C
97
D
98
答案与解析
正确答案:C
这道题暂未补解析。
题目详情