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