1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 10 及答案与解析一、综合题1 若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中(假设数组的第一个元素的下标为 1)，下标分别为 i 和 j 的两个结点处在树中同一层的条件是_。(ij1)【北京航空航天大学 2006 一、6(1 分)】2 给定 K(K1)，对一棵含有个结点的 K 叉树(N0)，请讨论其可能的最大高度和最小高度。【大连海事大学 2001 五(8 分)】3 已知一棵满二叉树的结点个数为 20 到 40 之间的素数，此二叉树的叶子结点有多少个?【东北大学 1999 一、 1(3 分) 】4 一棵共有 n
2、 个结点的树，其中所有分支结点的度均为 K，求该树中叶子结点的个数。【东北大学 2000 一、3(4 分)】5 已知在一棵含有 n 个结点的树中，只有度七的分支结点和度为 0 的叶子结点，求该树含有的叶子结点数。【大连理工大学 2005 二、2(204 分)】【江苏大学 2004三、5(6 分) 】6 证明：一棵满 k 叉树上的叶子结点数加和非叶子结点数，m 之间满足关系n0=(k-1)m+1。【北京交通大学 2006 四、1(5 分)】7 如在内存中存放一个完全二叉树，在树上只进行下面两个操作：(1)寻找某个结点双亲；(2)寻找某个结点的儿子。请问应该用何种结构来存储该二叉树?【东北大学 2
3、00l 一、3(3 分) 】8 试求有 n 个叶结点的非满的完全二叉树的高度。【中科院计算所 2000 五(5 分)】9 已知完全二叉树的第七层有 10 个叶子结点，则整个二叉树的结点数最多是多少?【西安电子科技大学 2000 计算机应用一、4(5 分)】10 已知一棵完全二叉树有 892 个结点，试求：(1)树的高度(2)叶结点个数(3)单支结点数(4)最后一个非终端结点的序号【中国海洋大学 2006 五(15 分)】11 求含有 n 个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【北京工业大学 2000 二、3(5 分)】12 设二叉树 T 中有 n
4、个顶点，其编号为 1，2，3 ，n，若编号满足如下性质：(1)T 中任一顶点 1，的编号等于左子树中最小编号减 1；(2)对 T 中任一顶点 v，其右子树中最小编号等于其左子树中的最大编号加 1。试说明对二叉树中顶点编号的规则(按何种顺序编号)。【山东大学 1992 一、1(3 分)】13 已知一棵度为 M 的树中有 n1 个度为 1 的结点， n2 个度为 2 结点，nm 个度为 m 的结点，证明其叶结点个数为 【 中国海洋大学 2004 五(15 分)】【山东大学 1993 一、2(4 分)】【西安交通大学 1996 四、1(5 分)】【东南大学1999 一、4(8 分) 】14 若一棵度
5、为 7 的树有 8 个度为 1 的结点，有 7 个度为 2 的结点，有 6 个度为 3的结点，有 5 个度为 4 的结点，有 4 个度为 5 的结点，有 3 个度为 6 的结点，有 2个度为 7 的结点，则该树一共有_个结点。【北京航空航天大学 2006 一、5(1 分)】15 有一非空树，其度为 4，已知度为 f 的结点数有 i 个，其中 1i=1。【清华大学 1998 四(10 分)】25 对于一个堆栈，若其入栈序列为 1，2，3，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n 的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为
6、 1，2，3，n)输出序列对应一种二叉树形态的方法，并以入栈序列 1，2，3(即 n=3)为例加以说明。【浙江大学 1998 五、1(7 分)】26 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学 1998 二、2(5 分) 】27 试证明：同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同)，例如前序abc，后序bca，对称序bac。【山东工业大学 1997 七(10 分)
7、】28 证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学 2001 二、3(5 分)】29 现在按前序遍历二叉树的结果为 abc，有哪几种不同的二叉树可以得到这一结果?画出这些二叉树。 【北京理工大学 2006 六、3(507 分)】30 由二叉树的中序序列及前序序列能唯一地建立二叉树，试问中序序列及后序序列是否也能唯一地建立二叉树，不能，则说明理由，若能，对中序序列 DBEAFGC和后序序列 DEBGFCA 构造二叉树。 【南京理工大学 1998 四(3 分)】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 10 答案与解析
8、一、综合题1 【正确答案】 logi=logj。编号为 i 的结点的高度是logi+1。2 【正确答案】 N 个结点的 K 叉树，最大高度 N(只有一个叶结点的任意 K 叉树)。设最小高度为 H，第 i(1iH)层的结点数为 Fk+1，则(K I+1+1)(K-1) H 一 1)(K-1)，由此得 H=logk(N(K-1)+1。3 【正确答案】 结点个数在 20 到 40 的满二叉树且结点数是素数的数是 31，该二叉树的叶子数是 16。4 【正确答案】 设分支结点和叶子结点数分别是为 nk 和 n0，因此有 n=Pn 0+nk (1) 另外从树的分支数 B 与结点的关系有 n=B+1=K*n
9、k+1 (2) 由(1)和(2)，有 n0=nnk=(n(K+1)+1)K。5 【正确答案】 设分支结点和叶子结点数分别是为 nk 和 n0，因此有 n=Pn 0+nk (1) 另外从树的分支数 B 与结点的关系有 n=B+1=K*nk+1 (2) 由(1)和(2)，有 n0=nnk=(n(K+1)+1)K。6 【正确答案】 因为 n=n0+m 和 n=B+1=km+1，其中 B 为分支数。故n0+m=km+1，所以 n0=(k-1)m+1。7 【正确答案】 用顺序存储结构存储 n 个结点的完全二叉树。编号为 i 的结点，其双亲编号是i2(i=时为根结点，无双亲 )，其左子女是 2i(若 2i
10、n，否则 i 无左子女)，右子女是 2i+1(若 2i+n，否则无右子女)。8 【正确答案】 设完全二叉树中叶子结点数为 n，则根据完全二叉树的性质，度为2 的结点数是 n 一 1，而完全二叉树中，度为 1 的结点数至多为 1，所以具有 n 个叶子结点的完全二叉树结点数是 n+(n1)+1=2n 或 2n1(有或无度为 1 的结点)。由于具有 2n(或 2n 一 1)个结点的完全二叉树的深度是log 2(2n)+1(或log 2(2n 一 1)+1)，即log 2n+1，故 n 个叶结点的非满的完全二叉树的高度是log 2n+1(最下层结点数=2)，或 log2n+2(最下层只一个叶结点)。9
11、 【正确答案】 235。由于本题求二叉树的结点数最多是多少，第 7 层共有 27-1=64个结点，已知有 10 个叶子，其余 54 个结点均为分支结点。它在第 8 层上有 1 08个叶子结点。所以该二叉树的结点数最多可达 27 一 1+108=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能 8 层。)10 【正确答案】 (1)根据公式：log 2892+1，所以树的高度是 10。 (2)根据公式：n=n0+n1+n2=2n0 一 1+n1，所以叶结点数为 446。 (3) 根据(2)，单支结点数为 1。 (4)最后一个非终端结点，即完全二叉树最后结点的双亲，序号是8922=44
12、6。11 【正确答案】 根据完全二叉树的性质，最后一个结点(编号为 n)的双亲结点的编号是n 2，这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是n2+1 。12 【正确答案】 按前序遍历对顶点编号，即根结点从 1 开始，对前序遍历序列的结点从小到大编号。13 【正确答案】 设树的结点数为 n，分支数为 B，则下面二式成立：n=n0+n1+n2+nm (1)n=B+1=n1+2n2+-mnm (2)由 (1)和(2)得，叶子结点数14 【正确答案】 78。15 【正确答案】 2116 【正确答案】 99。由公式 n=n0+n1+n2=n0+n1+n0 一 1=2n0
13、+n1-1，当 n1=0 时，二又树的结点数最少。17 【正确答案】 二叉树按完全二叉树存储，加了虚结点。二叉树略。中序序列：BADCFE，后序序列：BDFECA。18 【正确答案】 第一个结点是编号最小的叶子结点，编号为n2+1；第二个结点是 d-1 层最后一个，编号为 2d-1 一 1；第三个结点是 d 层第一个结点，编号为 2d-1；第一个结点是 d 层最后一个结点，编号为 n。19 【正确答案】 二叉树度为 2 的结点 n2 和度为 0 的结点 n0 间有关系式 n2=n0-1，且完全二叉树中度为 1 的结点 n1 至多为 1，由上述关系得知完全二叉树结点间的公式 n=2n0+n1-1
14、。故当 n=500 时，n0=250，n1=1，n2=249;n=501 时，n0=251，n1=0，n2=250。20 【正确答案】 (1)根据二叉树度为 2 结点个数等于叶子结点个数减 1 的性质，故具有 n 个叶子结点且非叶子结点均有左右子树的二叉树的结点数是 2n-1。(2)证明：当 i=1 时，2 -（k-1） =20=1，公式成立。设当 i=n-1 时公式成立，证明当 i=n 时公式仍成立。设某叶子结点的层号为 t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是 t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两个新叶子结点，反映到公式中，因为
15、 2-(t-1)=2-(t+1-1)+2-(t+1-1)，所以结果不变，这就证明当 i=n 时公式仍成立。证毕。21 【正确答案】 结点数的最大值 2h1(满二叉树)；最小值 2h-1(第一层根结点，其余每层均两个结点)。22 【正确答案】 (1)k(u 一 1)+1+i (2)(v2) k+123 【正确答案】 该二叉树是按前序遍历顺序编号，以根结点为编号 1，前序遍历的顺序是“根一左一右 ”。24 【正确答案】 (1)设 n=1，则 e+2*1=2(只有一个根结点时，有两个外部结点)，公式成立。 设有 n 个结点时，公式成立，即 E n=In+2n (1) 现在要证明，当有 n+1 个结点
16、时公式成立。 增加一个内部结点，设路径长度为 l，则 I n+1=In+l (2) 该内部结点，其实是从一个外部结点变来的，即这时相当于也增加了一个外部结点(原外部结点变成内部结点时，增加两个外部结点)，则 E n+1=En+1+2 (3) 由(1) 和(2)，则(3)推导为 E n+1=In+2n+1+2=In+1 1+2n+1+2 =In+1+2(n+1) 故命题成立。 (2)成功查找的平均比较次数 s=In 不成功查找的平均比较次数 u=(E，n) (n+1)=(I+n) n+1 由以上二式，有 s=(1+1n)*u 一 1。25 【正确答案】 由于二叉树前序遍历序列和中序遍历序列可唯一
17、确定一棵二叉树，因此，若入栈序列为 1，2，3，n，相当于前序遍历序列是 1，2，3，n，出栈序列就是该前序遍历对应的二叉树的中序序列。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。下图以入栈序列 1，2，3(解释为二叉树的前序序列)为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系：26 【正确答案】 给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设 l 个元素) 表示左子树，若左边无元素，则说明左子树为空；右边(
18、设 r 个元素)是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二元素开始的 l 个结点序列和中序序列根左边的 l 个结点序列构造左子树，由前序序列最后 r 个元素序列与中序序列根右边的 r 个元素序列构造右子树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左、右子树两部分。例如，任何结点只有左子树的一棵二叉树和任何结点只有右子树的一棵二叉树，其两棵树的前序序列相同，后序序列相同，但却是两棵不同的二叉树。27 【正确答案】 前序遍历是“根一左一右” ，中序遍历是 “左一根一右”，后序遍历是“左一右一根 ”。三种遍历中只是访问 “根”结点的时
19、机不同，对左右子树均是按先左后右顺序来遍历的，因此所有叶子都按相同的相对位置出现。28 【正确答案】 前序遍历是“根一左一右” ，中序遍历是 “左一根一右”，后序遍历是“左一右一根 ”。若将“根”去掉，三种遍历就剩“左一右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此三种遍历中叶子结点间的先后关系都是相同的。29 【正确答案】 5 种。30 【正确答案】 在已经说明由二叉树的前序序列和中序序列可以唯一确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当 n=1 时，只有一个根结点，由中序序列和后序序列可以
20、确定这棵二叉树。设当n=m 一 1 时结论成立，现证明当 n=m 时结论成立。设中序序列为S1，S2，Sm，后序序列是 P1，P2，Pm 。因后序序列最后一个元素 Pm 是根，则在中序序列中可找到与 Pm 相等的结点(设二叉树中各结点互不相同)Si(1im)，因中序序列是由中序遍历而得，Si 是根结点， S1，S2，Si 一 1 是左子树的中序序列，而 Si+1，Si+2 ，Sm 是右子树的中序序列。若 i=1，则 S1是根，这时二叉树的左子树为空，右子树的结点数是 m 一 1，则S2，S3，Sm和P1，P2，Pm 一 1)可以唯一确定右子树，从而也确定了二叉树。若 i=m，则 Sm 是根，这时二叉树的右子树为空，左子树的结点数是 m一 1，则S1，S2，Sm 一 1)和 P1，P2 ， Pm 一 1)唯一确定左子树，从而也确定了二叉树。最后，当 1im 时，Si 把中序序列分成S1，S2，Si-1)和Si+1，Si+2 ，Sm 。由于后序遍历是“左子树一右子树一根结点” ，所以P1，P2，Pi-1和Pi，Pi+1，Pm 一 1)是二叉树的左子树和右子树的后序遍历序列。因而由S1，S2，Si 一 1和P1 ，P2，Pi 一 1可唯一确定二叉树的左子树，由Si+1，Si+2，Sm)和Pi，Pi+1，Pm 一 1)可唯一确定二叉树的右子树。
