文档介绍：第6章树和二叉树自测卷解答一、下面是有关二叉树的叙述,请判断正误(每小题1分,共10分)(√),则在n个结点的二叉树链表中只有n—1个非空指针域。(×)。(√)。(×)。(×)-1-1,其中k是树的深度。(应2i-1)(×),如果不存在非空左子树,则不存在非空右子树。(×),它的根结点作为第一层,则它的第i层上最多能有2i—1个结点。(应2i-1)(√)(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。(正确。用二叉链表存储包含n个结点的二叉树,结点共有2n个链域。由于二叉树中,除根结点外,每一个结点有且仅有一个双亲,所以只有n-1个结点的链域存放指向非空子女结点的指针,还有n+1个空指针。)即有后继链接的指针仅n-1个。(√)。最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5二、填空(每空1分,共15分)。+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子。注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。,它的深度为9。(注:用ëlog2(n)û+1=ëû+1=9设一棵完全二叉树有700个结点,则共有350个叶子结点。答:最快方法:用叶子数=[n/2]=,则此完全二叉树有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有0个结点只有非空右子树。答:最快方法:用叶子数=[n/2]=500,n2=n0-1=499。另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=.【③】一棵含有n个结点的k叉树,可能达到的最大深度为n,最小深度为2。答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层),但不包括n=0或1时的特例情况。:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按NLR次序),后序法(即按LRN次序)和中序法(也称对称序法,即按LNR次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是FEGHDCB。解:先由已知条件画图,再后序遍历得到结果;(n)。答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。{3,2,4,5,1}构造的哈夫曼(Huffman)树的带权路径长度是33。解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33(15)(9)(6)(注:两个合并值先后不同会导