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 · 目视转录

一棵有 nn 个结点的树的所有结点的度数之和为( )。

A. n−1n-1

B. nn

C. n+1n+1

D. 2n2n

查看答案与解析

答案:A。

除根结点外,其他每个结点都是某个结点的孩子,因此树中所有结点的度数加 1 等于结点数,即所有结点的度数之和等于总结点数减 1。这是一个重要的结论,做题时经常用到。

单项选择题 03

原书题目P127 · 解析P128 · 目视转录

树的路径长度是从树根到每个结点的路径长度的( )。

A. 总和

B. 最小值

C. 最大值

D. 平均值

查看答案与解析

答案:A。

树的路径长度是指树根到每个结点的路径长的总和,根到每个结点的路径长度的最大值应是树的高度减 1。注意与哈夫曼树的带权路径长度相区别。

单项选择题 04

原书题目P127 · 解析P128 · 目视转录

对于一棵具有 nn 个结点、度为 4 的树来说,( )。

A. 树的高度至多是 n−3n-3

B. 树的高度至多是 n−4n-4

C. 第 ii 层上至多有 4(i−1)4(i-1) 个结点

D. 至少在某一层上正好有 4 个结点

查看答案与解析

答案:A。

要使得具有 nn 个结点、度为 4 的树的高度最大,就要使得每层的结点数尽可能少:除最后一层外,每层的结点数是 1,最后一个非叶结点有 4 个叶孩子。最终该树的高度为 n−3n-3。树的度为 4 只能说明存在某结点正好(也是最多)有 4 个孩子结点,选项 D 错误。

○
│
○        前n-4层各1个结点
⋮
○
├─○
├─○
├─○
└─○      最后一层4个叶结点

单项选择题 05

原书题目P127 · 解析P128 · 目视转录

度为 4、高度为 hh 的树,( )。

A. 至少有 h+3h+3 个结点

B. 至多有 4h−14h-1 个结点

C. 至多有 4h4h 个结点

D. 至少有 h+4h+4 个结点

查看答案与解析

答案:A。

要使得度为 4、高度为 hh 的树的总结点数最少,需要满足以下两个条件:

① 至少有一个结点有 4 个分支。

② 每层的结点数目尽可能少。

可令前 h−1h-1 层各只有一个结点,在第 h−1h-1 层结点下连接 4 个叶结点,结点个数为 h+3h+3。

要使得度为 4、高度为 hh 的树的总结点数最多,应使每个非叶结点的度均为 4,即满树,总结点个数最多为 1+4+42+⋯+4h−11+4+4^2+\cdots+4^{h-1}。

对于上面的两题,应画出草图来求解,就能一目了然。

单项选择题 06

原书题目P127 · 解析P128 · 目视转录

假定一棵度为 3 的树中,结点数为 50,则其最小高度为( )。

A. 3

B. 4

C. 5

D. 6

查看答案与解析

答案:C。

要求满足条件的树,那么该树是一棵完全三叉树。在度为 3 的完全三叉树中,第 1 层有 1 个结点,第 2 层有 31=33^1=3 个结点,第 3 层有 32=93^2=9 个结点,第 4 层有 33=273^3=27 个结点,因此结点数之和为 1+3+9+27=401+3+9+27=40,第 5 层的结点数为 50−40=1050-40=10 个,因此最小高度为 5。

单项选择题 07

原书题目P127 · 解析P128 · 目视转录

设有一棵度为 3 的树,其中度为 3 的结点数 n3=2n_3=2,度为 2 的结点数 n2=1n_2=1,叶结点数 n0=6n_0=6,则该树的结点总数为( )。

A. 12

B. 9

C. 10

D. ≥9 的任意整数

查看答案与解析

答案:D。

总结点数 n=n0+n1+n2+n3=6+n1+1+2=n1+9n=n_0+n_1+n_2+n_3=6+n_1+1+2=n_1+9,总度数 n−1=n1+2n2+3n3=n1+2+6=n1+8n-1=n_1+2n_2+3n_3=n_1+2+6=n_1+8,根据题目条件无法得出 nn 的具体值,只能证明 nn 是一个大于或等于 9 的任意整数。

例如可先构造一个 9 结点的树:根有 3 个孩子,三个孩子的度分别为 2、0、3,其余均为叶结点;再在任意分支上增加度为 1 的结点,给定的 n0,n2,n3n_0,n_2,n_3 均不变,故无法确定 nn 的具体数量。

单项选择题 08

原书题目P127 · 解析P129 · 目视转录

设一棵 mm 叉树中有 N1N_1 个度数为 1 的结点、N2N_2 个度数为 2 的结点……NmN_m 个度数为 mm 的结点,则该树中共有( )个叶结点。

A. ∑i=1m(i−1)Ni\displaystyle\sum_{i=1}^{m}(i-1)N_i

B. ∑i=1mNi\displaystyle\sum_{i=1}^{m}N_i

C. ∑i=2m(i−1)Ni\displaystyle\sum_{i=2}^{m}(i-1)N_i

D. ∑i=2m(i−1)Ni+1\displaystyle\sum_{i=2}^{m}(i-1)N_i+1

查看答案与解析

答案:D。

设叶结点数为 N0N_0,总结点数为 NN,则 N=N1+2N2+3N3+⋯+mNm+1N=N_1+2N_2+3N_3+\cdots+mN_m+1,又因为 N=N0+N1+N2+N3+⋯+NmN=N_0+N_1+N_2+N_3+\cdots+N_m,所以

N0=N2+2N3+⋯+(m−1)Nm+1=∑i=2m(i−1)Ni+1.N_0=N_2+2N_3+\cdots+(m-1)N_m+1=\sum_{i=2}^{m}(i-1)N_i+1.

单项选择题 09

原书题目P127 · 解析P129 · 目视转录

【2010 统考真题】在一棵度为 4 的树 T 中,若有 20 个度为 4 的结点、10 个度为 3 的结点、1 个度为 2 的结点、10 个度为 1 的结点,则树 T 的叶结点个数是( )。

A. 41

B. 82

C. 113

D. 122

查看答案与解析

答案:B。

设树中度为 ii(i=0,1,2,3,4i=0,1,2,3,4)的结点数分别为 nin_i,树中结点总数为 nn,则 n=n= 分支数 +1+1,而分支数又等于树中各结点的度之和,即

n=1+n1+2n2+3n3+4n4=n0+n1+n2+n3+n4.n=1+n_1+2n_2+3n_3+4n_4=n_0+n_1+n_2+n_3+n_4.

依题意,n1+2n2+3n3+4n4=10+2+30+80=122n_1+2n_2+3n_3+4n_4=10+2+30+80=122,n1+n2+n3+n4=10+1+10+20=41n_1+n_2+n_3+n_4=10+1+10+20=41,可得出 n0=82n_0=82,即树 T 的叶结点的个数是 82。

单项选择题 10

原书题目P127 · 解析P129 · 目视转录

【2016 统考真题】若森林 F 有 15 条边、25 个结点,则 F 包含树的个数是( )。

A. 8

B. 9

C. 10

D. 11

查看答案与解析

答案:C。

解法 1:树有一个重要性质,即在 nn 个结点的树中有 n−1n-1 条边,“那么对于每棵树,其结点数比边数多 1”。本题森林中的结点数比边数多 10(25−15=1025-15=10),显然共有 10 棵树。

解法 2:仔细分析后发现此题也是考查图的性质:生成树和生成森林。对于图的生成树有个重要的性质,即图中顶点数若为 nn,则其生成树含有 n−1n-1 条边。对比解法 1 中树的性质,不难发现两种解法都用到了性质“树中结点数比边数多 1”,后面的分析如解法 1。

综合应用题

综合应用题 01

原书题目P127 · 解析P129 · 目视转录

含有 nn 个结点的三叉树的最小高度是多少?

查看答案与解析

要求含有 nn 个结点的三叉树的最小高度,那么满足条件的一定是一棵完全三叉树。设含有 nn 个结点的完全三叉树高度为 hh,第 hh 层至少有 1 个结点,至多有 3h−13^{h-1} 个结点。则有

1+3+32+⋯+3h−2<n≤1+3+32+⋯+3h−1,1+3+3^2+\cdots+3^{h-2}<n\le1+3+3^2+\cdots+3^{h-1},

即 (3h−1−1)/2<n≤(3h−1)/2(3^{h-1}-1)/2<n\le(3^h-1)/2,得 3h−1<2n+1≤3h3^{h-1}<2n+1\le3^h,即 h<log⁡3(2n+1)+1h<\log_3(2n+1)+1,h≥log⁡3(2n+1)h\ge\log_3(2n+1)。

因为 hh 只能为正整数,h=⌈log⁡3(2n+1)⌉h=\lceil\log_3(2n+1)\rceil,所以三叉树的最小高度是 ⌈log⁡3(2n+1)⌉\lceil\log_3(2n+1)\rceil。

综合应用题 02

原书题目P127 · 解析P129 · 目视转录

已知一棵度为 4 的树中,度为 0、1、2、3 的结点数分别为 14、4、3、2,求该树的结点总数 nn 和度为 4 的结点个数,并给出推导过程。

查看答案与解析

设树中度为 ii(i=0,1,2,3,4i=0,1,2,3,4)的结点数为 nin_i,则结点总数 n=n0+n1+n2+n3+n4n=n_0+n_1+n_2+n_3+n_4,即 n=23+n4n=23+n_4。

根据“树中所有结点的度数加 1 等于结点数”的结论,有 n=0+n1+2n2+3n3+4n4+1n=0+n_1+2n_2+3n_3+4n_4+1,即有 n=17+4n4n=17+4n_4。

综合两式得 n4=2n_4=2,n=25n=25。所以该树的结点总数为 25,度为 4 的结点个数为 2。

综合应用题 03

原书题目P127 · 解析P129 · 目视转录

已知一棵度为 mm 的树中,有 n1n_1 个度为 1 的结点,有 n2n_2 个度为 2 的结点……有 nmn_m 个度为 mm 的结点,问该树有多少个叶结点?

查看答案与解析

树中的结点数等于所有结点的度数加 1,因此有

n=∑i=0mini+1=n1+2n2+3n3+⋯+mnm+1.n=\sum_{i=0}^{m}i n_i+1=n_1+2n_2+3n_3+\cdots+mn_m+1.

又有 n=n0+n1+n2+⋯+nmn=n_0+n_1+n_2+\cdots+n_m,所以

n0=(n1+2n2+3n3+⋯+mnm+1)−(n1+n2+⋯+nm)=n2+2n3+⋯+(m−1)nm+1=1+∑i=2m(i−1)ni.\begin{aligned} n_0&=(n_1+2n_2+3n_3+\cdots+mn_m+1)-(n_1+n_2+\cdots+n_m)\\ &=n_2+2n_3+\cdots+(m-1)n_m+1\\ &=1+\sum_{i=2}^{m}(i-1)n_i. \end{aligned}

注意:综合以上几题,常用于求解树结点与度之间关系的有:

① 总结点数 =n0+n1+n2+⋯+nm=n_0+n_1+n_2+\cdots+n_m。

② 总分支数 =n1+2n2+⋯+mnm=n_1+2n_2+\cdots+mn_m(度为 mm 的结点引出 mm 条分支)。

③ 总结点数=总分支数+1。

这类题目常在选择题中出现,读者对以上关系应当熟练掌握并灵活应用。