计算机专业基础综合数据结构树和二叉树历年真题试卷汇编7

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编7（总分：60.00，做题时间：90分钟）一、综合题（总题数：30，分数：60.00）.若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中（假设数组的第一个元素的下标为1）,下标分别为i和j的两个结点处在树中同一层的条件是°（iWjW1）【北京航空航天大学2006一、6（1分）】（分数：2.00）正确答案：（正确答案：[logi]=[logj]。编号为i的结点的高度是[logi]+1。）解析：.给定K（KN1）,对一棵含有IV个结点的K叉树（N>0）,请讨论其可能的最大高度和最小高度。【大连海事大学2001五（8分）】（分数：2.00）正确答案：（正确答案：N个结点的K叉树，最大高度N（只有一个叶结点的任意K叉树）。设最小高度为H,第i（1WiWH）层的结点数为Fk+1,则（Ki+1+1）/（K-1）H-1）/（K-1）,由此得H=[log（N（K-1））]+1。）k解析：.已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？【东北大学1999一、1（3分）】（分数：2.00）正确答案：（正确答案：结点个数在20到40的满二叉树且结点数是素数的数是31,该二叉树的叶子数是16。）解析：.一棵共有n个结点的树，其中所有分支结点的度均为K,求该树中叶子结点的个数。【东北大学2000一、3（4分）】（分数：2.00）正确答案：（正确答案：设分支结点和叶子结点数分别是为nk和n0,因此有n=P/n0+nk（1）另外从树的分支数B与结点的关系有n=B+1=K*nk+1（2）由（1）和（2）,有n0=n—nk=（n（K+1）+1）/Ko）解析：.已知在一棵含有n个结点的树中，只有度七的分支结点和度为0的叶子结点，求该树含有的叶子结点数。【大连理工大学2005二、2（20/4分）】【江苏大学2004三、5（6分）】（分数：2.00）正确答案：（正确答案：设分支结点和叶子结点数分别是为nk和n0,因此有n=P/n0+nk（1）另外从树的分支数B与结点的关系有n=B+1=K*nk+1（2）由（1）和（2）,有n0=n—nk=（n（K+1）+1）/K。）解析：.证明：一棵满k叉树上的叶子结点数加和非叶子结点数，m之间满足关系n0=（k-1）m+1。【北京交通大学2006四、1（5分）】（分数：2.00）正确答案：（正确答案：因为n=n0+m和n=B+1=km+1,其中B为分支数。故n0+m=km+1,所以n0=（k-1）m+1。）解析：.如在内存中存放一个完全二叉树，在树上只进行下面两个操作：（1）寻找某个结点双亲；（2）寻找某个结点的儿子。请问应该用何种结构来存储该二叉树？【东北大学2001一、3（3分）】（分数：2.00）正确答案：（正确答案：用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是［i/2］（i=时为根结点，无双亲），其左子女是2i（若2iWn,否则i无左子女），右子女是2i+1（若2i+Wn,否则无右子女）。）解析：.试求有n个叶结点的非满的完全二叉树的高度。【中科院计算所2000五（5分）】（分数：2.00）正确答案：（正确答案：设完全二叉树中叶子结点数为n,则根据完全二叉树的性质，度为2的结点数是n一1,而完全二叉树中，度为1的结点数至多为1,所以具有n个叶子结点的完全二叉树结点数是n+（n—1）+1=2n或2n—1（有或无度为1的结点）。由于具有2n（或2n—1）个结点的完全二叉树的深度是［log（2n）］+1（或［log（2n-1）］+1）,即［logn］+1,故n个叶结点的非满的完全二叉树的高度是［logn］+1（最2 2 2 2下层结点数＞=2）,或log2n+2（最下层只一个叶结点）。）解析：.已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少?【西安电子科技大学2000计算机应用一、4（5分）】（分数：2.00）正确答案：（正确答案：235。由于本题求二叉树的结点数最多是多少，第7层共有27-1=64个结点，已知有10个叶子，其余54个结点均为分支结点。它在第8层上有108个叶子结点。所以该二叉树的结点数最多可达27一1+108=235。（注意；本题并未明说完全二叉树的高度，但根据题意，只能8层。））解析：.已知一棵完全二叉树有892个结点，试求：（1）树的高度⑵叶结点个数⑶单支结点数（4）最后一个非终端结点的序号【中国海洋大学2006五（15分）】（分数：2.00）正确答案：（正确答案：（1）根据公式：［log892］+1,所以树的高度是10。（2）根据公式：n=n0+n1+n2=2n02一1+n1,所以叶结点数为446。（3）根据（2）,单支结点数为1。（4）最后一个非终端结点，即完全二叉树最后结点的双亲，序号是［892/2］=446。）解析：.求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【北京工业大学2000二、3（5分）】（分数：2.00）正确答案：（正确答案：根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是［n/2］,这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是［n/2］+1。）解析：.设二叉树T中有n个顶点，其编号为1,2,3,…，n,若编号满足如下性质：（1）T中任一顶点1,的编号等于左子树中最小编号减1;（2）对T中任一顶点v,其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。【山东大学1992一、1（3分）】（分数：2.00）正确答案：（正确答案：按前序遍历对顶点编号，即根结点从1开始，对前序遍历序列的结点从小到大编号。）解析：.已知一棵度为M的树中有n1个度为1的结点，n2个度为2结点，…，nm个度为m的结点，证明其叶结点个数为【中国海洋大学2004五（15分）】【山东大学1993一、2（4分）】【西安交通大学1996四、点个数为【中国海洋大学2004五（15分）】【山东大学1993一、2（4分）】【西安交通大学1996四、1（5分）】【东南大学1999一、4（8分）】（分数：2.00）正确答案：（正确答案：设树的结点数为n，分支数为B，则下面二式成立：n=n+n+n+…+n（1）n=B+1=n012m+2n+…-mn （2）由（1）和（2）得，叶子结点数I——）1 2 m解析：.若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，则该树一共有个结点。【北京航空航天大学2006一、5（1分）】（分数：2.00）正确答案：（正确答案：78。）解析：.有一非空树，其度为4,已知度为f的结点数有i个，其中1Wi<5,试问其叶结点个数是多少？【天津大学2005一、1（5分）】（分数：2.00）正确答案：（正确答案：21）解析：.已知二叉树有50个叶子结点，则二叉树的总结点数至少应为多少个?请给出计算过程。【中科院研究生院2004五（7分）】（分数：2.00）正确答案：（正确答案：99。由公式n=n0+n1+n2=n0+n1+n0—1=2n0+n1-1,当n1=0时，二又树的结点数最少。）解析：.下图给出了一个二叉树的顺序存储结构，其中空白表示结点不存在。请回答下列问题：（1）画出该二叉I审N匐树。（2）给出该二叉树的中序序列和后序序列。I 【北京理工大学2007三、3（6分）】（分数：2.00）正确答案：（正确答案：二叉树按完全二叉树存储，加了虚结点。二叉树略。中序序列：BADCFE,后序序列：BDFECAo）解析：.下列完全二叉树共有d层及n个结点，试在下图涂黑的结点（叶结点）上标上相应的序号（用d或n表示）o【浙江大学2004三（5分）】I——I（分数：2.00）正确答案：（正确答案：第一个结点是编号最小的叶子结点，编号为[n/2]+1；第二个结点是d-1层最后一个，编号为2d-1一1；第三个结点是d层第一个结点，编号为2d-1；第一个结点是d层最后一个结点，编号为no）解析：.一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点?有多少个度为1的结点?有多少个度为2的结点?如果完全二叉树有501个结点，结果如何?请写出推导过程。【东南大学2004一、1（5分）】（分数：2.00）正确答案：（正确答案：二叉树度为2的结点n2和度为0的结点n0间有关系式n2=n0-1，且完全二叉树中度为1的结点n1至多为1，由上述关系得知完全二叉树结点间的公式n=2n0+n1-1。故当n=500时，n0=250，n1=1，n2=249;n=501时，n0=251，n1=0，n2=250。）解析：.对于具有n个叶子结点，且所有非叶子结点都有左、右孩子的二叉树，（1）试问这种二叉树的结点总数是多少？（5分）（2）试证明I——。其中：lt表示第i个叶子结点所在的层号（设根结点所在层号为1）。（10分）【北方交通大学1995三（15分）】 ,（分数：2.00）正确答案：（正确答案：（1）根据二叉树度为2结点个数等于叶子结点个数减1的性质，故具有n个叶子结点且非叶子结点均有左右子树的二叉树的结点数是2n-1。（2）证明：当i=1时，2-（k-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶子结点的层号为t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两个新叶子结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。）解析：.假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？【北京邮电大学1996一、1（4分）】（分数：2.00）正确答案：（正确答案：结点数的最大值2h—1（满二叉树）；最小值2h-1（第一层根结点，其余每层均两个结点）。）解析：.一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标为"的结点的第f个孩子的下标以及结点下标为1,的结点的父母结点的下标。【北京邮电大学2001四、4（5分）】（分数：2.00）正确答案：（正确答案:（1）k（u-1）+1+i（2）［（v-2）/k+1）解析：.二叉树有n个顶点，编号为1,2,3,…，n,设：T中任一顶点V的编号等于左子树中最小编号减1；T中任一顶点V的右子树中最小编号等于其左子树中的最大编号加1。试描绘该二叉树。【东南大学1999一、2（7分）】（分数：2.00）正确答案：（正确答案：该二叉树是按前序遍历顺序编号，以根结点为编号1,前序遍历的顺序是“根一左一右”。）解析：.设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。（1）试利用归纳法证明E=I+2n,nN0。（5分）（2）利用（1）的结果，试说明：成功查找的平均比较次数s与不成功查找的平均比较次数u之间的关系可用公式表示s=（1+1/n）u-1,n>=1。【清华大学1998四（10分）】（分数：2.00）正确答案：（正确答案：（1）设n=1,则e+2*1=2（只有一个根结点时，有两个外部结点），公式成立。设有n个结点时，公式成立，即E°=1n+2n（1）现在要证明，当有n+1个结点时公式成立。增加一个内部

结点，设路径长度为1,则In+1=In+l（2）该内部结点，其实是从一个外部结点变来的，即这时相当于也增加了一个外部结点（原外部结点变成内部结点时，增加两个外部结点），则En+1=En+1+2（3）由（1）和（2），则（3）推导为En+1=In+2n+1+2=In+1—1+2n+1+2=In+1+2（n+1）故命题成立。"（2）成功查找的平均比较次数s=I/n不成功查找的平均比较次数u=（E,n）/（n+；）［（I+n）/n+1由以上二式，有s=（1+1/n）*u一1。）解析：.对于一个堆栈，若其入栈序列为1,2,3,…，n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入（固定为1,2,3,…，n）/输出序列对应一种二叉树形态的方法，并以入栈序列1,2,3（即n=3）为例加以说明。【浙江大学1998五、1（7分）】（分数：2.00）正确答案：（正确答案：由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若入栈序列为1,2,3,…，n,相当于前序遍历序列是1,2,3,…，n,出栈序列就是该前序遍历对应的二叉树的中序序列。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。下图以入栈序列1,2,3（解释为二叉树的前序序列）为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系:解析：.如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学1998二、2（5分）】（分数：2.00）正确答案：（正确答案：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左、右子树两部分。例如，任何结点只有左子树的一棵二叉树和任何结点只有右子树的一棵二叉树，其两棵树的前序序列相同，后序序列相同，但却是两棵不同的二叉树。）解析：.试证明：同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，对称序bac。【山东工业大学1997七（10分）】（分数：2.00）正确答案：（正确答案：前序遍历是“根一左一右”，中序遍历是“左一根一右”，后序遍历是“左一右一根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按先左后右顺序来遍历的，因此所有叶子都按相同的相对位置出现。）解析：.证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学2001二、3（5分）】（分数：2.00）正确答案：（正确答案：前序遍历是“根一左一右”，中序遍历是“左一根一右”，后序遍历是“左一右一根”。若将“根”去掉，三种遍历就剩“左一右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此三种遍历中叶子结点间的先后关系都是相同的。）解析：.现在按前序遍历二叉树的结果为abc,有哪几种不同的二叉树可以得到这一结果?画出这些二叉树。【北京理工大学2006六、3（50/7分）】.由二叉树的中序序列及前序序列能唯一地建立二叉树，试问中序序列及后序序列是否也能唯一地建立二叉树，不能，则说明理由，若能，对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。【南京理工大学