第四章 树 真题

2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ ） A.acbed B.becab C.deabc D.cedba

3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 12.有关树的叙述正确的是( )

A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点

C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____________。

30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。 34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ） A.23 B.37 C.44 D.46 12.用n个值构造一棵二叉排序树，它的最大高度为（ ） A.n/2 B. n C. n+1 D.log2n 21.若满二叉树的结点数为n，则其高度为________。

22.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点，那么其父结点的编号为_____。 23.深度为k的二叉树，结点数最多有________个。

24.某二叉树的后根遍历为ABKCBPM，则该二叉树的根为______。

29.某通讯电文由A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是6，

5，9，10，20，1，试画出这六个字符编码所用的哈夫曼树。

30.已知一棵二叉树的顺序存储结构如题30图所示，其中∧表示虚结点，试构造该二叉树。

A B G C D ∧ H ∧ ∧ E F 题30图

34.若两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。

8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ ） A.n-1 B.n C.n+1 D.2n

9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ） A.99 B.98 C.97 D.50 10.有m个叶子结点的哈夫曼树，其结点总数是（ ）

A.2m-1 B.2m C.2m+1 D.2(m+1) 22.深度为k的二叉树至多有______个结点，最少有______个结点。

29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。

30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。

13

8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（ ） A.n-1 B.n C.n+1 D.n+2

9.在一棵深度为H的完全二叉树中，所含结点的个数不少于（ ） A.2H-1-1 B.2H-1 C.2H-1 D.2H

19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为_______。 21.具有n个叶子结点的哈夫曼树，其结点总数为________。

22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。 30.画出题30图所示的二叉树的二叉链表存储结构。

35.设二叉树的结点类型定义如下： typedef struct node{ datatype data;

struct node*lchild,*rchild; }Bitree; Bitree*t;

试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t))。

8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )

A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点 9.在完全二叉树中，若一个结点是叶结点，则它没有( )

A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点 12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____。 20.深度为15的满二叉树上，第11层有_______个结点。

21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为________。 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。

8.除根结点外，树上每个结点( )

A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( )

14

A.2 B.3 C.5 D.8

20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。

21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。

29.分别写出题29图中二叉树的先根、中根、后根遍历序列。

10．高度为h的完全二叉树中，结点数最多为（ ）A．2h-1 B.2h+1 C.2h-1 D.2h 11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（ ）A．mn B.mn-1 C.n(m-1) D.m(n-1) 21．有4个结点且深度为4的二叉树的形态共有_______种。

22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。

30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。

8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ） A.3 B.4 C.5 D.6

9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ） A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。

22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。

29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。 7.关于二叉树性质的描述，正确的是（ ）

A.二叉树结点的个数可以为0 B.二叉树至少含有一个根结点 C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子

15

D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 8.具有4个结点的二叉树可有（ ）

A.4种形态 B.7种形态 C.10种形态 D.11种形态 22.深度为k的满二叉树其叶子结点个数共有________________个。 23.二叉树通常采用________________两种存储结构表示。 29.试采用类C语言，给出二叉树的二叉链表结构描述。

35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述 7.树是n个结点的有穷集合，( )

A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子C.2k-1个叶子 D.2k-1-1个叶子 22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。

23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。 29．对于如题29图所示二叉树，分别写出其先根遍历，中根遍历，后根遍历的结点访问序列。

35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。 7．深度为k的二叉树最多有（）个结点

22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为______。 23.具有n个结点的完全二叉树，其深度为___________。 29．已知某二叉树的顺序存储结构如图所示，试画出该二叉树。

35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左 右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。 7.根据定义，树的叶子结点其度数（ ）

A.必大于 0 B.必等于0 C.必等于1 D.必等于2

8.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（ ） A.2n个指针域其中n个指针为NULL B.2n个指针域其中n+1个指针为NULL C.2n-1个指针域其中n个指针为NULL D.2n-1个指针域其中n+1个指针为NULL 22.树的遍历主要有先根遍历、后根遍历和___________三种。 23.深度为k的完全二叉树至少有___________个结点。

29.已知某二叉树如下图所示，试给出其二叉链表及顺序存储结构表示。

16