1、数据结构树练习注：“”为向上取整， “”为向下取整。一、填空题1、二叉树第 i(i=1)层上至多有_2(i-1)_个结点。2、深度为 k(k=1)的二叉树至多有_2k -1_个结点。3、具有 n 个结点的完全二叉树的深度为_log 2(n+1)_。4、具有 n 个结点的二叉树中,一共有_2n_个指针域,其中只有_n-1_个用来指向结点的左右孩子，其余的_n+1_个指针域为 NULL。5、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的_第一个_个结点。6、在_先序_遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。7、具有 n 个结
2、点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为 1 号） ，则编号最大的分支结点序号是_n/2_，编号最小的分支结点序号是_1_，编号最大的叶子结点序号是_n_，编号最小的叶子结点序号是_n/2 +1_。8、先根遍历树和先根遍历与该树对应的二叉树，其结果_相同_（填“相同”或“不同” ） 。9、由_一颗树_转换成二叉树时，其根结点的右子树总是空的。10、若一棵二叉树的叶子数为 n，则该二叉树中，左、右子树皆非空的结点个数为_n-1_。11、任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为_n-2m+1 _个。12、现有按中序遍历二叉树的结果
3、为 ABC，问有_5_种不同形态的二叉树可以得到这一遍历结果13、已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度过为 2 的结点，4 个度为 3 的结点，则该树中有_12_个叶子结点。二、单选题1、1 以下说法错误的是 ( 1. )树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据树(及一切树形结构)是一种“分支层次“结构任何只含一个结点的集合是一棵树2.以下说法错误的是 ( 4 )完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达在三叉链表上，二叉树的求双亲运算很容易实现在二叉链表上，求根，求左、右孩子等
4、很容易实现在二叉链表上，求双亲运算的时间性能很好3、深度为 6 的二叉树最多有( 2 )个结点 ( )64 63 32 314、将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的双结点编号为 ( 4 )42 40 21 205、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( 3 ) 肯定发生变化 有时发生变化肯定不发生变化 无法确定6、设深度为 k 的二叉树上只有度为 0 和度为 2 的节点，则这类二叉树上所含结点总数最少（ 3）个k+1 2k 2k-1 2k+17、下列说法正确的是 ( 1 )树的
5、先根遍历序列与其对应的二叉树的先根遍历序列相同树的先根遍历序列与其对应的二叉树的后根遍历序列相同树的后根遍历序列与其对应的二叉树的先根遍历序列相同树的后根遍历序列与其对应的二叉树的后根遍历序列相同8、设森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林 T 转换成一棵二叉树后，且根结点的右子树上有（ 4）个结点。n 1-1 n 1 n 1+n2+n3 n 2+n3+n49、已知某二叉树的后续遍历序列是 dabec,中序遍历序列是 deabc,它的前序遍历序列是（ 4 ）acbed deabc decab cedba10、如果 T2是由有序树 T
6、转化而来的二叉树，那么 T 中结点的前序就是 T2中结点的（ 1）前序 中序 后序 层次序11、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( 1 )正确 错误12、树最适合用来表示 ( 3 )有序数据元素 无序数据元素元素之间具有分支层次关系的数据 元素之间无联系的数据13、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ 1 ）数据结构栈 树 双向队列 顺序表14、以下说法错误的是 ( 2 )存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同二叉树是树的特殊情形由树转换成二叉树，其根结点的右子树总是空的在二叉树只有一棵子树的情况下也要明确指
7、出该子树是左子树还是右子树15设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（a ） 。(A) BADC (B) BCDA(C) CDAB (D) CBDA16.设一棵树 T 中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F) ，(C，G)，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。17.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。18、下图所示的森林： (1) 求树（a ）的先根序列和后根序列； (2) 求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)19.设某棵二叉树的中序遍历序列为 DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。15.将 P168 页图 7.8 所示的二叉树转换成森林。16.用 7，9，2，6，32，3，21，10 作为叶子节点，建立哈夫曼树，并写出哈夫曼编码。
