数据结构 - 树习题

数据结构——树练习

注：“[]”为向上取整，“{}”为向下取整。 一、填空题

1、二叉树第i(i>=1)层上至多有__2^(i-1)___个结点。 2、深度为k(k>=1)的二叉树至多有___2^k -1__个结点。 3、具有n个结点的完全二叉树的深度为__log2(n+1)____。

4、具有n个结点的二叉树中,一共有____2n___个指针域,其中只有____n-1___个用来指向结点的左右孩子，其余的___n+1_____个指针域为NULL。

5、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的___第一个_____个结点。 6、在____先序____遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

7、具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是____n/2____，编号最小的分支结点序号是___1____，编号最大的叶子结点序号是_____n__，编号最小的叶子结点序号是__n/2 +1_____。

8、先根遍历树和先根遍历与该树对应的二叉树，其结果___相同____（填“相同”或“不同”）。

9、由____一颗树___转换成二叉树时，其根结点的右子树总是空的。 10、若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为___n-1____。

11、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为___n-2m+1___个。

12、现有按中序遍历二叉树的结果为ABC，问有____5__种不同形态的二叉树可以得到这一遍历结果

13、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有____12___个叶子结点。

二、单选题 1、1． ( 1. )

①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种\分支层次\结构 ⑤任何只含一个结点的集合是一棵树 2.

以

下

说

法

错

误

的

以

下

说

法

错

误

的

是

是

( 4 )

①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达

②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好

3、深度为( )

6的二叉树最多有( 2 )个结点

①64 ②63 ③32 ④31

4、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( 4 ) ①42 ②40 ③21 ④20

5、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( 3 )

①肯定发生变化 ②有时发生变化 ③肯定不发生变化 ④无法确定

6、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ 3）个 ①k+1 ②2k ③2k-1 ④2k+1 7

、

下

列

说

法

正

确

的

是

( 1 )

①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同 8、设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子

树上有（ 4）个结点。

①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4

9、已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ 4 ）

①acbed ②deabc ③decab ④cedba 10、如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（ 1）

①前序 ②中序 ③后序 ④层次序 11、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( 1 ) ①正确 ②错误 12

、

树

最

适

合

用

来

表

示

( 3 )

①有序数据元素 ②无序数据元素

③元素之间具有分支层次关系的数据 ④元素之间无联系的数据

13、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ 1 ）数据结构

①栈 ②树 ③双向队列 ④顺序表 14

、

以

下

说

法

错

误

的

是

( 2 )

①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同

②二叉树是树的特殊情形

③由树转换成二叉树，其根结点的右子树总是空的

④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

15．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（a ）。 (A) BADC (C) CDAB

16.设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

17.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 18、下图所示的森林：

(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树；

(B) BCDA (D) CBDA

ABD(a)CEFIGHJ(b)K

19.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。

15.将P168页图7.8所示的二叉树转换成森林。

16.用7，9，2，6，32，3，21，10作为叶子节点，建立哈夫曼树，并写出哈夫曼编码。

本文来源：https://www.bwwdw.com/article/84pf.html