资源简介

一、 树、二叉树的概念及其性质
1. 下列选项中,属于非线性数据结构的是(　A　)
A. 二叉树 B. 队列
C. 栈 D. 数组
【解析】 二叉树是一种非线性的数据结构,A符合题意。
2. 下列选项中,最适合用树表示的是(　D　)
A. 有序的数据元素
B. 无序的数据元素
C. 元素间无任何联系的数据
D. 元素间具有分支层次关系的数据
【解析】 树的最大特点是可以描述具有分支层次关系的数据,D正确。
3. 已知某完全二叉树有2022个节点,则该二叉树的高度是(　C　)
A. 9 B. 10
C. 11 D. 12
【解析】 由完全二叉树的结点数n与高度h的关系为n=2h－1可知,h=[log22022]＋1=11,所以该完全二叉树的高度为11,C正确。
4. 某完全二叉树的节点数为20个,则其深度是(　B　)
A. 4 B. 5
C. 6 D. 7
【解析】 本题考查完全二叉树的性质。具有n个结点的完全二叉树的深度为[log220]＋1=5,模拟后可知,从上层到下层,其节点数分别为1＋2＋4＋8＋5=20,共5层,B正确。
5. 具有10个叶子节点的二叉树中,度为2的节点个数是(　B　)
A. 8 B. 9
C. 10 D. 11
【解析】 在任意一棵二叉树中,如果度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2＋1。因此,度为2的节点个数为10－1=9,B正确。
6. 在一棵二叉树上,第5层的节点数最多是(　C　)
A. 4 B. 8
C. 16 D. 32
【解析】 本题考查二叉树的性质。二叉树的第k层上最多有2k－1(k≥1)个节点,24=16,C正确。
7. 关于如图所示的树,下列说法中正确的是(　B　)
A. 该树中共有6个叶子节点
B. 该树的度为3,深度为4
C. E节点的父节点是A
D. 节点I和J都是B的孩子节点
【解析】 该树中共有5个叶子节点;E节点的父节点是B;节点I是D的孩子节点,节点J是E的孩子节点。B正确。
8. 一棵二叉树共有20个节点,其中5个是叶子节点,则度为1的节点数是(　A　)
A. 11 B. 10
C. 9 D. 8
【解析】 任意一棵二叉树节点度数都小于等于2(0、1、2),叶子节点数等于度为2的节点数＋1,所以度为1的节点数=20－5－4=11,A正确。
9. 在如图所示的4棵二叉树中,不是完全二叉树的是(　C　)
A. B.
C. D.
【解析】 完全二叉树最下面一层的叶子节点都依次排列在该层的最左边位置,C符合题意。
10. 已知一棵完全二叉树的节点总数为10个,则最后一层的节点数为(　C　)
A. 1 B. 2
C. 3 D. 4
【解析】 本题考查完全二叉树的特性。二叉树的节点总数为10个,则深度至少为4层,前三层分别为1＋2＋4=7,因此第四层节点数为10－7=3,B正确。
11. 某二叉树前序遍历为abdcef,中序遍历为dbaecf,则此二叉树的后序遍历为 (　A　)
A. dbefca B. debfca
C. dfebca D. dbfeca
【解析】 本题考查二叉树的遍历。前序遍历为abdcef,中序遍历为dbaecf,则说明根节点为a,其中根的左子树是bd,ecf是右子树,B、C错误。同时中序表达式中的“ecf”说明后序遍历时肯定是efc,A正确,D错误。
12. 某二叉树包含4个节点,共3层,该二叉树的形态有多种,如图所示为其中的一种形态。该形态的中序遍历序列中,根节点在第3个位置。在该树的各种可能的形态中,根节点出现在中序遍历序列中的同一个位置的形态不超过(　B　)
A. 1种 B. 2种
C. 3种 D. 4种
【解析】 本题考查二叉树的遍历。另外一种符合要求的二叉树的形态如图所示,B正确。
13. 已知完全二叉树T共有30个节点,则其叶子节点的数量为(　B　)
A. 10 B. 15
C. 16 D. 20
【解析】 分别用n0、n1和n2表示二叉树度为0、1和2的节点数量,则有n0＋n1＋n2=30,且n2=n0－1 ,可得n0=(31－n)/2,又因为完全二叉树中n的值为0或1,代入可得n0=15,B正确。
14. 某二叉树的中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA。下列关于该二叉树的说法,错误的是(　B　)
A. 该二叉树前序遍历的结果是ABDGCEF
B. 该二叉树是满二叉树
C. 该二叉树有3个叶子节点
D. 节点D是节点G的父节点
【解析】 本题考查二叉树的遍历。根据中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA可知,具体二叉树的形态如图所示。
因此该二叉树前序遍历的结果是ABDGCEF,A不符合题意。该二叉树不是一个满二叉树,B符合题意。该二叉树有3个叶子节点,C不符合题意。节点D是节点G的父节点,D不符合题意。
15. 有一棵深度为4的二叉树,已知其根节点左侧的节点总数比右侧的节点总数多1。下列关于该树的说法,正确的是(　D　)
A. 这肯定是一棵完全二叉树
B. 根节点右侧可能只有1个节点
C. 可能共有16个节点
D. 可能共有7个叶子节点
【解析】 本题考查二叉树知识。该树可能是、但不一定是完全二叉树,A错误。右侧最少有2个节点,B错误。深度为4,最多有15个节点,C错误。(共18张PPT)
一、 树、二叉树的概念及其性质
第四章　树
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 下列选项中,属于非线性数据结构的是(　　)
A. 二叉树 B. 队列
C. 栈 D. 数组
【解析】 二叉树是一种非线性的数据结构,A符合题意。
A
2. 下列选项中,最适合用树表示的是(　　)
A. 有序的数据元素
B. 无序的数据元素
C. 元素间无任何联系的数据
D. 元素间具有分支层次关系的数据
【解析】 树的最大特点是可以描述具有分支层次关系的数据,D正确。
D
3. 已知某完全二叉树有2022个节点,则该二叉树的高度是(　　)
A. 9 B. 10
C. 11 D. 12
【解析】 由完全二叉树的结点数n与高度h的关系为n=2h－1可知,h=[log22022]＋1=11,所以该完全二叉树的高度为11,C正确。
C
4. 某完全二叉树的节点数为20个,则其深度是(　　)
A. 4 B. 5
C. 6 D. 7
【解析】 本题考查完全二叉树的性质。具有n个结点的完全二叉树的深度为[log220]＋1=5,模拟后可知,从上层到下层,其节点数分别为1＋2＋4＋8＋5=20,共5层,B正确。
B
5. 具有10个叶子节点的二叉树中,度为2的节点个数是(　　)
A. 8 B. 9
C. 10 D. 11
【解析】 在任意一棵二叉树中,如果度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2＋1。因此,度为2的节点个数为10－1=9,B正确。
B
6. 在一棵二叉树上,第5层的节点数最多是(　　)
A. 4 B. 8
C. 16 D. 32
【解析】 本题考查二叉树的性质。二叉树的第k层上最多有2k－1(k≥1)个节点,24=16,C正确。
C
7. 关于如图所示的树,下列说法中正确的是(　　)
A. 该树中共有6个叶子节点
B. 该树的度为3,深度为4
C. E节点的父节点是A
D. 节点I和J都是B的孩子节点
【解析】 该树中共有5个叶子节点;E节点的父节点是B;
节点I是D的孩子节点,节点J是E的孩子节点。B正确。
B
8. 一棵二叉树共有20个节点,其中5个是叶子节点,则度为1的节点数是(　　)
A. 11 B. 10
C. 9 D. 8
【解析】 任意一棵二叉树节点度数都小于等于2(0、1、2),叶子节点数等于度为2的节点数＋1,所以度为1的节点数=20－5－4=11,A正确。
A
9. 在如图所示的4棵二叉树中,不. 是. 完全二叉树的是(　　)
C
A. B. C. D.
【解析】 完全二叉树最下面一层的叶子节点都依次排列在该层的最左边位置,C符合题意。
10. 已知一棵完全二叉树的节点总数为10个,则最后一层的节点数为(　　)
A. 1 B. 2
C. 3 D. 4
【解析】 本题考查完全二叉树的特性。二叉树的节点总数为10个,则深度至少为4层,前三层分别为1＋2＋4=7,因此第四层节点数为10－7=3,B正确。
C
关键能力练
11. 某二叉树前序遍历为abdcef,中序遍历为dbaecf,则此二叉树的后序遍历为 (　　)
A. dbefca B. debfca
C. dfebca D. dbfeca
【解析】 本题考查二叉树的遍历。前序遍历为abdcef,中序遍历为dbaecf,则说明根节点为a,其中根的左子树是bd,ecf是右子树,B、C错误。同时中序表达式中的“ecf”说明后序遍历时肯定是efc,A正确,D错误。
A
12. 某二叉树包含4个节点,共3层,该二叉树的形态有多种,如图所示为
其中的一种形态。该形态的中序遍历序列中,根节点在第3个位置。在
该树的各种可能的形态中,根节点出现在中序遍历序列中的同一个位置
的形态不超过(　　)
A. 1种 B. 2种
C. 3种 D. 4种
【解析】 本题考查二叉树的遍历。另外一种符合要求的二叉树的形态如图所示,B正确。
B
13. 已知完全二叉树T共有30个节点,则其叶子节点的数量为(　　)
A. 10 B. 15
C. 16 D. 20
【解析】 分别用n0、n1和n2表示二叉树度为0、1和2的节点数量,则有n0＋n1＋n2=30,且n2=n0－1 ,可得n0=(31－n)/2,又因为完全二叉树中n的值为0或1,代入可得n0=15,B正确。
B
14. 某二叉树的中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA。下列关于该二
叉树的说法,错. 误. 的是(　　)
A. 该二叉树前序遍历的结果是ABDGCEF
B. 该二叉树是满二叉树
C. 该二叉树有3个叶子节点
D. 节点D是节点G的父节点
【解析】 本题考查二叉树的遍历。根据中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA可知,具体二叉树的形态如图所示。
因此该二叉树前序遍历的结果是ABDGCEF,A不符合题意。该二叉树不是一个满二叉树,B符合题意。该二叉树有3个叶子节点,C不符合题意。节点D是节点G的父节点,D不符合题意。
B
15. 有一棵深度为4的二叉树,已知其根节点左侧的节点总数比右侧的节点总数多1。下列关于该树的说法,正确的是(　　)
A. 这肯定是一棵完全二叉树
B. 根节点右侧可能只有1个节点
C. 可能共有16个节点
D. 可能共有7个叶子节点
【解析】 本题考查二叉树知识。该树可能是、但不一定是完全二叉树,A错误。右侧最少有2个节点,B错误。深度为4,最多有15个节点,C错误。
D

展开更多......

收起↑