1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 9及答案解析(总分：60.00，做题时间：90 分钟)一、设计题(总题数：30，分数：60.00)1.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为 1 的结点数目的算法。【同济大学 2000 三、2(12 分)】【山东大学 1993 二(12 分)】【上海交大 1999 三(12 分)】【天津大学 2005 七(10 分)】【北京理工 200l 九(8 分)2006 七、1(152 分)】【南京航空航天大学 2004二、3(12 分)】（分数：2.00）_2.设一棵二叉树以二叉链表为存储结构，结点
2、结构为(1child，data，rchild)，设计一个算法将二叉树中所有结点的左、右子树相互交换。【福州大学 1998 四、2(10 分)】（分数：2.00）_3.设 t 为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。【东北大学 1996 五(14 分)】（分数：2.00）_4.设 T 是一棵满二叉树，写一个把 T 的后序遍历序列转换为先序遍历序列的递归算法。【中科院研究生院2003 十(15 分)】（分数：2.00）_5.所有分支结点的度为 2 的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归 函数 int FormalTree(B
3、itree t)，判断二叉树是否为正则二叉树。【北京理工大学 2005 四、2(5 分)】（分数：2.00）_6.若二叉树 BT 的每个结点，其左、右子树都为空，或者其左、右子树都不空，这种二又树有时称为“严格二叉树”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。设“严格二叉树”BT 的前序遍历序列为：ABDECFHIGJKLM，后序遍历序列为：DEBHIFJLMKGCA(1)试画出该二叉树；(6 分)(2)写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。(9 分)（分数：2.00）_7.设二叉树采用二叉链表作为存储结构。试用类 Pascal 语言实现按前序遍历顺序
4、输出二又树中结点的非递归算法。要求定义所用结构。设栈已经定义：inits(S)，empty(S)，push(S，P)，pop(S)，top(S)分别为栈初始化，判栈空，入栈，出栈，看栈顶等操作。【北京工业大学 1997 二、1(10 分)】（分数：2.00）_8.以二叉链表作存储结钩，试编写非递归的前序遍历算法。【华南理工大学 2005 三、1(5 分)】（分数：2.00）_9.设二叉树以二叉链表为存储结构，编写一个后序遍历二叉树的非递归算法(要求先用文字写出实现的基本思想，再用 C 语言写出算法)。【中国海洋大学 2006 八(15 分)】（分数：2.00）_10.已知一棵度为 12 的树，
5、它的根结点的地址为 root。该树是用顺序方式存储的，说明如下：struct node int data; 树中结点的数据场 int son12； 给出结点的第 1 个，第 2 个，第 3 个第 12 个儿子结点地址tnodeM； M 是树中结点数，常量请设计一个非递归的程序，按前序遍历该树，打印每个结点的数据场之值。注意：如用递归程序实现，做零分处理。【上海交通大学 2003 一(15分)】（分数：2.00）_11.设某二叉树结点结构为：TYPE bitreptr=bnodetp；bnodetp=RECORD data：integer； 1child， rchild：bitreptr END
6、；试编写算法，计算每层中结点 data 域数值大于 50 的结点个数，并输出这些结点的 data 域的数值和序号。【北京工业大学 1998 九(10 分)】（分数：2.00）_12.已知一二叉树中结点的左右孩子分别为 left 和 right，p 指向二叉树的某一结点。请用 C 或 Pascal 编一个非递归函数 postfirstp)，求 p 所对应子树的第一个后序遍历结点。【浙江大学 1998 六(10 分)】【上海交通大学 2004 二(10 分)】（分数：2.00）_13.假设在二叉链表的结点中增设两个域：parent 域以指示其双亲结点；flag 域(取值为 02)以区分在遍历过程中
7、到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。【中南大学 2004 三、2(10 分)】（分数：2.00）_14.已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。【上海交通大学 1999 四(12 分)】【江苏大学 2005 五、2(10 分)】（分数：2.00）_15.已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组 IN1：n和 POST1：n中，(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(1chil
8、d，data，。rchild)，其中 data 为数据域，lchild 与 rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 nil 表示)。【北京航空航天大学1998 六(1 5 分)】（分数：2.00）_16.试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学 2000 二(10 分)】（分数：2.00）_17.已知二叉树 T，试写出复制该二叉树的算法(tT)(1)(8 分)递归算法(2)(12 分)非递归算法【北方交通大学 1993 七(20 分)】（分数：2.00）_18.假设一维数组研 1：n存放森林 F 的每个结点的地址，且序列 H
9、1，H2，Hn正好是森林 F 在先根次序下结点地址的排列；E1：n是一维数组，且当 1in 时，Ei是 Hi所指结点的次数(即儿子结点的个数)。试给出一个算法，该算法计算森林 F 的树形个数，并计算森林 F 的最后一个树形的根结点地址。【吉林大学 1995 五(15 分)】（分数：2.00）_19.已知二叉树的链表存储结构定义如下：TYPE bitreptr=bitrenode;bitrenode：record data：char; 1chi ld， rchi 1d：bitreptr END;编写一个递归算法，利用叶结点中空的右链指针域 rchild，将所有叶结点自左至右链接成一个单链表，算法
10、返回最左叶结点的地址(链头)。【清华大学 1997 三(10 分)】（分数：2.00）_20.(1)试分别找出满足下列条件的所有二叉树：(a)前序序列和中序序列相同；(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。(2)已知非空二叉树的结点结构为(1child，data，rchild)，设计算法：从右向左依次将所有叶子的数据值放到 a 向量(假定向量的空间大干叶子的总个数)中。【厦门大学 2005二(1 5 分)】 （分数：2.00）_21.编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。【东北大学 1999 四(1 3 分)】（
11、分数：2.00）_22.写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。【中国人民大学 2000 三、1(10 分)】（分数：2.00）_23.假设二叉树 T 的各个元素值均不相同，设计一个递归算法按递减次序打印各元素值，用 C 语言描述二叉树的结构，用文字说明算法思想，并写出算法。【北京交通大学 2005 八(10 分)】（分数：2.00）_24.已知二叉树 T 采用二叉链表结构存储，每个结点有三个字段：data，Lchild 和 Rchild。设计算法求出T 的顺序存储结构 A1n，并给出初始调用形式。要求：如某位置为空，将其置为 null；如超出下标范围 n 则报错；最后返回实际的最
12、大下标。如图所示为，l=15 时一个二叉树及所对应的输出结果示例(空缺表示 null)。输出结果(表结构的值和最大下标)：maxsub=12(最大下标为 12)。【合肥工业大学 2001 五、5(8 分)】 （分数：2.00）_25.设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。(注：按层由上到下，由左到右)【东南大学 2005 数据结构部分四(15 分)】（分数：2.00）_26.设两棵二叉树的根结点地址分别为 p 和 q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交通大学 2000 十二(8 分)】（分数：2.00）_27.设计一个算
13、法，判断两棵以二叉链表表示的二叉树是否相等。【北京邮电大学 2005 五、3(10 分)】（分数：2.00）_28.编写递归算法，依据树的双亲表示法及其根结点创建树的孩子兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。【清华大学 1995 六(20 分)】（分数：2.00）_29.已知二叉树以二又链表存储，编写算法完成：对于树中每一个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。【北京工商大学 1998 二(14 分)】（分数：2.00）_30.试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为 x 的结点，以及以它为根的子树，且释放相应存储
14、空间。二叉树的三叉链表的描述为：TYPE bitreptr=nodetp；nodetp=record data：char； lchild， rchild，parent：bitreptr END；VAR bt：bitreptr；二叉树根结点的指针【同济大学 1998 四(14 分)】（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 9答案解析(总分：60.00，做题时间：90 分钟)一、设计题(总题数：30，分数：60.00)1.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为 1 的结点数目的算法。【同济大学 2000 三、2(1
15、2 分)】【山东大学 1993 二(12 分)】【上海交大 1999 三(12 分)】【天津大学 2005 七(10 分)】【北京理工 200l 九(8 分)2006 七、1(152 分)】【南京航空航天大学 2004二、3(12 分)】（分数：2.00）_正确答案：(正确答案：层次遍历二叉树，需要使用队列。在遍历中统计度为 1 的结点的个数。核心语句段如下： QueueInit(Q)； QueueIn(Q，bt)； Q 是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q) p=Queueout(Q)； coutichild 树中结点的数据场 int son12； 给出结点
16、的第 1 个，第 2 个，第 3 个第 12 个儿子结点地址tnodeM； M 是树中结点数，常量请设计一个非递归的程序，按前序遍历该树，打印每个结点的数据场之值。注意：如用递归程序实现，做零分处理。【上海交通大学 2003 一(15分)】（分数：2.00）_正确答案：(正确答案：将根结点 root 进栈。(1)若栈不空，出栈，访问该结点；(2)按从 12 到 1 的逆序，将该结点非空儿子进栈。(3)转(1)。)解析：11.设某二叉树结点结构为：TYPE bitreptr=bnodetp；bnodetp=RECORD data：integer； 1child， rchild：bitreptr
17、END；试编写算法，计算每层中结点 data 域数值大于 50 的结点个数，并输出这些结点的 data 域的数值和序号。【北京工业大学 1998 九(10 分)】（分数：2.00）_正确答案：(正确答案：采用层次遍历，设一队列 Q，用 front 和 rear 分别指向队头和队尾元素，last 指向各层最右结点位置。存放值大于 50 的结点结构如下： typedef structint level，value，idx；node； 元素所在层号、值和本层中的序号 int front=0，last=1，rear=1，level=1，i=0，num=0； num 记大于 50 的结点个数 BiTre
18、e Q；Q1=bt ； 根结点入队 while(frontdata50) s.level=level； sidx=+i； svalue=bt 一data； a+num=s ; if(bt 一Ichild!=null)Q+rear=bt 一ichild； 左子女入队列 if(bt 一rchild!=null)Q+rear=bt 一rchild； 右子女入队列 if(front=last) 本层最后一个结点已处理完 last=rear； level+；i=0 ； 初始化下层：last 指向下层最右结点 层号加 1，下层50 的序号初始为 0 )解析：12.已知一二叉树中结点的左右孩子分别为 lef
19、t 和 right，p 指向二叉树的某一结点。请用 C 或 Pascal 编一个非递归函数 postfirstp)，求 p 所对应子树的第一个后序遍历结点。【浙江大学 1998 六(10 分)】【上海交通大学 2004 二(10 分)】（分数：2.00）_正确答案：(正确答案：二又树结点 P 所对应子树的第一个后序遍历结点 g 的求法如下：若 P 有左子树，则 q 是 p 的左子树上最左下的叶子结点；若 P 无左子树，仅有右子树，则 q 是 P 的右子树上最左下的叶子结点。 while(q 一left llq 一right) 找最左下的叶子结点，初始调用 q=p if(q 一left)q=q
20、一left； 优先沿左分支向下去查“最左下”的叶子结点 else q=q 一right； 沿右分支去查“最左下”的叶子结点)解析：13.假设在二叉链表的结点中增设两个域：parent 域以指示其双亲结点；flag 域(取值为 02)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。【中南大学 2004 三、2(10 分)】（分数：2.00）_正确答案：(正确答案：后序遍历二叉树是“左子树一右子树一根结点”，而查找结点的后继要通过双亲结点，因此设置结点结构为(1child，data，rchild，parent，flag)。遍历中当
21、flag=0 时置 flag 为 1，并遍历左子树；当 flag=1 时置 flag 为 2，并遍历右子树；当 flag=2 时访问结点，同时恢复 flag=0，再去查找其双亲。核心语句段如下： while(p) switch(p 一flag) (case 0：P 一flag=1；if(p 一ichild)p=p-Ichild； 向左 break； case 1：p 一flag=2；if(p 一rchild)p=P 一rchild； 向右 break； case 2：p 一flag=0；printf(p 一data)； 访问“根”结点 P=P 一parent； 找被访问结点的双亲 switch
22、)解析：14.已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。【上海交通大学 1999 四(12 分)】【江苏大学 2005 五、2(10 分)】（分数：2.00）_正确答案：(正确答案：由一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定二叉树，请参见本章四、41 题。确定二又树的算法如下： void PreInCreat(BiTree root，ElemType pre，in，int 11，h1，12，h2) (root=new(BiNode)； 申请结点 root 一data=pre11； pre11是根 for(i：12；ic：h2
23、；i+) 在中序序列中查找根结点，它将二叉树分成左右子树 if(ini=pre11)break； if(i：=12)root 一ichild=null； 无左子树 else PreInCreat(root 一ichild，pre，in，11+1，ii+(i 一 12)，12，i 一 1)； 递归建立左子树 if(i=-h2)root 一rchiId=null； 无右子树 else PreInCreat(root 一rchild，pre，in，11+(i 一 12)+1，hl，i+l，h2) 递归建立右子树 结束 PreInCreat)解析：15.已知一具有 n 个结点的二叉树的中序遍历序列与后
24、序遍历序列分别存放于数组 IN1：n和 POST1：n中，(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(1child，data，。rchild)，其中 data 为数据域，lchild 与 rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 nil 表示)。【北京航空航天大学1998 六(1 5 分)】（分数：2.00）_正确答案：(正确答案：由二叉树的中序序列与后序序列也可以建立一棵二叉树 void PreInCreat(BiTree root，ElemType pre，in，int 11，h
25、1，12，h2) (root=new(BiNode)； 申请结点 root 一data=pre11； pre11是根 for(i：12；ic：h2；i+) 在中序序列中查找根结点，它将二叉树分成左右子树 if(ini=pre11)break； if(i：=12)root 一ichild=null； 无左子树 else PreInCreat(root 一ichild，pre，in，11+1，ii+(i 一 12)，12，i 一 1)； 递归建立左子树 if(i=-h2)root 一rchiId=null； 无右子树 else PreInCreat(root 一rchild，pre，in，11+(
26、i一 12)+1，hl，i+l，h2) 递归建立右子树 结束 PreInCreat)解析：16.试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学 2000 二(10 分)】（分数：2.00）_正确答案：(正确答案：由二叉树的中序序列和层次序列可以唯一确定该二叉树，其手工描述见上面应用题的 63 题，限于篇幅，这里不再画出该二叉树，只分析生成二叉树的算法。层次序列第一个结点是二叉树的根，在中序序列中“根”将二叉树分成左右子树两部分。但在层次序列中，左子树的结点和右子树的结点混在一起，不能一眼分出每个结点属于左子树还是属于右子树。应从层次序列第 2 个(第 1 个是根)结点起，逐个到
27、二叉树的左子树部分比对，形成左子树的层次遍历序列。同样，也可形成右子树的层次遍历序列。实现时可利用两个一维数组，分别存放左右子树的层次序列。设二叉树的层次序列和中序序列分别用 level0n 一 1和 in0.n 一 1表示，再设根结点在中序序列中下标是 i(0in 一 1)，则左、右子树层次序列和中序序列都可以用数组表示。算法的核心语句如下：BiTree creat(EiemType level，in，int 11，h1，12，h2)二叉树的层次序列和中序序列生成二叉树。初始 11=12=0，h1=h2=n 一1，n 是结点数 bt=new(BiNode)； bt 一data=level11
28、； 层次序列的第一个结点是二叉树的根 for(i=12jiichild=null； 二叉树无左子树 elsefor(k=11+1；krchild=null； 二叉树无右子树 elsefor(k=11+1；krhild=Creat(1evell，in，0，ii，i+l，h2)；生成右子树 return bt； BiTree Copy(BiTree t) 复制-X 树 t 的递归算法 BiTree bt； if(t=null)bt=null； elsebt=new(BiNode)； bt 一data=t 一data； bt 一lchild=C0py(t 一l child)； bt 一rchild=
29、Copy(t-rchiid)； return(bt)；结束 Copy)解析：17.已知二叉树 T，试写出复制该二叉树的算法(tT)(1)(8 分)递归算法(2)(12 分)非递归算法【北方交通大学 1993 七(20 分)】（分数：2.00）_正确答案：(正确答案：下面是复制二叉树的非递归算法的核心语句段： Queueln(Q，(t，bt)； while(!QueueEmpty(Q) (t，bt)=QueueOut(Q)； bt=new(BiNode)；bt 一data=t 一data ； if(t 一ichiid)QueueIn(Q，(t-ichild，bt-ichild)； elBe bt
30、 一ichiid=null； if(t 一rchiId)QueueIn(Q，(t-rchiid，bt-rchiid)；else bt-rchiId=null； 本题队列中元素是两个二叉树结点指针，使用了队列，用栈也可以。)解析：18.假设一维数组研 1：n存放森林 F 的每个结点的地址，且序列 H1，H2，Hn正好是森林 F 在先根次序下结点地址的排列；E1：n是一维数组，且当 1in 时，Ei是 Hi所指结点的次数(即儿子结点的个数)。试给出一个算法，该算法计算森林 F 的树形个数，并计算森林 F 的最后一个树形的根结点地址。【吉林大学 1995 五(15 分)】（分数：2.00）_正确答案
31、：(正确答案：森林在先根次序遍历时，首先遍历第一棵子树的根，接着是第一棵子树的结点；之后是第二棵树，直到最后一棵树。前序序列中每棵树的结点连续存放，不会丢掉一个结点，也不会插入其他树上的一个结点。本题中 Ei是 Hi所指结点的次数，就是结点的分支个数 B，而分支数 B与树的结点数的关系是 N=B+1(除根结点外，任何一个结点都有一个分支所指)。所以，从 Ei的第一个单元开始，将值累加，当累加到第 i 个单元，其值正好等于 i 一 1 时，就是第一棵树。接着，用相同方法，将其他树分开，进行到第 n 个单元，将所有树分开。例如，上面应用题第 51 题(2)的森林可按本题图示如下。从左往右将次数加到
32、下标 8(=B+1)时，正好结束第一棵树。 )解析：19.已知二叉树的链表存储结构定义如下：TYPE bitreptr=bitrenode;bitrenode：record data：char; 1chi ld， rchi 1d：bitreptr END;编写一个递归算法，利用叶结点中空的右链指针域 rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址(链头)。【清华大学 1997 三(10 分)】（分数：2.00）_正确答案：(正确答案：叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针 head 指向，遍历到叶
33、子结点时，就将它前驱的 rchild 指针指向它，最后叶子结点的 rchild 为空。核心语句段如下： if(bt)InOrder(bt 一Ichild)； 中序遍历左子树 if(bt 一Ichild=null&bt 一rchild=null) 叶子结点 if(pre=null)head=bt；pre=bt；) 处理第一个叶子结点 elsepre 一rchild=bt；pre=bt；) 将叶子结点链入链表 InOrder(bt 一rchild)； 中序遍历右子树 pre 一rchild=null ； 设置链表尾 时间复杂度为 O(n)，辅助变量使用 head 和 pre，栈空间复杂度为 O(n
34、)。)解析：20.(1)试分别找出满足下列条件的所有二叉树：(a)前序序列和中序序列相同；(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。(2)已知非空二叉树的结点结构为(1child，data，rchild)，设计算法：从右向左依次将所有叶子的数据值放到 a 向量(假定向量的空间大干叶子的总个数)中。【厦门大学 2005二(1 5 分)】 （分数：2.00）_正确答案：(正确答案：(1)本题在应用题第 46 题已有解答，请参考。(2)题目要求“从右向左依次将所有叶子的数据值放到 a 向量中”，这要使用“右子树一根结点一左子树”，的中序遍历。可以参照上题算法。)解析：21.编写算法
35、，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。【东北大学 1999 四(1 3 分)】（分数：2.00）_正确答案：(正确答案：“双链表”中定义二叉树的左指针为指向前驱的指针，右指针是指向后继的指针，链表在遍历中建立，记住前驱结点和当前结点，访问中第一个叶子结点的前驱为空，最后一个叶子结点的后继为空。算法简单，可以参照上面第 55 题，不再赘述。)解析：22.写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。【中国人民大学 2000 三、1(10 分)】（分数：2.00）_正确答案：(正确答案：此树看作度为 2 的有序树，先将根结点入队列。 (1)当队列不空，结点出队；若队列为空，则结束。 (2)若结点有两个子女，访问该结点，将(右)第二子女入队列，并转向第一子女，重复执行(2)否则转(3)。 (3)若结点仅一个子女，访问该结点，并将子女入队，转(I)。 (4)若结点无子女，则访问该结点，转(1)。)解析：23.假设二叉树 T 的各个元素值均不相同，设计一个递归算法按递减次序打印各元素值，用 C 语言描述二叉树的结构，用文字说明算法思想，并写出算法。【北京交通大学 2005 八(10 分)】（分数：2.00）_
