树和二叉树练习new

《树和二叉树练习new》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树和二叉树练习一、选择题1.有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最合适的数据结构为（）。A．向量B.树C.图D二叉树B2.树最合适用来表示（）。A.有序数据元素B.元素之间具有分支层次关系的数据C.无序数据元素D.元素之间无联系的数据.B3.树B的层号表示为1a,2b,3d,3e,2c,对应于下面选择的（）。A.1a(2b(3d,3e),2c)B.a(b(D.,e),c)C.a(b(d,e),c)D.a(b,d(e),c)c4.对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同

2、一结点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（）次序的遍历实现二叉树的结点编号。A.先序B.中序C.后序D.从根开始按层次遍历C按照二叉树的定义，具有3个结点的二叉树有（）种。A.3B.4C.5D.6C在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1,度为0的结点数为n0，则树的最大高度为（），其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采用链表存储结构，则有（）个空链域。A.n/2B.[log2n+1]C.log2nD.nE.n0+n1+n2F.n1+n2G.n2+1H.1I.n+1J.

3、n1K.n2L.n1+1EGBGI对一个满二叉树，m个树叶，n个结点，深度为h,则（）。n=h+mB.h+m=2nC.m=h-1D.n=2h–1D设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（），至多为（）。A.2hB.2h–1C.2h+1D.h+1E.2h-1F.2h–1G.2h+1+1H.2h+1BF最少的情况：除了第一层外，每层最少有两个结点，故2h-1深度为5的二叉树至多有（）个结点。A.16B.32C.31D.10C假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个

4、。A.15B.16C.17D.47Bn0=n2+1用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（）。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]B在一非空二叉树的中序遍历序列中，根结点的左边（）A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点D任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序（）。A．不发生改变B.发生改变C.不能确定D.以上都不对A设n,m为一棵树上的两个结点，在中序遍历时，n在

5、m前的条件是（）。n在m右方B.n是m祖先C.n在m左方D.n是m子孙C一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前趋为（），后序遍历中结点B的直接后继是（）。（1）B（2）D（3）A（4）I（5）F（6）C(4)(5)先序：ABDHIECFG后序：HIDEBFGCA已知某二叉树的后序遍历是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A.acbedB.decabC.deabcD.cedbaD二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。A.前序B

6、.中序C.后序D.层次C在线索化二叉树中，Ｔ所指结点没有左子树的充要条件是（）。Ａ.Tleft=NULLB.Tltag=1C.Tltag=1且Tleft=NULLD以上都不对B线索二叉树是一种（）结构。Ａ.逻辑　　Ｂ.逻辑和存储Ｃ.物理D.线性C将图中的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向（）。（1）A，D(2)B,C(3)D,A（4）C，A(3)ABDCXEY树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历，中序遍历和后序遍历。这里，把由树转化得到的二叉树叫做这棵树对应得二叉树。下面结论

7、正确的是（）。A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的后序遍历序列与其对应的二叉树的后序遍历序列相同C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对A30.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（）。A．前序B.中序C.后序D.层次序A31.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A．前序B.中序C.后序D层次序B如图所示的t2是由有序树t1转化而来的二叉树，那么树t1有（）个叶结点。A.4B.5C.6D.7Cabecfhigdj

8、转换为对应的森林由带权为８，２，５，７的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。Ａ.23B.37C.46D.43D二、填空题1.在树形结构中，树根结