1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 4及答案解析(总分：74.00，做题时间：90 分钟)一、综合题(总题数：35，分数：74.00)1.(1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同 2)中序序列与后序序列相同 3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG 和 DEBHIFGCA，画出这棵二叉树。【东北大学 1999 六(4 分)】【东南大学 2000 一、4(6 分)】（分数：2.00）_2.分别给出满足下列条件的二叉树。(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不
2、相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。【四川大学 2004】【烟台大学 2007 四、2(8 分)】（分数：2.00）_3.将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。 （分数：2.00）_4.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H 中序遍历序列：B FDAG E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。【南京航空航天大学 1997 二(10 分)】（分数：2.00）_5.已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJF
3、K 后序：LGHDIEBJKFCA(1)(2 分)给出这棵二叉树；(2)(2 分)转换为对应的森林；(3)(4 分)画出该森林的带右链的先根次序表示法；（分数：2.00）_6.设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有 4 个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由 a，b，c，d 排列构成的字符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有 4 个结点二叉树的全部形态及
4、相应的中序遍历序列。【浙江大学 1997 六(15 分)】（分数：2.00）_7.假设一棵二叉树的前序序列为 ABCD，它的中序序列可能是 DABC 吗?【石油大学 1998 一、1(5 分)】（分数：2.00）_8.已知一棵二叉树的后序遍历序列为 EICBGAHDF，同时知道该二叉树的中序遍历序列为 CEIFGBADH，试画出该二叉树。【重庆大学 2000 二、2】（分数：2.00）_9.已知一棵二叉树 T 的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。 【吉林大学 2007 二、3(3 分)】（分数：2.00）_1
5、0.在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么?【上海交通大学 2003 五(10 分)】（分数：2.00）_11.在二叉树上进行前序遍历时，结点 A 在结点 B 之前，而在进行后序遍历时，结点 A 在结点 B 之后，那么结点 A 是结点 B 的祖先，对吗?为什么?【上海交通大学 2003 六(10 分)】（分数：2.00）_12.某二叉树的后序遍历序列为：，A，E，C D，B，其中 表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树?如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学
6、 2007 三、23(8 分)】（分数：2.00）_13.输入带空二叉树信息(O)的前序遍历序列：A，G，B，C，D，E，E ，E ， 建立一棵二又树，其中 表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学 2006三、1(6 分)】（分数：2.00）_14.已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列为(即后根次序)：A、C、B、E、D、X、，、H、F、K、，。请给出该二叉树的中序序列(即中根次序)。【上海交通大学 2001二(8 分)】（分数：2.00）_15.假
7、设一棵二叉树的层次序列为 ABCDEFGHIJ，中序序列 DBGEHJACIF。请画出这棵二叉树。【武汉大学2000 三、1】【东南大学 2000 一、1(6 分)】【大连理工大学 2005 二、3(204 分)】【中国海洋大学2007 一、5(8 分)】（分数：2.00）_16.已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK【合肥工业大学 2000 四、1(5 分)】（分数：2.00）_17.画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为 ABCDE。(2)高度为 5其对应的树
8、(森林)的高度最大为 4。【东北大学 1 997 一、3(5 分)】（分数：2.00）_18.用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学 1999 计算机应用一、6(5 分)】（分数：2.00）_19.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：一一 CDEGHI 一 K 中序序列为：C B 一一 F AJ K I G 后序序列为：一 E F D BJ I HA【电子科技大学 2001 三、1(5 分)】【厦门大学 2002 七、l(6 分)】（分数：2.00）_20.M 叉树的前
9、序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应?【中国人民大学 2000 一、2(4分)】（分数：2.00）_21.设树形 T 在后根次序下的结点排列和各结点相应的次数如下：后根次序：BDEFCGJKILHA 次 数：000030002024 请画出 T 的树形结构图。【吉林大学 2001 一、2(4 分)】（分数：2.00）_22.已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学 2001 三、6】（分数：2.00）_23.对于二叉树 T 的两个结点 N1 和 N2，我们应该选择树 T 结点的前序、
10、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2 的祖先，并给出判断的方法。不需证明判断方法的正确性。【复旦大学 1999 五(10分)】（分数：2.00）_24.在二又树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用?如何清除最后这个递归语句?【北京邮电大学 1994 三(8 分)】（分数：2.00）_25.在二叉树的 Llink-一 Rlink 存储表示中，引入“线索”的好处是什么?【山东大学 1999 六、1(2 分)】（分数：2.00）_26.按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林
11、；(3)用后根序遍历该森林，写出遍历后的结点序列。 （分数：2.00）_27.一棵 h 层、度为 k(k1)的树，最多有多少个结点?【北京科技大学 2006】（分数：2.00）_设二叉树 BT 的存储结构如下： （分数：6.00）(1).画出二叉树 BT 的逻辑结构；（分数：2.00）_(2).写出按前序、中序、后序遍历该二叉树所得到的结点序列；（分数：2.00）_(3).画出二叉树的后序线索树。【中国矿业大学 2000 二(15 分)】（分数：2.00）_28.请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈
12、。【西安电子科技大学 1996 二、l(5 分)】（分数：2.00）_29.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少?【西安电子科技大学 2000 计算机应用一、2(5 分)】（分数：2.00）_30.在前序线索树上，要找出结点 p 的直接后继结点，请写出相关语句。结点结构为(1tag，lc，data， nag，rc)。 【西北大学 2000 二、6(5 分)】（分数：2.00）_31.对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱?【西北工业大学 1998 一、4(4 分)】（分数：2.00）_32.将下列树的孩子兄弟链表改
13、为后根遍历全线索链表。【清华大学 1994 二(10 分)】 （分数：2.00）_33.若森林共有 n 个结点和 b 条边(b_34.给定权 W1，W2，Wm。说明怎样来构造一个具有最小的加权路径长度的 k 叉树。试对于权1，4，9，16，25，36，49，64，8l，100 来构造最优的三叉树，并给出其最小加权路径长度。【北方交通大学 1994 四(12 分)】（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 4答案解析(总分：74.00，做题时间：90 分钟)一、综合题(总题数：35，分数：74.00)1.(1)试找出满足下列条件的二叉树：1)先序序列与后序序列
14、相同 2)中序序列与后序序列相同 3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG 和 DEBHIFGCA，画出这棵二叉树。【东北大学 1999 六(4 分)】【东南大学 2000 一、4(6 分)】（分数：2.00）_正确答案：(正确答案：(1)先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右子树”，后序遍历顺序是“左子树一右子树一根”，根据以上原则，本题解答如下： 1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。 2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左
15、子树的二叉树。 3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (2)由中序序列 DBEAFIHCG 和后序序列 DEBHIFGCA。 )解析：2.分别给出满足下列条件的二叉树。(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。【四川大学 2004】【烟台大学 2007 四、2(8 分)】（分数：2.00）_正确答案：(正确答案：空二叉树满足题目要求，若二叉树非空，则 (1)前序和中序遍历结果相同的二
16、叉树是任一结点无左子女； (2)前序和中序遍历结果不相同而是相反的二叉树是任一结点无右子女； (3)中序和后序遍历结果相同的二叉树是任一结点无右子女； (4)前序和后序遍历结果相同的二叉树是只有根结点。)解析：3.将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。 （分数：2.00）_正确答案：(正确答案：森林转为二叉树的三步： (1)连线(将兄弟结点相连，各树的根看作兄弟)； (2)切线(保留最左边子女为独生子女，将其他子女分支切掉)； (3)旋转(以最左边树的根为轴，顺时针向下旋转 45 度)。 其实经过(1)和(2)，已转为二又树，执行(3)只是为了与平时的二又树的画法一致。)
17、解析：4.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H 中序遍历序列：B FDAG E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。【南京航空航天大学 1997 二(10 分)】（分数：2.00）_正确答案：(正确答案：(1) (2) (3) )解析：5.已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)(2 分)给出这棵二叉树；(2)(2 分)转换为对应的森林；(3)(4 分)画出该森林的带右链的先根次序表示法；（分数：2.00）_正确答案：
18、(正确答案：(1) (2) (3)森林的带右链的前序表示法。在前序序列中，任何结点的子树的所有结点都直接跟在该结点之后；每棵子树的所有结点都聚集在一起，中间不会插入其他结点；任何分支结点后面跟的是它的第一个子女。故结点可采用如下结构(1tag，data，rlink)。其中，ltag 为左标记，ltag=1 表示该结点无子女或二叉树无左子女，Itag=0 表示其后存储其第一子女或二叉树的左子女；data 是结点的数据；rlink 指向下一兄弟或二叉树的右子女。用左标记代替左指针，占用存储单元少，不会丢失信息。本题森林的带右链的前序表示法为(注：“下标”行不是结点成分)： (4)带度数的后根次序表
19、示法。在后序序列中，任何一棵子树的结点聚在一起，根结点在最后。结点按后根次序顺序存储在一片连续的存储单元中，结点结构可描述为：(data，degree)。 (5)该森林带度数的后根次序表示法如下：后根次序序列中任何一棵子树的结点个数减边数为 1。设某结点的度 degree=m，即该结点有 m 个子女，最右边的子女就是该结点的前驱。在后根次序表示法中最后的第 2 个子女是最右子女为根的子树的前驱，以结点 x 为根的子树的前驱求法如下：令 q=0，从 x 开始从后往前走，每经过一个结点 z，作 q=q+-degree(z)；到 q=1 时，再往前走一个结点就是以结点 x 为根的子树在后根序列中的前
20、驱。 )解析：6.设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有 4 个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由 a，b，c，d 排列构成的字符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有 4 个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学 1997 六(15 分)】（分数：2.00）_正确答案：(正确答案：(1) )解析：7.假设一棵二叉树的前序序列为 ABCD，
21、它的中序序列可能是 DABC 吗?【石油大学 1998 一、1(5 分)】（分数：2.00）_正确答案：(正确答案：不能。因 DABC 并不是 ABCD 的合法出栈序列)解析：8.已知一棵二叉树的后序遍历序列为 EICBGAHDF，同时知道该二叉树的中序遍历序列为 CEIFGBADH，试画出该二叉树。【重庆大学 2000 二、2】（分数：2.00）_正确答案：(正确答案： )解析：9.已知一棵二叉树 T 的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。 【吉林大学 2007 二、3(3 分)】（分数：2.00）_正确答案
22、：(正确答案：二叉树略，其后根序列为：ECFDBIHGA。)解析：10.在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么?【上海交通大学 2003 五(10 分)】（分数：2.00）_正确答案：(正确答案：该结点应是二叉树最右边的叶子结点。因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，只有在最右边的叶子处，前序和中序遍历才能是同一个结点。)解析：11.在二叉树上进行前序遍历时，结点 A 在结点 B 之前，而在进行后序遍历时，结点 A 在结点 B 之后，那么结点 A 是结点 B 的祖先，对吗?为什么
23、?【上海交通大学 2003 六(10 分)】（分数：2.00）_正确答案：(正确答案：正确。前序遍历是“根一左一右”，后序遍历是“左一右一根”。前序遍历结点A 在结点 B 之前，说明结点 A 到 B 有路径，或 A 在 B 的左面。后序遍历结点 A 在结点 B 之后，说明结点 A到 B 有路径，或 A 在右面，B 在左面。综合以上情况，说明结点 A 是 B 的祖先。)解析：12.某二叉树的后序遍历序列为：，A，E，C D，B，其中 表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树?如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学 2007 三、23(8 分)】（分数：2.0
24、0）_正确答案：(正确答案：二叉树后序遍历序列是“左一右一根”，序列的最后一个结点是根，根结点的左面是右子树的根，若无右子树，则该位置应为 ， 的左面应是左子树的根结点，若无左子女，则该位置也为 。照此规则，就能建立二叉树。 )解析：13.输入带空二叉树信息(O)的前序遍历序列：A，G，B，C，D，E，E ，E ， 建立一棵二又树，其中 表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学 2006三、1(6 分)】（分数：2.00）_正确答案：(正确答案：二叉树前序遍历序列的第一个结点是根(如是空树，则用 表示)，接着应是左子树的根，如无左子树，则用 表示， 的后边是右子树的根，如无右子
25、树，则用 表示。如此分析，得二叉树如下。 )解析：14.已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列为(即后根次序)：A、C、B、E、D、X、，、H、F、K、，。请给出该二叉树的中序序列(即中根次序)。【上海交通大学 2001二(8 分)】（分数：2.00）_正确答案：(正确答案：二叉树中序序列 ABCDEFXHIJK。)解析：15.假设一棵二叉树的层次序列为 ABCDEFGHIJ，中序序列 DBGEHJACIF。请画出这棵二叉树。【武汉大学2000 三、1】【东南大学 20
26、00 一、1(6 分)】【大连理工大学 2005 二、3(204 分)】【中国海洋大学2007 一、5(8 分)】（分数：2.00）_正确答案：(正确答案：按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把序列分成左右两部分左子树和右子树。若左子树不空，层次序列中第二个结点是左子树的根；若左子树为空，则层次序列中第二个结点是右子树的根。对左、右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。该题型的算法参见下面算法设计题第 52 题。 )解析：16.已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO 后
27、序序列：CDEBFHIJGAMLONK【合肥工业大学 2000 四、1(5 分)】（分数：2.00）_正确答案：(正确答案：森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。 )解析：17.画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为 ABCDE。(2)高度为 5其对应的树(森林)的高度最大为 4。【东北大学 1 997 一、3(5 分)】（分数：2.00）_正确答案：(正确答案： )解析：18.用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学 1999
28、 计算机应用一、6(5 分)】（分数：2.00）_正确答案：(正确答案：HIDJKEBLFGCA。完全二叉树的结点按从上到下、从左到右的顺序，在数组中存储。结点 t 和其双亲、子女的编号间有确定的关系。)解析：19.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：一一 CDEGHI 一 K 中序序列为：C B 一一 F AJ K I G 后序序列为：一 E F D BJ I HA【电子科技大学 2001 三、1(5 分)】【厦门大学 2002 七、l(6 分)】（分数：2.00）_正确答案：(正确答案：本题解答原理及方法如下：首先掌握先序遍历是“根一左一右
29、”中序遍历是“左一根一右”，后序遍历是“左一右一根”。从给定条件的后序序列中，最后元素 A 是根。到中序序列中找到 A，A 将序列分成左右两部分：左边 5 个元素形成二叉树的左子树，右边 5 个元素形成二叉树的右子树。这样，先序序列从第 2 个元素开始的 5 个元素是二叉树左子树的先序序列，后面的 5 个元素形成二叉树右子树的先序序列。同理，后序序列也可以确定左右子树各有 5 个元素。先画左子树还是右子树都一样，按习惯，我们先画出左子树。从后序序列知，B 是左子树的根，到左子树的中序序列中找到 B，B 的左面有一个元素 C，这是 B 的左子女。B 的右面有 3 个元素，即 B 的右子树有 3
30、个结点。从左子树的先序(或后序)序列中都能发现 D 是 B 的右子树的根。但是这时中序序列并未给出 D，而是空格。这时 B 的右子树先序序列是“DE_”，中序序列是“_F”，后序序列是“EFD”，可以判定 E 是 D 的左子女，F 是 D 的右子女。至此，整棵二叉树的左子树分析完毕。同样，也可以画出右子树。)解析：20.M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应?【中国人民大学 2000 一、2(4分)】（分数：2.00）_正确答案：(正确答案：M 叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。)解析：21.设树形 T 在后根次序下的结点排列和各结点相应
31、的次数如下：后根次序：BDEFCGJKILHA 次 数：000030002024 请画出 T 的树形结构图。【吉林大学 2001 一、2(4 分)】（分数：2.00）_正确答案：(正确答案：树的遍历序列中，各子树的结点在一起，不会漏掉一个结点，也不会有其他子树的结点插到里面。后根遍历序列中最后一个是根结点，根结点的左边是其最右子树的根，该子树的结点连在一起。据此分析本题。A 是根结点，其次数是 4，即有 4 棵子树。H 在 A 的左边， 是 A 的最右子树的根，它有两棵子树，L 是右子树的根，它次数是 O，说明 L 是叶子。I 是 H 的左子树的根，它有两棵子树，K 是它右子树的根，次数 0
32、说明它是叶子，J 是 I 的左子树的根，它也是叶子。这就完成了对根 A 的最右子树的分析。同样也可以从右到左地分析根 A 的其他 3 棵子树。最后得到结果树如下。 )解析：22.已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学 2001 三、6】（分数：2.00）_正确答案：(正确答案：后序遍历的顺序是“左一右一根”。因此，二叉树最左(或右)下的叶子结点是后序遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。 if(p!=null) while(p 一lchild!=null p 一rchild!=null) 只要不是叶子 (while(p 一lchild!=null)p=p一1
