1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 8 及答案与解析一、填空题1 设一棵完全二叉树叶子结点数为 k，最后一层结点数2，则该二叉树的高度为_。【北京科技大学 1998 一、3】2 已知完全二叉树的第 7 层有 10 个叶子结点，则整个二叉树的结点数最多是_。【东南大学 2005 数据结构部分二、7(1 分)】3 将一棵有 100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为 0，则编号为 50 的结点的右孩子编号为_。【中南大学 2005 二、l(2 分)】4 高度为 i(i1)的完全二叉树最多有_个结点；最少有_个结点；若按自上而下，
2、从左到右的次序给结点编号(从 1 开始)，则编号最小的叶子结点的编号为_。【大连理工大学 2005 一、2(3 分)】【江苏大学 2006 二、3(2分)】5 对于一个具有 n 个结点的二叉树，当它为一棵(1)二叉树时具有最小高度，当它为一棵(2)时，具有最大高度。【哈尔滨工业大学 2001 一、3(2 分)】6 n(n 大于 1)个结点的各棵树中，其深度最小的那棵树的深度是(1)。它共有(2)个叶子结点和(39) 个非叶子结点，其中深度最大的那棵树的深度是(4) ，它共有(5)个叶子结点和(6)个非叶子结点。【山东大学 2001 三、7(2 分)】7 在树的孩子兄弟表示法中，二叉链表的左指针
3、指向_，右指针指向_。【北京理工大学 2006 十、3(1 分)】8 设 F 是由 T1、T2、T3 三棵树组成的森林，与 F 对应的二叉树为 B，已知T1、T2、T3 的结点数分别为 n1、n2 和，n3，则二叉树 B 的左子树中有 (1)个结点，右子树中有 (2)个结点。【南京理工大学 2000 二、9(3 分)】9 先序遍历森林时，首先访问森林中第一棵树的_。【中山大学 2005】10 设森林 F 对应的二元树为 B，它有 m 个结点，B 的根为 P，P 的右子树结点个数为 n，则森林，中第一棵树的结点个数是_。【哈尔滨工业大学 2005一、8(1 分) 】11 一个深度为七的，具有最少
4、结点数的完全二叉树按层次，(同层次从左到右)用自然数依此对结点编号，则编号最小的叶子的序号是(1)；编号是 f 的结点所在的层次号是(2)(根所在的层次号规定为 1 层) 。【南京理工大学 2001 二、2(2 分)】12 将一棵结点编号(从上到下，从左至右)为 1 到 7 的满二叉树转变成森林，则中序遍历该森林得到的序列为_。【北京工业大学 2005 二、5(3 分)】13 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是 BEFCGDH，对称序列是 FEBGCHD，则它的后序序列是 (1)。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是(2)。【山东工业大学
5、1997 二(6 分)】14 前序遍历树林正好等同于按(1)遍历对应的二叉树，后序遍历树林正好等同于按(2)遍历对应的二又树。【山东工业大学 1999 二、1(4 分)】15 二叉树的先序序列和中序序列相同的条件是_。【合肥工业大学 2000三、7(2 分) 】16 已知一棵二叉树的前序序列为 abdecfhg，中序序列为 dbeahfcg，则该二叉树的根为(1)，左子树中有 (2)，右子树中有 (3)。【南京理工大学 1996 二、1(6 分)】17 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用“”表示，现前序遍历二叉树，访问的结点的序列为 ABDGCEHF，则中序
6、遍历二叉树时，访问的结点序列为(1)；后序遍历二叉树时，访问的结点序列为(2)。【南京理工大学 1999 二、3(4 分) 】18 设某二叉树的先序遍历序列为 abcdefgh，中序遍历序列为 dgbaechf,，则其后序遍历序列为_。【北京交通大学 2006 二、5(2 分)】19 某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，前序遍历序列是_。【中科院研究生院 2005 二、6(1 分)】【东南大学 2005 数据结构部分二、6(1 分) 】20 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是_
7、。【中国人民大学 2001 一、4(2 分)】21 一棵左子树为空的二又树在先序线索化后，其中的空链域的个数为_。【厦门大学 2002 六、1(4 分)】22 设一棵后序线索树的高是 50，结点 x 是树中的一个结点，其双亲是结点 y，y的右子树高度是 3l，x 是 y 的左孩子。则确定 x 的后继最多需经过 _中间结点(不含后继及 x 本身) 。【南京理工大学 2000 二、8(15 分)】二、综合题23 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001 软件二、1(5 分) 】24 请分析线性表
8、、树、广义表的主要结构特点，以及相互的差异与关联。【大连海事大学 2001 三(10 分) 】25 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?【中国人民大学 2001 二、3(4 分) 】26 将算术表达式(a+b)+c *(d+e)+f)*(g+h)转化为二叉树。 【天津大学 2003 一、3(8分)】【 东南大学 2003 二(7 分)】【东北大学 2000 三、1(4 分)】27 试分别画出表示下列两个表达式的二叉树。【华中科技大学 2006 三、1(6 分)】(1)a 一 b+c (2)a+(b 一 c)de*f28 已知树的广义表表示如下 T=(A(B(E(K,L
9、)，C(G)，D(H(M),I,J)，画出该广义表所对应的树。【天津大学 2006 二(10 分)】29 一棵二叉树中的结点的度或为 0 或为 2，则二叉树的枝数为 2(n0 一 1)，其中 n0是度为 0 的结点的个数。【南京理工大学 1998 六(3 分)】29 一棵高度为 h 的满 k 叉树有如下性质：根结点所在层次为 0；第 h 层上的结点都是叶子结点；其余各层上每个结点都有 k 棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问：30 各层的结点个数是多少?(3 分)31 编号为 l 的结点的双亲结点(若存在)的编号是多少?(3 分)32 编号为
10、 i 的结点的第 m 个孩子结点(若存在)的编号是多少?(3 分)33 编号为 i 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?(3 分)【清华大学 1999 八(12 分) 】【西北工业大学 1999 五(10 分)】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 8 答案与解析一、填空题1 【正确答案】 log 2k+12 【正确答案】 235。参见上面一、2 的分析。3 【正确答案】 102。假定编号为 i 的结点的左右孩子存在，左孩子的编号是2*i+1，右孩子的编号是 2*i+2。4 【正确答案】 (1)2 t-1 (2)2i-1 (3)n2+1(设 n 是完全二叉
11、树的结点数)5 【正确答案】 (1)完全 (2) 只有一个叶子结点的二叉树6 【正确答案】 (1)2 (2)n 一 1 (3)1 (4)n (5)1 (6)n 一 17 【正确答案】 (1)结点的第一个孩子 (2) 结点的右兄弟8 【正确答案】 (1)n1 1 (2)n2+n39 【正确答案】 根结点10 【正确答案】 m 一 n11 【正确答案】 (1)2 k2 +1(第 k 层 1 个结点，总结点个数是 2k-1，其双亲是 2k-12=2 k-2)(2)log2i+1 本题 (1)也可以这样分析：深度为 k 且具有最少结点数的完全二叉树，第 k 层只有一个结点，第 k-1 层是满的，最左边
12、的结点度为 1，其右兄弟就是编号最小的叶子结点。而第 k-2 层最右边结点的编号是 2k-21。所以，最小叶子结点的编号是(2 k-2 一 1)12 【正确答案】 4，2，5，1，6，3，7。说明：题中“中序遍历该森林” 多数教材使用“后序遍历该森林 ”。13 【正确答案】 (1)FEGHDCB (2)BEF(该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF)14 【正确答案】 (1)前序 (2) 中序15 【正确答案】 任何结点至多只有右子女的二叉树16 【正确答案】 (1)a (2)dbe (3)hfcg17 【正确答案】 (1).D.G.B.A.E.H.C.F (2)GD.B
13、HEFCA18 【正确答案】 gdbehfca19 【正确答案】 cedba20 【正确答案】 双亲的右子树中最左下的叶子结点21 【正确答案】 222 【正确答案】 31(x 的后继是经 x 的双亲 y 的右子树中最左下的叶结点)二、综合题23 【正确答案】 树的孩子兄弟链表表示法和二叉树二叉链表表示法本质上是一样的，只是解释不同，也就是说，树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林的问题。树和二又树均属于树形结构，其区别有三：一是二叉树的度至多为 2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须
14、指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空(一些教材上考虑到与二叉树的转换，允许树为空)。二叉树不是树的特例。24 【正确答案】 线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个 “最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲(根无双亲)，从这个意义上说，存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均
15、属非线性结构。但在以下意义上，又蜕变为线性结构：度为 1 的树，以及广义表中的元素都是原子时。另外，广义表中同层(最高层是用逗号分隔的)元素之间的关系可看成前驱和后继，也符合线性表中元素间的逻辑关系，但这时元素有原子，也有子表，即元素并不属于同一数据对象。25 【正确答案】 方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，即后缀表达式，可对其求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+、一、*、等)进行最后求值。26 【正确答案】 该算术表达式转化的二叉树如右图所示。27 【正确答案】 人们日常使用的表达式是中缀表达式，由
16、于存在括号和运算符的优先级，直接转换成表达式二叉树比较困难。最好的办法是先将中缀表达式转换成后缀表达式，转换规则已在第 3 章的应用题部分的第 21 题做了介绍，读者可参照。由后缀表达式转换成表达式二叉树的规则如下。从左到右读入后缀表达式，遇操作数就入栈，遇操作符就将该操作符做当前的根结点，并从栈内弹出两个操作数，后弹出的是第一操作数(被乘除加减数)做左子树，先弹出的做右子树，之后将该根结点入栈。继续读后缀表达式，如上处理，直至表达式结束。限于篇幅，表达式的二又树不再画出。28 【正确答案】 树的广义表表示法的特点如下：树是一个广义表，若括号内无元素，则为空树；若广义表是非空表，则表内第一个元
17、素是树的根。第一个元素后是表，若表内为空，则无子树；否则高层以逗号分隔的是互为兄弟的子树。对每棵子树，进行如上分解，最后得到广义表对应的子树。29 【正确答案】 证明：设二叉树度为 0 和 2 的结点数及总的结点数分别为 n0、n2和 n，则n=n0+n2 (1)再设二叉树的分支数为 B，除根结点外，每个结点都有一个分支所指，则n=B 一 1 (2)度为 0 的结点是叶子，没有分支，而度为 2 的结点有两个分支，因此(2)式可写为n=2*n2+1 (3)由(1)、(3)得 n2=n0-1，代入(1)，并由(1) 和(2)得 B=2*(n0 一 1)。证毕。30 【正确答案】 (1)k l(l
18、为层数，按题意，根结点为 0 层)31 【正确答案】 因为该树每层上均有 kl 个结点，从根开始编号为 1，则结点 i 的从右向左数第 2 个孩子的结点编号为 ki。设 n 为结点 i 的子女，则关系式(i-1)k+2nik+1成立，因 i 是整数，故结点 i 的双亲的编号为 (i 一 2)k/+1。32 【正确答案】 结点 i(i1)的前一结点编号为 i-1(其最右边子女编号是(i-1)*k+1)，故结点 i 的第 m 个孩子的编号是(i 一 1)*k1+m。33 【正确答案】 根据以上分析，结点 i 有右兄弟的条件是，它不是双亲的从右数的第一子女，即(i 一 1) k!=0，其右兄弟编号是 i+1。
