搜索
第六章树和二叉树（下载后用阅读版式视图或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中，()是完全二叉树，()是满二叉树。10.在题图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.在一非空二叉树的中序遍历序列中，根结点的右边()。A.只有右子树上的所有结点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.假定一棵树的广义表表示为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(n0)个结点的满二叉树共有____个叶子和____个非终端结点。9.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点为____个。10．在一棵二叉树中，第五层上的结点数最多为____。11.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为____个，其中____个用于链接孩子结点，____个空闲着。12.前序遍历的顺序是ABDGEHICFJ，则二叉树的根是____。13.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是____14.结点最少的树为____，结点最少的二叉树为____。15.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在前序遍历中结点E的直接前驱为____，后序遍历中结点B的直接后继是____。16.某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为____，该二叉树对应的森林包括____棵树。17.用一维数组存放的一棵完全二叉树如题图6-4所示。则后序遍历该二叉树时结点访问的顺序为____。18.由n个权值构成的哈夫曼树共有____个结点。19.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为____。20.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有____个。21.二叉树的存储结构分为____，树的存储结构分为____。三、判断题1．树中任意结点的子树不必是有序的。()2．树可以看成特殊的无向图。()3．可以使用双链表表示树型结构。()4．顺序存储方式只能用于存储线性结构。()5．完全二叉树的某结点若无左孩子，则必是叶结点。()6．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。()7．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。()8．二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。()9．二叉树的前序和后序遍历序列能惟一确定这棵二叉树。()10.中序线索二叉树中，右线索若不为空，则一定指向其父结点。()四、算法和操作题1．假定一棵二叉树广义表表示为a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。前序：中序：后序：2．已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。中根序列：c，b，d，e，a，g，i,h,j，f后根序列：c，e，d，b，i，j，h，g，fa高度：双支：单支：叶子：3．已知一棵树边的集合为{ISPAN，M，ISPAN，N，ESPAN，I，BSPAN，E，BSPAN，D，ASPAN，B，GSPAN，J，GSPAN，K，CSPAN，G，CSPAN，F，HSPAN，L，CSPAN，H，ASPAN，C)，请画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点G的祖先？(5)哪些是结点G的孩子？(6)哪些是结点E的子孙？(7)哪些是结点E的兄弟？哪些是结点F的兄弟？(8)结点B和N的层次号分别是什么？(9)树的深度是多少？(10)以结点C为根的子树的深度是多少？4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。5.一棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。6．假设前序遍历某棵树的结点次序为SACEFBDGHIJK；后序遍历该树的结点次序为CFEABHGIKJDS，请画出这棵树。7．已知一棵树如题图6-5所示，将其转换为其孩子兄弟表示的二叉树。并画出该二叉树的后序线索二叉树。8．试找出分别满足下列条件的所有二叉树：(1)前序遍历序列和中序遍历序列相同。(2)中序遍历序列和后序遍历序列相同。(3)前序遍历序列和后序遍历序列相同。9．已知信息为“ABCDBCDCBDBACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：其中若ltag为0，则lchild指向结点的前驱，否则lchild指向左孩子结点；若rtag为0，则rchild指向结点的后继，否则rchild指向右孩子结点。下面的算法返回x所指结点的直接后继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。BiTreeINSUCC(BiTreex){s=X-rchild;if（s-rtag）while（s-ltag）s=s-rchild;returns；)五、算法设计题1．编写对二叉树进行中序遍历的非递归算法，并对算法执行题图6-6所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。栈已经定义：InitStack(S)（初始化）、Empty(S)（判栈空）、Push(S，p)（入栈）、Pop(S，p)（出栈）等操作。2．假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag（可取0...2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。3．一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。4．设中序线索树的结点由5个域组成。Info：给出结点的数据域。LT:标志域，为0或1。LL：当LT为1时，给出该结点的左孩子的地址。当LT为0时，给出按中序遍历的前驱结点地址。RT:标志域，为0或1。RL：当RT为1时，给出该结点的右孩子的地址。当RT为O时，给出按中序遍历的后继结点地址。请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点p按后序遍历次序的后继结点的地址q，设该中序线索二叉树的根结点地址为r。另外，请注意必须满足：(l)额外空间的使用只能为O(1)。(2)程序为非递归形式。5．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。6．给出中序线索树的结点结构，设计算法在不使用栈和递归的情况下前序遍历一棵中序线索树，并分析它的时间复杂度。7．以二叉链表为存储结构，写出交换各结点左右子树的算法。8．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。第六章树和二叉树第6章树和二叉树一、选择题（参考答案）1．B2．B3．C4．A，C5．C6．C7．A8．B9．A，B10.(1)C(2)A(3)C(4)A(5)C(6)A(7)C11．B12.A13．B14．A15．B16．D17．A18．C19．D20．D二、填空题（参考答案）1．树的总结点数-1。2．前驱：1，后继，任意多个。3.kl,k2,k4,k5,k7,2,k5,k6,kl,3,4。4.3，4，6，1，1，2，A，F，G。5.(1)ki-l,(2)