计算机专业基础综合数据结构树和二叉树历年真题试卷汇编4

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编4（总分：74.00，做题时间：90分钟）一、综合题（总题数：35,分数：74.00）.（1）试找出满足下列条件的二叉树：1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同⑵已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。【东北大学1999六（4分）】【东南大学2000一、4（6分）】（分数：2.00）正确答案：（正确答案：（1）先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右子树”，后序遍历顺序是“左子树一右子树一根”，根据以上原则，本题解答如下：1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。4）若中序序列与层次遍历序列相同，则蚂为空树，或为任一结点至多只有右子树的二叉树。（2）由中序序列DBEAFIHCG和后序序列DEBHIFGCA。I ）解析：.分别给出满足下列条件的二叉树。（1）前序和中序遍历结果相同；（2）前序和中序遍历结果不相同而是相反；（3）中序和后序遍历结果相同；（4）前序和后序遍历结果相同。【四川大学2004】【烟台大学2007四、2（8分）】（分数：2.00）正确答案：（正确答案：空二叉树满足题目要求，若二叉树非空，则（1）前序和中序遍历结果相同的二叉树是任一结点无左子女；（2）前序和中序遍历结果不相同而是相反的二叉树是任一结点无右子女；（3）中序和后序遍历结果相同的二叉树是任一结点无右子女；（4）前序和后序遍历结果相同的二叉树是只有根结点。）（分数：2.00）正确答案：（正确答案：森林转为二叉树的三步：（1）连线（将兄弟结点相连，各树的根看作兄弟）；（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）；（3）旋转（以最左边树的根为轴，顺时针向下旋转45度）。其实经过（1）和（2），已转为二又树，执行⑶只是为了与平时的二又树的画法一致。）解析：.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABD，CEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学1997二（10分）】（分数：2.00）

(4)(4.已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK后序：LGHDIEBJKFCA（1）（2分）给出这棵二叉树；（2）（2分）转换为对应的森林；（3）（4分）画出该森林的带右链的先根次序表示法;(4)(4分）画出该森林带度数的后根次序表示法；（5）（4分）在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法。）【山东大学1998八（16分）】（分数：2.00）正确答案：（正确答案：（1）1——1（2）1——।⑶森林的带右链的前序表示法。在前序序列中，任何结点的子树的所有结点都直接跟在该结点之后；每棵子树的所有结点都聚集在一起，中间不会插入其他结点；任何分支结点后面跟的是它的第一个子女。故结点可采用如下结构（1tag，data，rlink）。其中，ltag为左标记，ltag=1表示该结点无子女或二叉树无左子女，Itag=0表示其后存储其第一子女或二叉树的左子女；data是结点的数据；rlink指向下一兄弟或二叉树的右子女。用左标记代替左指针』用存储单元少，不会丢失信息。本题森林的带右链的前序表示法为（注：“下标”行不是结点成分）：।——L）带度数的后根次序表示法。在后序序列中，任何一棵子树的结点聚在一起，根结点在最后。结点按后根次序顺序存储在一片连续的存储单元中，结点结构可描述为：（data，degree）o（5）该森林带度数的后根次序表示法如下：后根次序序列中任何一棵子树的结点个数减边数为1。设某结点的度degree=m，即该结点有m个子女，最右边的子女就是该结点的前驱。在后根次序表示法中最后的第2个子女是最右子女为根的子树的前驱，以结点x为根的子树的前驱求法如下:令q=0，从x开始从后往前走，每经过一个结点z，作q=q++-degree（z）；到q=1时，再往前走一个结点就是以结点x为根的子树在后根序列中的前驱。।——）解析：.设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树。（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。（3）设具有4个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学1997六（15分）】（分数：2.00）正确答案：（正确答案:⑵设二叉树的前序遍历序列为P1正确答案：（正确答案:⑵设二叉树的前序遍历序列为P1，P2,…，Pm，中序遍历序列为S1，S2,…，Sm。因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，则前序遍历序列中第一个结点P1是根结点。到中序序列中查询到Si=P1，根据中序遍历时根结点将中序序列分成左右两部分的原则，有：若i=1，即S1=P1，则这时的二叉树没有左子树；否则，S1，S2,…，Si一1是左子树的中序遍历序列，用该序列和前序序列p2,P3,…，Pi去构造该二叉树的左子树。若i=m，即Sm=P1，则这时的二叉树没有右子树；否则，Si+1，Si+2,…，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1，Pi+2,…，Pm，、去构造该二叉树的右子树。算法描述请参见下面算法设计题第49题。（3）若前序序列是abed，并非由这四个字母的任意组合（41=24）都能构造出二叉树、因为以abed为输入序列，通过栈只能得到1/n+1）*2n!/（n!*n!）=14种，即以abcd为前序序列的二叉树的数目是14。任取以abed作为中序遍历序列，并不全能与前序的abed序列构成二叉树。例如：若取中序序列dcab就不能。该14棵二叉树的形态及中序序列略。）解析：.假设一棵二叉树的前序序列为ABCD，它的中序序列可能是DABC吗？【石油大学1998一、1（5分）】（分数：2.00）正确答案：（正确答案：不能。因DABC并不是ABCD的合法出栈序列）解析：.已知一棵二叉树的后序遍历序列为EICBGAHDF,同时知道该二叉树的中序遍历序列为CEIFGBADH,试画出该二叉树。【重庆大学2000二、2】（分数：2.00）正确答案：（正确答案：। ）解析：.已知一棵二叉树T的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。【吉林大学2007二、3（3分）】（分数：2.00）正确答案：（正确答案：二叉树略，其后根序列为：ECFDBIHGAo）解析：.在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质？为什么？【上海交通大学2003五（10分）】（分数：2.00）正确答案：（正确答案：该结点应是二叉树最右边的叶子结点。因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，只有在最右边的叶子处，前序和中序遍历才能是同一个结点。）解析：.在二叉树上进行前序遍历时，结点A在结点B之前，而在进行后序遍历时，结点A在结点B之后，那么结点A是结点B的祖先，对吗?为什么？【上海交通大学2003六（10分）】（分数：2.00）正确答案：（正确答案：正确。前序遍历是“根一左一右”，后序遍历是“左一右一根”。前序遍历结点A在结点B之前，说明结点A到B有路径，或A在B的左面。后序遍历结点A在结点B之后，说明结点A到B有路径，或A在右面，B在左面。综合以上情况，说明结点A是B的祖先。）解析：.某二叉树的后序遍历序列为：，①，①，A，①，①，E，①，①，CD，B，其中①表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树?如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学2007三、23（8分）】（分数：2.00）正确答案：（正确答案：二叉树后序遍历序列是“左一右一根”，序列的最后一个结点是根，根结点的左面是右子树的根，若无右子树，则该位置应为T，9的左面应是左子树的根结点，若无左子女，则该位置也为①。照此规则，就能建立二叉树。I ）解析：.输入带空二叉树信息（O）的前序遍历序列：A，G，①，①，B，①，C，D，E，①，E①，①，①，E①，中建立一棵二又树，其中①表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学2006三、1（6分）】（分数：2.00）正确答案：（正确答案：二叉树前序遍历序列的第一个结点是根（如是空树，则用中表示），接着应是左子树的根，如无左子树■，则用①表示，9的后边是右子树的根，如无右子树，则用中表示。如此分析，得二叉树如下。। ）解析：

.已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为（即先根次序）：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。）解析：.假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。【武汉大学2000三、1】【东南大学2000一、1（6分）】【大连理工大学2005二、3（20/4分）】【中国海洋大学2007一、5（8分）】（分数：2.00）正确答案：（正确答案：按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分一一左子树和右子树。若左子树不空，层次序列中第二个结点是左子树的根；若左子树为空，则层次序列中第二个结点是右子树的根。对左、右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。该题型的算法参见下面算法设计题第52题。解析：.已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列:CDEBFHIJGAMLONK【合肥工业大学2000四、1（5分）】（分数：2.00）正确答案：（正确答案：森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。解析：构造二叉树，再构造出森林。解析：.画出同时满足下列两条件的两棵不同的二叉树。（1）按先根序遍历二叉树顺序为ABCDE。（2）高度为5其对应的树（森林）的高度最大为4。【东北大学1997一、3（5分）】.用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学1999计算机应用一、6（5分）】（分数：2.00）正确答案：（正确答案：HIDJKEBLFGCA。完全二叉树的结点按从上到下、从左到右的顺序，在数组中存储。结点t和其双亲、子女的编号间有确定的关系。）解析：.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：-一CDE—GHI-K中序序列为：CB——FA—JKIG后序序列为：-EFDB—JIH—A【电子科技大学2001三、1（5分）】【厦门大学2002七、l（6分）】（分数：2.00）正确答案：（正确答案：本题解答原理及方法如下：首先掌握先序遍历是“根一左一右”中序遍历是“左一根一右”，后序遍历是“左一右一根"。从给定条件的后序序列中，最后元素A是根。到中序序列中找到A,A将序列分成左右两部分：左边5个元素形成二叉树的左子树，右边5个元素形成二叉树的右子树。这样，先序序列从第2个元素开始的5个元素是二叉树左子树的先序序列，后面的5个元素形成二叉树右子树的先序序列。同理，后序序列也可以确定左右子树各有5个元素。先画左子树还是右子树都一样，按习惯，我们先画出左子树。从后序序列知，B是左子树的根，到左子树的中序序列中找到B，B的左面有一个元素C，这是B的左子女。B的右面有3个元素，即B的右子树有3个结点。从左子树的先序（或后序）序列中都能发现D是B的右子树的根。但是这时中序序列并未给出D，而是空格。这时B的右子树先序序列是“DE___"，中序序列是"___F”，后序序列是“EFD”，可以判定E是D的左子女，F是D的右子女。至此，整棵二叉树的左子树分析完毕。同样，也可以画出右子树。）解析：.M叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？【中国人民大学2000一、2（4分）】（分数：2.00）正确答案：（正确答案：M叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。）解析：.设树形T在后根次序下的结点排列和各结点相应的次数如下：后根次序：BDEFCGJKILHA次数：000030002024请画出T的树形结构图。【吉林大学2001一、2（4分）】（分数：2.00）正确答案：（正确答案：树的遍历序列中，各子树的结点在一起，不会漏掉一个结点，也不会有其他子树的结点插到里面。后根遍历序列中最后一个是根结点，根结点的左边是其最右子树的根，该子树的结点连在一起。据此分析本题。A是根结点，其次数是4,即有4棵子树。H在A的左边，是A的最右子树的根，它有两棵子树，L是右子树的根，它次数是O,说明L是叶子。I是H的左子树的根，它有两棵子树，K是它右子树的根，次数0说明它是叶子，J是I的左子树的根，它也是叶子。这就完成了对根A的最右子树的分析。同样也可以从右到左地分析根A的其他3棵子树。最后得到结果树如下。।——）解析：.已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学2001三、6】（分数：2.00）正确答案：（正确答案：后序遍历的顺序是“左一右一根”。因此，二叉树最左（或右）下的叶子结点是后序遍历的第一个结点。下面的语句段说明了这一过程（设p是二叉树根结点的指针）。if（p!=null）{while（p一>lchild!=nullI}p一〉rchild!=null）//只要不是叶子（while（p->lchild!=null）p=p—>1child；//首先沿左子树向下if（p一>rchildl=null）p=p—>rchild； //无左子树而有右子树时沿右子树向下}}ret一urn（p）； //返回后序序列第一个结点的指针）解析：.对于二叉树T的两个结点N1和N2,我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先，并给出判断的方法。不需证明判断方法的正确性。【复旦大学1999五（10分）】（分数：2.00）正确答案：（正确答案：采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先。在前序序列中某结点的祖先都排在其前。若结点n1是n2的祖先，则n1必在n2之前。而在后序序列中，某结点的祖先排在其后，即若结点n1是n2的祖先，则n1必在n2之后。根据这条规则来判断若结点n1在前序序列中在n2之前，在后序序列中又在n2之后，则它必是结点n2的祖先。对本题的解答还可以参见上面第59题。）解析：.在二又树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用？如何清除最后这个递归语句？【北京邮电大学1994三（8分）】（分数：2.00）正确答案：（正确答案：最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为“尾递归”，可不用栈且将其（递归）消除。如中序遍历递归算法中，最后的递归语句inorder（bt一〉rchild）可改为下列语句段：bt=bt一〉rchild；while（bt一〉rchild!=null）（inorder（bt—>1child）；conlt<data<rchild；｝）解析：.在二叉树的Llink-一Rlink存储表示中，引入“线索”的好处是什么？【山东大学1999六、1（2分）】（分数：2.00）正确答案：（正确答案：在二叉链表表示的二叉树中，查找结点的左右子女非常方便，但查找后继就不太方便。引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就变得非常简单。为此将二叉树加上线索。利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记ltag和rtag，约定ltag=0时，lchild指向左子女，ltag=1时，lchild指向前驱；rtag=0时，rchild指向右子女，rtag=1时，rchild指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（后序线索二叉树查后继仍需要栈。））解析：.按下面要求解下图中二叉树的有关问题：（1）对此二叉树进行后序后继线索化;（2）将此二叉树变换为森林；（3）用后根序遍历该森林，写出遍历后的结点序列。I 【北京邮电大学1996五（10分）】（分数：2.00）正确答案：（正确答案：给二叉树加上线索有如下要点：首先要明确是什么序的线索化，即前序、中序还是后序线索化；二是前驱、后继还是全线索化；三是只有空指针处才能加线索。本题是后序后继线索画，画上前驱线索或在非空处加线索就是画蛇添足，说明概念不明确。（1）। 1（2）। ⑶后根遍历森林，结点序列为：BDCAIFJGHELOPMNK）解析：.一棵h层、度为k（k〉1）的树，最多有多少个结点？【北京科技大学2006】（分数：2.00）正确答案：（正确答案：1+k1+k2+k3+…+kh-1=（kh-1）/（k-1））解析：设二叉树BT的存储结构如下：।——其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：（分数：6.00）（1）.画出二叉树BT的逻辑结构；（分数：2.00）（2）.写出按前序、中序、后序遍历该二叉树所得到的结点序列；（分数：2.00）正确答案：（正确答案：前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA）解析：解析：.请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学1996二、1（5分）】（分数：2.00）正确答案：（正确答案：后序线索树中结点的后继，要么是其右线索（当结点的rtag=1时），要么是其双亲结点右子树中最左下的叶子结点。所以，只有当二叉树只有根或树中任一结点均无右子树时，进行遍历才不用栈，其遍历程序段如下：whi1e（p—>1tag==0）p：=p->1chi1d； //找最左下叶子结点whi1e（p一〉rchi1d!=nu11）{visit（p一〉data）； //访问结点p=p一>rchild； //沿线索向上}对前序线索二叉树，当二叉树非空时，若其结点有左子女（1tag=0）,左子女是后继；否则，若结点有右子女（rtag=0）,则右子女是后继；若无右子女（rmg=1）,右链是线索，也指向后继。所以，对任何前序线索二叉树进行前序遍历均不需使用栈。）解析：.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？【西安电子科技大学2000计算机应用一、2（5分）】（分数：2.00）正确答案：（正确答案：左右子树均不空的二叉树先序线索化后，空指针域为1个（最后访问结点的右链为空）。）解析：.在前序线索树上，要找出结点p的直接后继结点，请写出相关语句。结点结构为（1tag,lc,data,nag,rc）。【西北大学2000二、6（5分）】（分数：2.00）正确答案：（正确答案：if（p一>1tag==0）return（p—>1chi1d）； //左子女不空，左子女为直接后继结点elsereturn（p一〉rchild）；//