1/17第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为()。A.向量B.树C图D.二叉树2．树最合适用来表示()。A.有序数据元素B元素之间具有分支层次关系的数据C无序数据元素D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的()。A.la(2b(3d,3e),2c)B.a(b(D,e),c)C.a(b(d,e),c)D.a(b,d(e),c)4.高度为h的完全二叉树至少有()个结点，至多有()个结点。A.2h_lB.hC．2h-1D.2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为()。A.2iB.2i-lC.2i+lD.2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为()。A.3B.4C.5D.67.深度为5的二叉树至多有()个结点。A.31B.32C.16D.108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为()个。A.15B.16C.17D.479.题图6-1中，()是完全二叉树，()是满二叉树。2/1710.在题图6-2所示的二叉树中：(1)A结点是A.叶结点B根结点但不是分支结点C根结点也是分支结点D.分支结点但不是根结点(2)J结点是A.叶结点B．根结点但不是分支结点C根结点也是分支结点D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.DC．空D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为()。A.5B.6C.7D.812.一棵有124个叶结点的完全二叉树，最多有()个结点。A．247B．248C．249D．25013.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1⋯n]中，结点R[i]若有左子树，则左子树是结点()。A.R[2i+l]B.R[2i]C.R[i/2]D.R[2i-1]14.在一非空二叉树的中序遍历序列中，根结点的右边()。3/17A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点15．一棵度为m的树中，有ni个度为1的结点，有n2个度为2的结点⋯⋯，有nm个度为m的结点，则该树的叶结点数为()。A.n1+n2+...+nmB.(m-l)nm+...+n2+1C.n1+n2+1D.nl-n216.已知某二叉树的中序遍历序列是debac，后序遍历序列是dabec，它的前序遍历序列是()。A.acbedB.decabC.deabcD.cedba17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加()。A.2B.1C.0D.-118.线索二叉树是一种()结构。A.逻辑B．逻辑和存储C．物理D.线性19.由权值分别是8，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.23B.37C．46D.4320.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是()。A.2B.3C.4D.5二、填空题1.对于一棵具有n个结点的树，该树中所有结点的度数之和为____。2.在树型结构中，树根结点没有____结点，其余每个结点有且只有____个前驱结点：叶子结点没有____结点，其余每个结点可以有____后继结点。3.有一棵树如题图6-3所示，回答下面的问题。这棵树的根点是____；叶子结点是____；结点k3的度是____；结点k3的子女是____；结点k3的父结点是____；这棵树的度为____；这棵树的深度是____。4/174.假定一棵树的广义表表示为A(B(E)，C(F(H，I，J，G)，D)，则该树的度为____，树的深度为____，终端结点的个数为____，单分支结点的个数为____，双分支结点的个数为____，3分支结点的个数为____，C结点的双亲结点为____，其孩子结点为____。5.一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子树。如果按层次顺序（同层自左至右）从1开始对全部结点编号，则：(1)第i层结点数目是____。(2)编号为n的结点的双亲结点（若存在）的编号是____。(3)编号为n的结点的第i个孩子结点（若存在）的编号是____。(4)编号为n的结点有右兄弟的条件是____：其右兄弟的编号是____。6．前序遍历一棵树相当于____树中对应的二叉树，后序遍历一棵树则相当于树中对应的二叉树。7．二叉树的遍历分为____，树与森林的遍历包括____。8．一棵二叉树的第i(i>=1)层最多有____个结点；一棵有n(n>0)个结点的满二叉树共有...
