[考研类试卷]计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编11及答案与解析.doc

1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 11 及答案与解析一、综合题1 (1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同 2)中序序列与后序序列相同3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为 DBEAFIHCG 和 DEBHIFGCA，画出这棵二叉树。【东北大学 1999 六(4 分)】【东南大学 2000 一、4(6 分)】2 分别给出满足下列条件的二叉树。(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。【四川大学 20

2、04】【烟台大学 2007 四、2(8 分)】3 将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。【南京航空航天大学1998 一(10 分) 】4 设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H 中序遍历序列：B FDAG E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林) 。【南京航空航天大学 1997 二(10 分)】5 已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)(2 分 )给出这棵二叉树；(2)(2 分)转换为对应的森林；(

3、3)(4 分)画出该森林的带右链的先根次序表示法； (4)(4 分)画出该森林带度数的后根次序表示法；(5)(4 分) 在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点 x 为根的子树在后根次序序列中的前驱的求法。(用语言叙述，不用写算法。)【山东大学 1998 八(16 分)】6 设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有 4 个结点的二叉树的前序遍历序列为 abcd；S 为长度等于 4 的由a，b，c，d 排列构成的

4、字符序列，若任取 S 作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有 4 个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学 1997 六(15 分)】7 假设一棵二叉树的前序序列为 ABCD，它的中序序列可能是 DABC 吗? 【石油大学 1998 一、1(5 分) 】8 已知一棵二叉树的后序遍历序列为 EICBGAHDF，同时知道该二叉树的中序遍历序列为 CEIFGBADH，试画出该二叉树。【重庆大学 2000 二、2】9 已知一棵二叉树 T 的诸结点在先根次序下的排列为 :ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给

5、出其后根序列。 【吉林大学 2007二、3(3 分) 】10 在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么? 【上海交通大学 2003 五(10 分)】11 在二叉树上进行前序遍历时，结点 A 在结点 B 之前，而在进行后序遍历时，结点 A 在结点 B 之后，那么结点 A 是结点 B 的祖先，对吗?为什么? 【上海交通大学2003 六(10 分) 】12 某二叉树的后序遍历序列为：， ，A，E ，C D，B ，其中 表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树?如不能，请说明理由；如能够，试

6、画出对应二叉树。【华中科技大学 2007 三、23(8 分)】13 输入带空二叉树信息(O)的前序遍历序列：A，G，B ， ，C，D，E，E ，E ， 建立一棵二又树，其中 表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学 2006 三、1(6 分)】14 已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D 、B、A、C、E、H 、X、I、K；后序序列为(即后根次序)：A、C、B 、E、D、X、，、H、F、K、，。请给出该二叉树的中序序列 (即中根次序)。【 上海交通大学 2001 二(8 分)】15 假设一棵二叉

7、树的层次序列为 ABCDEFGHIJ，中序序列 DBGEHJACIF。请画出这棵二叉树。【武汉大学 2000 三、1】【东南大学 2000 一、1(6 分)】【大连理工大学 2005 二、3(204 分)】【中国海洋大学 2007 一、5(8 分)】16 已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【合肥工业大学 2000 四、1(5 分)】17 画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为ABCDE。(2) 高度为 5 其对应的树(森林)的高度最大为 4。【东北大学 1 99

8、7 一、3(5 分)】18 用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学 1999 计算机应用一、6(5 分)】19 一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：一一 CDEGHI 一 K中序序列为：C B 一一 F AJ K I G后序序列为：一 E F D BJ I HA【电子科技大学 2001 三、1(5 分)】【厦门大学 2002 七、l(6 分)】20 M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应?【中国人民大学 2000 一、2(4 分)】21 设树形

9、 T 在后根次序下的结点排列和各结点相应的次数如下：后根次序：BDEFCGJKILHA次 数：000030002024请画出 T 的树形结构图。【吉林大学 2001 一、2(4 分)】22 已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学 2001 三、6】23 对于二叉树 T 的两个结点 N1 和 N2，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2 的祖先，并给出判断的方法。不需证明判断方法的正确性。【复旦大学 1999 五(10 分)】24 在二又树的前序遍历

10、和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用?如何清除最后这个递归语句? 【北京邮电大学 1994 三(8 分)】25 在二叉树的 Llink-一 Rlink 存储表示中，引入“线索”的好处是什么? 【山东大学1999 六、1(2 分) 】26 按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林；(3) 用后根序遍历该森林，写出遍历后的结点序列。【北京邮电大学 1996 五(10 分)】27 一棵 h 层、度为 k(k1)的树，最多有多少个结点?【北京科技大学 2006】27 设二叉树 BT 的存储结构如下：其中 B

11、T 为树根结点的指针，其值为 6，Lchild，Rchild 分别为结点的左、右孩子指针域，data 为结点的数据域。试完成下列各题：28 画出二叉树 BT 的逻辑结构；29 写出按前序、中序、后序遍历该二叉树所得到的结点序列；30 画出二叉树的后序线索树。【中国矿业大学 2000 二(15 分)】31 请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学 1996 二、l(5 分)】32 一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少?【西安电子科技大学 2000 计算机应用一、

12、2(5 分)】33 在前序线索树上，要找出结点 p 的直接后继结点，请写出相关语句。结点结构为(1tag，lc ，data， nag ， rc)。 【西北大学 2000 二、6(5 分)】34 对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱?【西北工业大学 1998 一、4(4 分)】35 将下列树的孩子兄弟链表改为后根遍历全线索链表。【清华大学 1994 二(10 分)】36 若森林共有 n 个结点和 b 条边(blchild!=null p 一rchild!=null) 只要不是叶子(while(p 一lchild!=null)p=p 一1c

13、hild ； 首先沿左子树向下if(p 一rchildl=null)p=p 一rchild； 无左子树而有右子树时沿右子树向下ret 一 urn(p)； 返回后序序列第一个结点的指针23 【正确答案】 采用前序和后序两个序列来判断二叉树上结点 n1 必定是结点 n2的祖先。在前序序列中某结点的祖先都排在其前。若结点 n1 是 n2 的祖先，则 n1必在 n2 之前。而在后序序列中，某结点的祖先排在其后，即若结点 n1 是 n2 的祖先，则 n1 必在 n2 之后。根据这条规则来判断若结点 n1 在前序序列中在 n2 之前，在后序序列中又在 n2 之后，则它必是结点 n2 的祖先。对本题的解答还

14、可以参见上面第 59 题。24 【正确答案】 最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为“ 尾递归 ”，可不用栈且将其 (递归)消除。如中序遍历递归算法中，最后的递归语句 inorder(bt 一rchild)可改为下列语句段：bt=bt 一rchi ld；while(bt 一rchild!=null)(inorder(bt 一1child)；conltdatarchild；25 【正确答案】 在二叉链表表示的二叉树中，查找结点的左右子女非常方便，但查找后继就不太方便。引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就变得非常

15、简单。为此将二叉树加上线索。利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记 ltag 和 rtag，约定 ltag=0 时，lchild 指向左子女，ltag=1 时，lchild 指向前驱；rtag=0 时，rchild 指向右子女，rtag=1 时，rchild 指向后继。这样，在线索二叉树(特别是中序线索二叉树) 上遍历就消除了递归，也不使用栈(后序线索二叉树查后继仍需要栈。)26 【正确答案】 给二叉树加上线索有如下要点：首先要明确是什么序的线索化，即前序、中序还是后序线索化；二是前驱、后继还是全线索化；三是只有空指针处才能加线索。本题是后序后继线索画

16、，画上前驱线索或在非空处加线索就是画蛇添足，说明概念不明确。(1) (2)(3)后根遍历森林，结点序列为：BDCAIFJGHELOPMNK27 【正确答案】 1+k 1+k2+k3+kh-1=(kh 一 1)(k-1)28 【正确答案】 29 【正确答案】 前序序列：A BC E D F H G I J中序序列：E C B H F D J I G A后序序列：E C H F J I G D B A30 【正确答案】 31 【正确答案】 后序线索树中结点的后继，要么是其右线索(当结点的 rtag=1 时) ，要么是其双亲结点右子树中最左下的叶子结点。所以，只有当二叉树只有根或树中任一结点均无右子

17、树时，进行遍历才不用栈，其遍历程序段如下：while(p 一1tag=0)p： =p 一lchild； 找最左下叶子结点while(p 一rchild!=null)visit(p 一data)； 访问结点p=p 一rchild； 沿线索向上对前序线索二叉树，当二叉树非空时，若其结点有左子女(ltag=0)，左子女是后继；否则，若结点有右子女(rtag=0)，则右子女是后继；若无右子女 (rmg=1)，右链是线索，也指向后继。所以，对任何前序线索二叉树进行前序遍历均不需使用栈。32 【正确答案】 左右子树均不空的二叉树先序线索化后，空指针域为 1 个(最后访问结点的右链为空)。33 【正确答案】

18、 if(p 一ltag=0)return(p 一lchild)； 左子女不空，左子女为直接后继结点 else return(p 一rchild)； 左子女空，右子女 (或右线索)为后继34 【正确答案】 后序线索树中结点的后继求法如下：根结点无后继；当结点的rtag=1 时，其右线索指向后继；当结点的 nag=0 且是其双亲的右子女，或是双亲的左子女且双亲无右子女时，其双亲是该结点的后继；当结点是其双亲的左子女且双亲有右子女时，其后继是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于 1，则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。

19、35 【正确答案】 树的后根遍历(对应二叉树的中序遍历)全线索链表36 【正确答案】 森林的 n 个结点开始可看作是 n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入 b 条边将减少 b 个连通分量，因而 n 个结点 b 条边的森林有 n 一 b 棵树。37 【正确答案】 首先确定是否需加“虚权值”( 即权值为 0)，对 m 个权值，建尼叉树，若(m1) (k-1)=0，则不需要加“虚权值” ，否则，第一次归并时需(m 一 1)(k-1)+1 个权值归并。建立 k 叉树的过程如下：(1)将 m 个权值看作 m 棵只有根结点的 k 叉树的集合 F=T1，T2 ，Tm 。(2) 从 F 中选 k(若需加虚权值，则第一次选(m 一 1)(k-1)+1) 个权值最小的树作子树，构成一棵 k 叉树，k 叉树根结点的权值为所选的后个树根结点权值之和，在 F 中删除这 k 棵子树，并将新 k 叉树加入 F 中。(3)重复(2)，直到 F 中只有一棵树为止，这就是最优的 k 叉树。对本题 10个权值，构造最优三叉树。因(101)(31)=1 ，所以第一次用 2 个权值合并。最小加权路径长度：