第六章树和二叉树一、选择题1.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④2．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定3．具有10个叶结点的二叉树中有（）个度为2的结点。A．8B．9C．10D．ll4.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为25．二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-16.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间7．一棵具有n个结点的完全二叉树的树高度（深度）是（）A．nlog2nB．log2nC．log2n|+1D．不确定8．深度为h的满m叉树的第k层有（）个结点。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-19．在一棵高度为k的满二叉树中，结点总数为（）A．2k-1B．2kC．2k-1D．log2k+110．高度为K的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-1-111.一棵树高为K的完全二叉树至少有（）个结点。A．2k–1B.2k-1–1C.2k-1D.2k12.利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空13．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历14．树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列15．在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法16．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG17．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定18．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba19.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对20．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：（）A、EB、FC、GD、H21．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树22.引入二叉线索树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一23．下述编码中哪一个不是前缀码（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）24．下面几个符号串编码集合中，不是前缀编码的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}二、判断题1.二叉树是度为2的有序树。2.完全二叉树一定存在度为1的结点。3.对于有N个结点的二叉树，其高度为log2n。4．深度为K的二叉树中结点总数≤2k-1。5.二叉树的遍历结果不是唯一的.6．由一棵二叉树的前序序列和后序序列可以唯一确定它。7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。8.二叉树只能用二叉链表表示。9.给定一棵树，可以找到唯一的一棵二叉树与之对应。10．树形结构中元素之间存在一个对多个的关系。11．在二叉树的第i层上至少有2i-1个结点(i>=1)。12．将一棵树转成二叉树，根结点没有左子树。三、填空题1．二叉树由_