第4课树和二叉树

第四课树和二叉树一、选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE参考答案：D2．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A．250B．500C．254D．505E．以上答案都不对参考答案：E3．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为（）。A．5B．6C．7D．8参考答案：D4．在下述结论中，正确的是（）。①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④参考答案：D5．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）。A．m-nB．m-n-1C．n+1D．条件不足，无法确定参考答案：A6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A．9B．11C．15D．不确定参考答案：B7．具有10个叶结点的二叉树中有（）个度为2的结点。A．8B．9C．10D．11参考答案：B8．下述编码中不是前缀码的是（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）参考答案：B9．设给定权值总数有n个，其哈夫曼二叉树的结点总数为（）。A．不确定B．2nC．2n+1D．2n-1参考答案：D10．有关二叉树下列说法正确的是（）。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2参考答案：B11．二叉树的第i层上最多含有结点数为（）。A．2iB．2i-1-1C．2i-1D．2i-1参考答案：C12．一个具有1025个结点的二叉树的高h为（）。A．11B．10C．11至1025之间D．10至1024之间参考答案：C13．对于有n个结点的二叉树，其高度为（）。A．nlog2nB．log2nC．log2n+1D．不确定参考答案：D14．一棵具有n个结点的完全二叉树的树高度（深度）是（）。A．logn+1B．logn+1C．lognD．logn-1参考答案：A15．在一棵高度为k的满二叉树中，结点总数为（）。A．2k-1B．2kC．2k-1D．log2k+1参考答案：C16．高度为k的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-1-1参考答案：C17．一棵树高为k的完全二叉树至少有（）个结点。A．2k–1B．2k-1–1C．2k-1D．2k参考答案：C18．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）。A．4B．5C．6D．7参考答案：C19．利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空参考答案：C20．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。A．先序B．中序C．后序D．从根开始按层次遍历参考答案：C21．树的后根遍历序列等同于该树对应的二叉树的（）。A．先序序列B．中序序列C．后序序列参考答案：B22．下述二叉树中，（）满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序。A．二叉排序树B．哈夫曼树C．AVL树D．堆参考答案：D23．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG参考答案：B24．已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定参考答案：A25．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A．先序B．中序C．后序D．层序参考答案：B26．若二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（）。A．EB．FC．GD．H参考答案：C27．将一棵树T转换为孩子兄弟链表表示的二叉树H，则T的后序遍历序列与H的（）序列相同。A．前序遍历B．中序遍历C．后序遍历参考答案：B28．下面的说法中正确的是（）。(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；(2)按二叉树定义，具有三个结点的二叉树共有6种。A．(1)(2)B．(1)C．(2)D．(1)、(2)都错参考答案：B29．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树参考答案：C30．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同参考答案：B31．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树参考答案：C32．由3个结点可以构造出（）种不同的二叉树。A．2B．3C．4D．5参考答案：D33．一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：（）。A．不确定B．0C．1D．2参考答案：D34．一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：（）。A．0B．1C．2D．不确定参考答案：C35．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。A．X的双亲B．X的右子树中最左的结点C．X的左子树中最右结点D．X的左子树中最右叶结点参考答案：C36．引入二叉线索树的目的是（）。A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一参考答案：A37．线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性参考答案：C38．n个结点的线索二叉树上含有的线索数为（）。A．2nB．n-1C．n+1D．n参考答案：C39．（）的遍历仍需要栈的支持。A．前序线索树B．中序线索树C．后序线索树参考答案：C40．二叉树在线索后，仍不能有效求解的问题是（）。A．先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继参考答案：D41．由3个结点可以构造出（）种不同的有序树。A．2B．3C．4D．5参考答案：A二、应用题1．设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？++*+fhg*+abc+de参考答案：方法有二。一是对该算术表达式（二叉树）进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、-、*、/等）进行最后求值。2．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。参考答案：3．一棵有n(n0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域?为什么?参考答案：n（n0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。4．试证明一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。参考答案：设二叉树度为0和2的结点数及总的结点数分别为n0，n2和n，则n=n0+n2(1)再设二叉树的分支数为B，除根结点外，每个结点都有一个分支所指，则n=B+1(2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此(2)式可写为n=2*n2+1(3)由(1)、(3)得n2=n0-1，代入(1)，并由(1)和(2)得B=2*(n0-1)。5．证明任一结点个数为n的二叉树的高度至少为O(log2n)。参考答案：最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1n=2h-1关系式。解此不等式，并考虑h是整数，则有h=log2n+1，即任一结点个数为n的二叉树的高度至少为O(log2n)。6．有n个结点并且其高度为n的二叉树的数目是多少?参考答案：2n-17．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？参考答案：235。8．高度为10的二叉树，其结点最多可能为多少？参考答案：1023。9．已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？参考答案：根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是i/2，故A[i]和A[j]的最近公共祖先可如下求出：while(i/2!=j/2)if(ij)i=i/2;elsej=j/2;退出while后，若i/2=0，则最近公共祖先为根结点，否则最近公共祖先是i/2。10．给定K(K=1)，对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度。参考答案：N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，第i(1=i=H)层的结点数Ki-1，则N=1+k+k2+…+kH-1，由此得H=logK(N(K-1)+1)11．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？参考答案：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。12．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。参考答案：设分支结点和叶子结点数分别是为nk和n0，因此有n=n0+nk(1)另外从树的分枝数B与结点的关系有n=B+1=K*nk+1(2)由(1)和(2)有n0=n-nk=(n(K-1)+1)/K。13．若一棵完全二叉树中叶子结点的个数为n，且最底层结点数≧2，求其深度。参考答案：log2n+1。14．已知完全二叉树有30个结点，则其中度为0的结点有多少个？参考答案：15。15．试证明，在具有n(n=1)个结点的m次树中，有n(m-1)+1个指针是空的。参考答案：n个结点的m次树，共有n*m个指针。除根结点外，其余n-1个结点均有指针所指，故空指针数为n*m-(n-1)=n*(m-1)+1。16．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？参考答案：结点数的最大值2h-1（满二叉树），最小值2h-1（第一层根结点，其余每层均两个结点）。17．试证明同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc后序bca中序bac。参考答案：前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。18．试找出满足下列条件的二叉树：(1)先序序列与后序序列相同；(2)中序序列与后序序列相同；(3)先序序列与中序序列相同；(4)中序序列与层序序列相同。参考答案：BACEDFNPGHJMOLIK(1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树；(2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树；(3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树；(4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至