5.1 树的基本概念·习题
复习入口
5.1 树的基本概念 · 5.1.1 树的定义 · 5.1.2 基本术语 · 5.1.3 树的性质
本节共13题:选择题10题,综合应用题3题。每题答案紧接题目折叠显示。
文字转录进度:13/13题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P126 · 解析P127 · 目视转录
树最适合用来表示( )的数据。
A. 有序
B. 无序
C. 任意元素之间具有多种联系
D. 元素之间具有分支层次关系
查看答案与解析
答案:D。
树是一种分层结构,它特别适合组织那些具有分支层次关系的数据。
单项选择题 02
原书题目P127 · 解析P127 · 目视转录
一棵有 个结点的树的所有结点的度数之和为( )。
A.
B.
C.
D.
查看答案与解析
答案:A。
除根结点外,其他每个结点都是某个结点的孩子,因此树中所有结点的度数加 1 等于结点数,即所有结点的度数之和等于总结点数减 1。这是一个重要的结论,做题时经常用到。
单项选择题 03
原书题目P127 · 解析P128 · 目视转录
树的路径长度是从树根到每个结点的路径长度的( )。
A. 总和
B. 最小值
C. 最大值
D. 平均值
查看答案与解析
答案:A。
树的路径长度是指树根到每个结点的路径长的总和,根到每个结点的路径长度的最大值应是树的高度减 1。注意与哈夫曼树的带权路径长度相区别。
单项选择题 04
原书题目P127 · 解析P128 · 目视转录
对于一棵具有 个结点、度为 4 的树来说,( )。
A. 树的高度至多是
B. 树的高度至多是
C. 第 层上至多有 个结点
D. 至少在某一层上正好有 4 个结点
查看答案与解析
答案:A。
要使得具有 个结点、度为 4 的树的高度最大,就要使得每层的结点数尽可能少:除最后一层外,每层的结点数是 1,最后一个非叶结点有 4 个叶孩子。最终该树的高度为 。树的度为 4 只能说明存在某结点正好(也是最多)有 4 个孩子结点,选项 D 错误。
○
│
○ 前n-4层各1个结点
⋮
○
├─○
├─○
├─○
└─○ 最后一层4个叶结点
单项选择题 05
原书题目P127 · 解析P128 · 目视转录
度为 4、高度为 的树,( )。
A. 至少有 个结点
B. 至多有 个结点
C. 至多有 个结点
D. 至少有 个结点
查看答案与解析
答案:A。
要使得度为 4、高度为 的树的总结点数最少,需要满足以下两个条件:
① 至少有一个结点有 4 个分支。
② 每层的结点数目尽可能少。
可令前 层各只有一个结点,在第 层结点下连接 4 个叶结点,结点个数为 。
要使得度为 4、高度为 的树的总结点数最多,应使每个非叶结点的度均为 4,即满树,总结点个数最多为 。
对于上面的两题,应画出草图来求解,就能一目了然。
单项选择题 06
原书题目P127 · 解析P128 · 目视转录
假定一棵度为 3 的树中,结点数为 50,则其最小高度为( )。
A. 3
B. 4
C. 5
D. 6
查看答案与解析
答案:C。
要求满足条件的树,那么该树是一棵完全三叉树。在度为 3 的完全三叉树中,第 1 层有 1 个结点,第 2 层有 个结点,第 3 层有 个结点,第 4 层有 个结点,因此结点数之和为 ,第 5 层的结点数为 个,因此最小高度为 5。
单项选择题 07
原书题目P127 · 解析P128 · 目视转录
设有一棵度为 3 的树,其中度为 3 的结点数 ,度为 2 的结点数 ,叶结点数 ,则该树的结点总数为( )。
A. 12
B. 9
C. 10
D. ≥9 的任意整数
查看答案与解析
答案:D。
总结点数 ,总度数 ,根据题目条件无法得出 的具体值,只能证明 是一个大于或等于 9 的任意整数。
例如可先构造一个 9 结点的树:根有 3 个孩子,三个孩子的度分别为 2、0、3,其余均为叶结点;再在任意分支上增加度为 1 的结点,给定的 均不变,故无法确定 的具体数量。
单项选择题 08
原书题目P127 · 解析P129 · 目视转录
设一棵 叉树中有 个度数为 1 的结点、 个度数为 2 的结点…… 个度数为 的结点,则该树中共有( )个叶结点。
A.
B.
C.
D.
查看答案与解析
答案:D。
设叶结点数为 ,总结点数为 ,则 ,又因为 ,所以
单项选择题 09
原书题目P127 · 解析P129 · 目视转录
【2010 统考真题】在一棵度为 4 的树 T 中,若有 20 个度为 4 的结点、10 个度为 3 的结点、1 个度为 2 的结点、10 个度为 1 的结点,则树 T 的叶结点个数是( )。
A. 41
B. 82
C. 113
D. 122
查看答案与解析
答案:B。
设树中度为 ()的结点数分别为 ,树中结点总数为 ,则 分支数 ,而分支数又等于树中各结点的度之和,即
依题意,,,可得出 ,即树 T 的叶结点的个数是 82。
单项选择题 10
原书题目P127 · 解析P129 · 目视转录
【2016 统考真题】若森林 F 有 15 条边、25 个结点,则 F 包含树的个数是( )。
A. 8
B. 9
C. 10
D. 11
查看答案与解析
答案:C。
解法 1:树有一个重要性质,即在 个结点的树中有 条边,“那么对于每棵树,其结点数比边数多 1”。本题森林中的结点数比边数多 10(),显然共有 10 棵树。
解法 2:仔细分析后发现此题也是考查图的性质:生成树和生成森林。对于图的生成树有个重要的性质,即图中顶点数若为 ,则其生成树含有 条边。对比解法 1 中树的性质,不难发现两种解法都用到了性质“树中结点数比边数多 1”,后面的分析如解法 1。
综合应用题
综合应用题 01
原书题目P127 · 解析P129 · 目视转录
含有 个结点的三叉树的最小高度是多少?
查看答案与解析
要求含有 个结点的三叉树的最小高度,那么满足条件的一定是一棵完全三叉树。设含有 个结点的完全三叉树高度为 ,第 层至少有 1 个结点,至多有 个结点。则有
即 ,得 ,即 ,。
因为 只能为正整数,,所以三叉树的最小高度是 。
综合应用题 02
原书题目P127 · 解析P129 · 目视转录
已知一棵度为 4 的树中,度为 0、1、2、3 的结点数分别为 14、4、3、2,求该树的结点总数 和度为 4 的结点个数,并给出推导过程。
查看答案与解析
设树中度为 ()的结点数为 ,则结点总数 ,即 。
根据“树中所有结点的度数加 1 等于结点数”的结论,有 ,即有 。
综合两式得 ,。所以该树的结点总数为 25,度为 4 的结点个数为 2。
综合应用题 03
原书题目P127 · 解析P129 · 目视转录
已知一棵度为 的树中,有 个度为 1 的结点,有 个度为 2 的结点……有 个度为 的结点,问该树有多少个叶结点?
查看答案与解析
树中的结点数等于所有结点的度数加 1,因此有
又有 ,所以
注意:综合以上几题,常用于求解树结点与度之间关系的有:
① 总结点数 。
② 总分支数 (度为 的结点引出 条分支)。
③ 总结点数=总分支数+1。
这类题目常在选择题中出现,读者对以上关系应当熟练掌握并灵活应用。