树
第二章 程序设计基本知识
第8节 树
1.【NOIP2013】已知一棵二叉树有10个节点，则其中至多有( )个节点有2个子节点。
{{ select(1) }}
- 4
- 5
- 6
- 7
2.【NOIP2013】已知一棵二叉树有2013个节点，则其中至多有( )个节点有2个子节点。
{{ select(2) }}
- 1006
- 1007
- 1023
- 1024
3.【NOIP2011】如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是( ):
{{ select(3) }}
- 10
- 11
- 12
- 13
4.【NOIP2010】如果树根算是第一层，那么一颗n层的二叉树最多有()个结点。
{{ select(4) }}
5.【NOIP2009】一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为：
{{ select(5) }}
- 2n+1
- 2n-1
- n-1
- n+1
6.【NOIP2009】最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。
{{ select(6) }}
- (00,01,10,11)
- (0,1,00,11)
- (0,10,110,111)
- (1,01,000,001)
7.【NOIP2011】现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、200。那么,“也”字的编码长度是( )。
{{ select(7) }}
- 1
- 2
- 3
- 4
8.【NOIP2016】一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标 (2i+1)处),则图中所有结点的最大下标为( )。
{{ select(8) }}
- 6
- 10
- 12
- 15
9.【NOIP2016】一棵二叉树如右图所示，若采用二叉树链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为()。
{{ select(9) }}
- 6
- 7
- 12
- 14
10.【NOIP2010】完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的()号位置。
{{ select(10) }}
- 2k
- 2k+1
- k/2下取整
- (k+1)/2
11.【NOIP2008】完全二叉树共有2*N-1个结点，则它的叶节点数是()。
{{ select(11) }}
- N-1
- N
- 2*N
- 2N-1
12.【NOIP2009】一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1,它的叶结点数目为：
{{ select(12) }}
- nk+1
- nk-1
- (k+1)n-1
- (k-1)n+1
13.【NOIP2015】如果根的高度为1,具有61个结点的完全二叉树的高度为( )。
{{ select(13) }}
- 5
- 6
- 7
- 8
14.【NOIP2014】一棵具有5层的满二叉树中结点数为( )。
{{ select(14) }}
- 31
- 32
- 33
- 16
15.【NOIP2018】根节点深度为0,一棵深度为h的满k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有()个结点。
{{ select(15) }}
16.【NOIP2013】二叉树的( )第一个访问的节点是根节点。
{{ select(16) }}
- 先序遍历
- 中序遍历
- 后序遍历
- 以上都是
17.【NOIP2013】二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么,二叉查找树的( )是一个有序序列。
{{ select(17) }}
- 先序遍历
- 中序遍历
- 后序遍历
- 宽度优先遍历
18.前序遍历序列与中序遍历序列相同的二叉树为( )。
{{ select(18) }}
- 根结点无左子树的二叉树
- 根结点无右子树的二叉树
- 只有根结点的二叉树或非叶子结点只有左子树的二叉树
- 只有根结点的二叉树或非叶子结点只有右子树的二叉树
19.【NOIP2015】前序遍历序列与后序遍历序列相同的二叉树为( )。
{{ select(19) }}
- 非叶子结点只有左子树的二叉树
- 只有根结点的二叉树
- 根结点无右子树的二叉树
- 非叶子结点只有右子树的二叉树
20.【NOIP2011】右图是一棵二叉树，它的先序遍历是( )。
{{ select(20) }}
- ABDEFC
- DBEFAC
- DFEBC△
- ABCDEF
21.【NOIP2012】如果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是( )。
{{ select(21) }}
- ABC
- CBA
- ACB
- BAC
22.【NOIP2009】【NOIP2016】表达式a*(b+c)-d的后缀表达式是：
{{ select(22) }}
- abcd*+-
- abc+*d-
- abc*+d-
- -+*abcd
23.【NOIP2018】表达式a*d-b*c的前缀形式是()。
{{ select(23) }}
- a d*bc*-
- -*ad*bc
- a*d-b*c
- -**a d b c
24.【NOIP2010】前缀表达式“+3*2+512”的值是()。
{{ select(24) }}
- 23
- 25
- 37
- 65
25.【NOIP2008】二叉树T,已知其先根遍历是1243576(数字为结点的编号，以下同),中根遍历是2415736,则该二叉树的后根遍历是()。
{{ select(25) }}
- 4257631
- 4275631
- 7425631
- 4276531
26.【NOIP2010】一棵二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结 点的左子树的结点个数可能是()。
{{ select(26) }}
- 2
- 3
- 4
- 5
不定项选择题
1.【NOIP2008】设T是一棵有n个顶点的树，下列说法正确的是( )。
{{ multiselect(27) }}
- T是连通的、无环的
- T是连通的，有n-1条边
- T是无环的，有n-1条边
- 以上都不对
2.【NOIP2018】下列说法中，是树的性质的有( )。
{{ multiselect(28) }}
- 无环
- 任意两个结点之间有且只有一条简单路径
- 有且只有一个简单环
- 边的数目恰是顶点数目减1
3.【NOIP2015】下列有关树的叙述中，叙述正确的有( )。
{{ multiselect(29) }}
- 在含有n个结点的树中，边数只能是(n-1)条
- 在哈夫曼树中，叶结点的个数比非叶结点个数多1
- 完全二叉树一定是满二叉树
- 在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先
4.【NOIP2008】二叉树T,已知其先根遍历是1243576(数字为结点的编号，以下同),后根遍历是4275631,则该二叉树的可能的中根遍历是( )。
{{ multiselect(30) }}
- 4217536
- 2417536
- 4217563
- 2415736
5.【NOIP2011】如果根结点的深度记为1,则一棵恰有2011个叶子结点的二叉树的深度可能是( )。
{{ multiselect(31) }}
- 10
- 11
- 12
- 2011
6.【NOIP2012】一棵二叉树一共有19个节点，其叶子节点可能有( )个。
{{ multiselect(32) }}
- 1
- 9
- 10
- 11
7.【NOIP2018】 2-3树是一种特殊的树，它满足两个条件：
(1)每个内部结点有两个或三个子结点； (2)所有的叶结点到根的路径长度相同。 如果一棵2-3树有10个叶结点，那么它可能有( )个非叶结点。
{{ multiselect(33) }}
- 5
- 6
- 7
- 8