树和二叉树习题及答案

一、填空题1.不相交的树的聚集称之为森林。2.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。3.深度为k的完全二叉树至少有2k-1个结点。至多有2k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2k-2+1。4.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=n2+1。5.一棵二叉树的第i（i≥1）层最多有2i-1个结点；一棵有n（n0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。7.哈夫曼树是带权路径最小的二叉树。8.前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。9.以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是165。10.树被定义为连通而不具有回路的（无向）图。11.若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。12.高度为k，且有个结点的二叉树称为二叉树。2k-1满13.带权路径长度最小的二叉树称为最优二叉树，它又被称为树。Huffman14.在一棵根树中，树根是为零的结点，而为零的结点是结点。入度出度树叶15.Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。结点树根16.满二叉树是指高度为k，且有个结点的二叉树。二叉树的每一层i上，最多有个结点。2k-12i-1二、单选题1.具有10个叶结点的二叉树中有(B)个度为2的结点。(A)8(B)9(C)10(D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。（1）先序（2）中序（3）后序（4）从根开始按层遍历3.由2、3、4、7作为结点权值构造的树的加权路径长度B。A、33B、30C、36D、404.高度为6的满二叉树，总共有的结点数是B。A、15B、63C、20D、255.下面描述根树转换成二叉树的特性中，正确的是C。A、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子。B、根树转换成的二叉树是不唯一的，二叉树的根结点只有左孩子。C、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。D、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子。6.如图所示的4棵二叉树中，不是完全二叉树的是。A、○B、○○○○○○○○○○○C、○D、○○○○○○○○○C7.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是D。A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca8.已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，按先序遍历所得到的结点序列为ABCDGEIHFJK。9.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是C。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙10.二叉树第i层结点的结点个数最多是（设根的层数为1）：AA）2i-1B）2i-1C）2iD）2i-111.树的后根遍历序列等同于该树对应的二叉树的：BA）先序序列B）中序序列C）后序序列12.树最适合用来表示_C___。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据13.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。A.正确B.错误14.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为B个。A．15B．16C．17D．4715.按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。A.3B.4C.5D.616.深度为5的二叉树至多有__C__个结点。A.16B.32C.31D.1017.对一个满二叉树，m个树叶，n个结点，深度为h，则__D__。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-118.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A___。A.不发生改变B.发生改变C.不能确定D.以上都不对19.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__C__。A.uwvtsB.vwutsC.wuvtsD.wutsv20.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。A.正确B.错误21.在一非空二叉树的中序遍历序列中，根结点的右边_A___。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点22.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是__D__。A.acbedB.decabC.deabcD.cedba23.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_C___存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构24.在线索化二叉树中，t所指结点没有左子树的充要条件是_B___。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不对25.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B___。A.正确B.错误26.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论__A__是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对6.42统统计计二二叉叉树树中中叶叶子子结结点点的的个个数数（（先先序序遍遍历历））typedefstructBiTnode{ElemTypedata;BiTnode*rchild；*lchild;}BiTnode,*BiTree;VVooiiddCCoouunnttLLeeaaff（（BBiiTTrreeeeTT，，iinntt&&ccoouunntt））{{iiff（（TT））{{iiff（（（（！！TT-Lchild）&&&&（（！！TT-Rchild）)Count++；//计数器加1CountLeaf（TT-Lchild，count）；CountLeaf（TT-Rchild，count）；}}.43交换所有结点的左右子树typedefstructBiTnode{ElemTypedata;BiTnode*rchild；*lchild;}BiTnode,*BiTree;voidBitree_Revolute(BitreeT){if(T)T-lchild-T-rchild;//交换左右子树if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);//左右子树再分别交换各自的左右子树}//Bitree_Revolute6-1列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为1；结点②、③的层次为2；结点④、⑤、⑥的层次为3；结点⑦、⑧的层次为4；结点⑨的层次为5。6-2使用(1)顺序表示和(2)二叉链表表示法，分别画出右图所示二叉树的存储表示。①②③④⑤⑥⑦⑨⑧∧∧∧∧∧∧∧∧∧∧0123456789101112131415161718①②③④⑤⑥⑦⑧⑨顺序表示二叉链表表示6-3请画出右图所示的树所对应的二叉树。【解答】6-4已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。【解答】当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：6-5给定权值集合{15,03,14,02,06,09,16,17},构造相应的霍夫曼树,并计算它的带权外部路径长度。【解答】此树的带权路径长度WPL=229。1对应二叉树122334455667788EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHI1503140206091617F：02031514060916170502031514060916170511(Ⅰ)(Ⅱ)(Ⅲ)0203151409161705110620(Ⅳ)02031415091617051106202902031415091617051106202933(Ⅴ)0203141509051106202916173349(Ⅵ)020315090511062029161733491482(Ⅶ)6-6假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数。【解答】已知字母集{c1,c2,c3,c4,c5,c6,c7,c8}，频率{5,25,3,6,10,11,36,4}，则Huffman编码为c1c2c3c4c5c6c7c801101000000111001010110001电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=25710061393625221771011114365C3C8C5C6C1C4C2C700000001111111