2025年数据库系统l试题库及答案第6章树和二叉树 .pdfVIP

百川东到海，何时复西归?少壮不努力，老大徒伤悲。——汉乐府

数据库系统l试题库及答案第6章树和⼆叉树

第6章树和⼆叉树

6.1知识点：树和⼆叉树的基本概念

—、填空题

1.⾼度为h,度为m的树中⾄少有______________个结点，⾄多有_______________个结点。

2.树的结点是由________及若⼲指向其⼦树的_______组成；结点拥有的⼦树数称为_______;度为0的结

点称为___________;度不为0的结点成为______________;树中结点的最⼤度数称为_________;树的最⼤层次称为

_____________。

3.对于⼀棵具有n个结点的树，该树中所有结点的度数之和为_________________。

4.如果结点A有3个兄弟结点，⽽且B是A的双亲，则B的度是___________________。

5.⼆叉树是另⼀种树形结构，它的特点是。

6.⼀颗度数为k且有2k-1个结点的⼆叉树称为_____________。

7.深度为k，且有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1到n

的结点--对应时，称之为________________。

8.⼀棵深度为6的满⼆叉树有_________个分⽀结点和________个叶⼦。

9.⼀棵具有257个结点的完全⼆叉树，它的深度为____________。

10.设⼀棵完全⼆叉树具有1000个结点，则此完全⼆叉树有________个叶⼦结点，有________个度为2的结

点，有_______个结点只有⾮空左⼦树，有_________个结点只有⾮空右⼦树。

11.由3个结点可以构成__________种形态的的⼆叉树，可以构成_________种形态的树。

12.将含有82个结点的完全⼆叉树从根结点开始顺序编号，根结点为第1号，其他结点⾃上向下，同⼀

层⾃左向右连续编号。则第40号结点的双亲结点的编号为________。

13.⼀棵⾼度为5的完全⼆叉树中，最多包含有________________个结点。

14.⼀棵具有n个结点的⼆叉树，若它有n0个叶⼦结点，则该⼆叉树上度为1的结点n仁______________。

15.在⾼度为h（h=0）的⼆叉树中⾄多可以有____________个结点，⾄少可以有____________个结点。

16.n个结点的⼆叉树最⼤⾼度是______________,最⼩⾼度是________________。

⼆、选择题

1.（）不含任何结点的空树（）。

A.是⼀棵树

B.是⼀棵⼆叉树

C.是⼀棵树也是⼀棵⼆叉树

D.既不是树也不是⼆叉树

2.（）⼀棵度为4的树中度为1、2、3、4的结点个数为4、3、2、1,则该树的结点总数为（

）。

A.21

B.26

君子忧道不忧贫。——孔丘

C.27

D.24

3.（）具有10个叶⼦结点的⼆叉树中有____________个度为2的结点。

A.8

B.9

C.10

D.11

5.（）如下的4棵⼆叉树中，（）不是完全⼆叉

树。

4.（）在⼀棵⾼度为h（假定根结点的层号为1）的完全⼆叉树中，所含结点个数不⼩于（）。

24-1

A.B.C.D.

6.（）设树T的度为4，其中度为

1,2,3,4的结点个数分别为4,2,1,1则T中的叶⼦数为（

）。

A.5

B.6

C.7

D.8

7.______________________________________________________()从供选择的答案中，选出应填⼊下⾯叙述内的最确

切的解答，把相应编号写在答卷的

对应栏内。

树是结点的有限集合，它A根结点，记为T。其余的结点分成为m(详0)个_B_________________

的集合T1,T2,…，Tm每个集合⼜都是树，此时结点T称为T的⽗结点，Ti称为T的⼦结点

(1im)。⼀个结点的⼦结点个数为该结点的C。

供选择的答案

A:①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上

B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交

C:①权②维数③次数(或度)④序

()在⼀棵⼆叉树的⼆叉链表中，空指针域数等于⾮空指针域数加(、)。

A?2

B?1

C?0D.-1

三、简答题

1?⼀棵度为2的树与⼀棵⼆叉树有何区别?

6.2知识点