1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 13 及答案与解析一、设计题1 在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为 1 的结点数目的算法。【同济大学 2000 三、2(12 分)】【山东大学1993 二(12 分) 】【上海交大 1999 三(12 分) 】【天津大学 2005 七(10 分)】【北京理工 200l 九(8 分)2006 七、 1(152 分) 】【南京航空航天大学 2004 二、3(12 分)】2 设一棵二叉树以二叉链表为存储结构，结点结构为(1child，data ，rchild)，设计一个算法将二叉树中所有结点的
2、左、右子树相互交换。【福州大学 1998 四、2(10分)】3 设 t 为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。【东北大学 1996 五(14 分)】4 设 T 是一棵满二叉树，写一个把 T 的后序遍历序列转换为先序遍历序列的递归算法。【中科院研究生院 2003 十(15 分)】5 所有分支结点的度为 2 的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归 函数 int FormalTree(Bitree t)，判断二叉树是否为正则二叉树。【北京理工大学 2005 四、2(5 分) 】6 若二叉树 BT 的每个结点，其左、右子树都为
3、空，或者其左、右子树都不空，这种二又树有时称为“ 严格二叉树 ”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。设“ 严格二叉树 ”BT 的前序遍历序列为：ABDECFHIGJKLM，后序遍历序列为：DEBHIFJLMKGCA(1)试画出该二叉树；(6 分)(2)写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。(9 分)7 设二叉树采用二叉链表作为存储结构。试用类 Pascal 语言实现按前序遍历顺序输出二又树中结点的非递归算法。要求定义所用结构。设栈已经定义：inits(S)，empty(S)，push(S，P)，pop(S)，top(S)分别为栈初始化，判栈空，入
4、栈，出栈，看栈顶等操作。【北京工业大学 1997 二、1(10 分)】8 以二叉链表作存储结钩，试编写非递归的前序遍历算法。【华南理工大学 2005三、1(5 分) 】9 设二叉树以二叉链表为存储结构，编写一个后序遍历二叉树的非递归算法(要求先用文字写出实现的基本思想，再用 C 语言写出算法)。【中国海洋大学 2006 八(15 分)】10 已知一棵度为 12 的树，它的根结点的地址为 root。该树是用顺序方式存储的，说明如下：struct node int data; 树中结点的数据场int son12； 给出结点的第 1 个，第 2 个，第 3 个第 12 个儿子结点地址tnodeM；
5、M 是树中结点数，常量请设计一个非递归的程序，按前序遍历该树，打印每个结点的数据场之值。注意：如用递归程序实现，做零分处理。【上海交通大学 2003 一(15 分)】11 设某二叉树结点结构为：TYPE bitreptr=bnodetp；bnodetp=RECORD data：integer ； 1child ， rchild：bitreptr END；试编写算法，计算每层中结点 data 域数值大于 50 的结点个数，并输出这些结点的data 域的数值和序号。【北京工业大学 1998 九(10 分)】12 已知一二叉树中结点的左右孩子分别为 left 和 right，p 指向二叉树的某一结点
6、。请用 C 或 Pascal 编一个非递归函数 postfirstp)，求 p 所对应子树的第一个后序遍历结点。【浙江大学 1998 六(10 分)】【上海交通大学 2004 二(10 分)】13 假设在二叉链表的结点中增设两个域：parent 域以指示其双亲结点；flag 域(取值为 02)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。【中南大学 2004 三、2(10 分 )】14 已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。【上海交通大学 1999 四(12 分)】
7、【江苏大学2005 五、2(10 分) 】15 已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN1：n和 POST1：n 中， (设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(1child，data，。rchild)，其中 data 为数据域，lchild 与 rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 nil 表示)。【北京航空航天大学 1998 六(1 5 分)】16 试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学 2000 二(10 分)】
8、17 已知二叉树 T，试写出复制该二叉树的算法(tT)(1)(8 分) 递归算法(2)(12 分) 非递归算法【北方交通大学 1993 七(20 分)】18 假设一维数组研 1：n存放森林 F 的每个结点的地址，且序列 H1，H2，Hn正好是森林 F 在先根次序下结点地址的排列；E1：n是一维数组，且当1in时，Ei是 Hi所指结点的次数 (即儿子结点的个数)。试给出一个算法，该算法计算森林 F 的树形个数，并计算森林 F 的最后一个树形的根结点地址。 【吉林大学 1995 五(15 分) 】19 已知二叉树的链表存储结构定义如下：TYPE bitreptr=bitrenode;bitreno
9、de：record data：char; 1chi ld， rchi 1d：bitrept r END;编写一个递归算法，利用叶结点中空的右链指针域 rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址(链头)。【清华大学 1997 三(10 分)】20 (1)试分别找出满足下列条件的所有二叉树：(a)前序序列和中序序列相同；(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。(2)已知非空二叉树的结点结构为(1child ，data，rchild)，设计算法：从右向左依次将所有叶子的数据值放到a 向量(假定向量的空间大干叶子的总个数 )中。【厦门大学 2005
10、 二(1 5 分)】21 编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。【东北大学 1999 四(1 3 分)】22 写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。【中国人民大学2000 三、1(10 分) 】23 假设二叉树 T 的各个元素值均不相同，设计一个递归算法按递减次序打印各元素值，用 C 语言描述二叉树的结构，用文字说明算法思想，并写出算法。【北京交通大学 2005 八(10 分) 】24 已知二叉树 T 采用二叉链表结构存储，每个结点有三个字段： data，Lchild 和Rchild。设计算法求出 T 的顺序存储结构
11、A1n，并给出初始调用形式。要求：如某位置为空，将其置为 null；如超出下标范围 n 则报错；最后返回实际的最大下标。如图所示为，l=15 时一个二叉树及所对应的输出结果示例(空缺表示 null)。输出结果(表结构的值和最大下标)：maxsub=12(最大下标为 12)。【合肥工业大学 2001 五、5(8 分)】25 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。(注：按层由上到下，由左到右)【东南大学 2005 数据结构部分四(15 分)】26 设两棵二叉树的根结点地址分别为 p 和 q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交
12、通大学 2000 十二(8 分)】27 设计一个算法，判断两棵以二叉链表表示的二叉树是否相等。【北京邮电大学2005 五、3(10 分) 】28 编写递归算法，依据树的双亲表示法及其根结点创建树的孩子兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。【清华大学 1995 六(20分)】29 已知二叉树以二又链表存储，编写算法完成：对于树中每一个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。【北京工商大学 1998 二(14 分)】30 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为 x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树
13、的三叉链表的描述为：TYPE bitreptr=nodetp；nodetp=record data：char； lchild， rchild，parent：bitreptr END；VAR bt：bitreptr；二叉树根结点的指针【同济大学 1998 四(14 分)】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 13 答案与解析一、设计题1 【正确答案】 层次遍历二叉树，需要使用队列。在遍历中统计度为 1 的结点的个数。核心语句段如下：QueueInit(Q)； QueueIn(Q，bt)； Q 是以二叉树结点指针为元素的队列while(!QueueEmpty(Q)p=Queue
14、out(Q)； coutdata； 出队，访问结点if(p 一ichildif(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 的序号初始为 012 【正确答案】 二又树结点 P 所对应子树的第一个后序遍历结点 g 的求法如下：若 P 有左子树，则 q 是 p 的左子树上最左下的叶子结点；若 P 无左子树
15、，仅有右子树，则 q 是 P 的右子树上最左下的叶子结点。while(q 一left llq 一right) 找最左下的叶子结点，初始调用 q=pif(q 一left)q=q 一left ； 优先沿左分支向下去查 “最左下”的叶子结点else q=q 一 right； 沿右分支去查“最左下”的叶子结点13 【正确答案】 后序遍历二叉树是“左子树一右子树一根结点” ，而查找结点的后继要通过双亲结点，因此设置结点结构为(1child，data ，rchild，parent，flag)。遍历中当 flag=0 时置 flag 为 1，并遍历左子树；当 flag=1 时置 flag 为 2，并遍历右子
16、树；当 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 ； 找被访问结点的双亲 switch14 【正确答案】 由一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定二叉树，请参见本章四、41 题。确
17、定二又树的算法如下：void PreInCreat(BiTree root，ElemType pre，in ，int 11，h1，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； 无左子树elsePreInCreat(root 一ichild，pre，in，11+1 ，ii+(i 一 12)，12，i 一 1)； 递归建立左子树if(i=-h2)root 一r
18、chiId=null； 无右子树elsePreInCreat(root 一rchild，pre ，in，11+(i 一 12)+1，hl ，i+l，h2) 递归建立右子树 结束 PreInCreat15 【正确答案】 由二叉树的中序序列与后序序列也可以建立一棵二叉树void PreInCreat(BiTree root，ElemType pre，in，int 11，h1，12，h2)(root=new(BiNode)； 申请结点root 一data=pre11； pre11是根for(i：12；ic ：h2；i+) 在中序序列中查找根结点，它将二叉树分成左右子树if(ini=pre11)bre
19、ak；if(i：=12)root 一ichild=null； 无左子树elsePreInCreat(root 一ichild，pre，in，11+1 ，ii+(i 一 12)，12，i 一 1)； 递归建立左子树if(i=-h2)root 一rchiId=null； 无右子树elsePreInCreat(root 一rchild，pre ，in，11+(i 一 12)+1，hl ，i+l，h2) 递归建立右子树 结束 PreInCreat16 【正确答案】 由二叉树的中序序列和层次序列可以唯一确定该二叉树，其手工描述见上面应用题的 63 题，限于篇幅，这里不再画出该二叉树，只分析生成二叉树的算
20、法。层次序列第一个结点是二叉树的根，在中序序列中“根” 将二叉树分成左右子树两部分。但在层次序列中，左子树的结点和右子树的结点混在一起，不能一眼分出每个结点属于左子树还是属于右子树。应从层次序列第 2 个(第 1 个是根)结点起，逐个到二叉树的左子树部分比对，形成左子树的层次遍历序列。同样，也可形成右子树的层次遍历序列。实现时可利用两个一维数组，分别存放左右子树的层次序列。设二叉树的层次序列和中序序列分别用 level0n 一 1和 in0.n 一 1表示，再设根结点在中序序列中下标是 i(0in 一 1)，则左、右子树层次序列和中序序列都可以用数组表示。算法的核心语句如下：BiTree cr
21、eat(EiemType level ，in ，int 11，h1，12，h2)二叉树的层次序列和中序序列生成二叉树。初始11=12=0，h1=h2=n 一 1，n 是结点数bt=new(BiNode)；bt 一data=level11； 层次序列的第一个结点是二叉树的根for(i=12jiichild=null； 二叉树无左子树elsefor(k=11+1；kIchild=Creat(1evell，in，0，ii，II，i 一 1)；生成左子树if(i=h2)bt 一rchild=null； 二叉树无右子树elsefor(k=11+1；krhild=Creat(1evell，in，0，ii，
22、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=Copy(t-rchiid)；return(bt)；结束 Copy17 【正确答案】 下面是复制二叉树的非递归算法的核心语句段：Queueln(Q，(t ，bt)；while(!QueueEmpty(Q)(t，bt)=QueueOut(Q)；bt=new(BiNode)；b
23、t 一data=t 一data ；if(t 一ichiid)QueueIn(Q，(t-ichild，bt-ichild)； elBe bt 一ichiid=null；if(t 一rchiId)QueueIn(Q，(t-rchiid，bt-rchiid) ；else bt-rchiId=null；本题队列中元素是两个二叉树结点指针，使用了队列，用栈也可以。18 【正确答案】 森林在先根次序遍历时，首先遍历第一棵子树的根，接着是第一棵子树的结点；之后是第二棵树，直到最后一棵树。前序序列中每棵树的结点连续存放，不会丢掉一个结点，也不会插入其他树上的一个结点。本题中 Ei是 Hi所指结点的次数，就是结
24、点的分支个数 B，而分支数 B 与树的结点数的关系是 N=B+1(除根结点外，任何一个结点都有一个分支所指)。所以，从 Ei的第一个单元开始，将值累加，当累加到第 i 个单元，其值正好等于 i 一 1 时，就是第一棵树。接着，用相同方法，将其他树分开，进行到第 n 个单元，将所有树分开。例如，上面应用题第 51 题(2)的森林可按本题图示如下。从左往右将次数加到下标8(=B+1)时，正好结束第一棵树。19 【正确答案】 叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre，初始为空。第一个叶子结点由指针 head 指向，遍历到叶子结点时，就将它前驱的 rchild 指针
25、指向它，最后叶子结点的 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)。20 【正确答案】 (1)本题在应用题第 46 题
26、已有解答，请参考。(2)题目要求“从右向左依次将所有叶子的数据值放到 a 向量中” ，这要使用 “右子树一根结点一左子树”，的中序遍历。可以参照上题算法。21 【正确答案】 “ 双链表 ”中定义二叉树的左指针为指向前驱的指针，右指针是指向后继的指针，链表在遍历中建立，记住前驱结点和当前结点，访问中第一个叶子结点的前驱为空，最后一个叶子结点的后继为空。算法简单，可以参照上面第 55题，不再赘述。22 【正确答案】 此树看作度为 2 的有序树，先将根结点入队列。(1)当队列不空，结点出队；若队列为空，则结束。(2)若结点有两个子女，访问该结点，将(右) 第二子女入队列，并转向第一子女，重复执行(2
27、)否则转 (3)。(3)若结点仅一个子女，访问该结点，并将子女入队，转(I)。(4)若结点无子女，则访问该结点，转(1) 。23 【正确答案】 这里按二叉排序树考虑。按“右一根一左” 的中序遍历即可。若非二叉排序树，则很复杂。 一次遍历找到一个最小结点，循环 n 遍，输出完毕。24 【正确答案】 按层次遍历二叉树，用队列存储结点，数组 A 按完全二叉树存储，初始化 A 的各元素都是 null。核心语句段如下：QueueIn(Q，(bt，1) ； 二叉树根结点指针和参数 1 入队列while(!QueueEmpty(Q)qq=QueueDel(Q)； p=qqt；i=qq i；Ai=P 一dat
28、a ；last=i； 数据存入数组， i 是当前最大下标if(p 一lchild) QueueIn(Q，(p 一ichiid，2*i)；if(t-rchild)QueueIn(Q，(p-ichild ，2*i+1)coutdata ；last=i； 数据存入数组， i 是当前最大下标if(p 一lchild) QueueIn(Q，(p 一ichiid，2*i)；if(t-rchild)QueueIn(Q，(p-ichild ，2*i+1)coutichild，q 一ichiid)&Similar(p-rchild，q-rchiid)；27 【正确答案】 在上题基础上，增加判断对应结点的数据是否
29、相等的语句。if(p=null&q=null)return(1)；else if(!P&q P& !q) return (0)；else if(pdada!=q-data)return(0)；else return(Equal(p 一Ichild，q-Ichild)&Equal(p 一rchild，q-rchild)；28 【正确答案】 树根结点是二叉树的根，遍历双亲表示法的整个静态链表找到根结点的子女，第一个子女是孩子兄弟表示法中的孩子，其他子女结点作兄弟。对双亲表示法中的任一结点，均递归建立其孩子兄弟链表子树。核心语句段如下：CSTree cst=new(CSNode)； 申请结点空间cs
30、t 一data=ptnodesroot data ； 根结点，初始调用要给出 root 的下标值cst 一fir8tchild=null ； cst 一nextsibling=null； firstchild=l ； 孩子标记for(i=l；ifirstchild=chiid；firstchiid=0；sibling=cst 一firstchiid ； elsechild 不是 root 的第一个孩子，作兄弟处理(sibling 一nextsibling=child ； sibling=sibling 一nextsibling ；29 【正确答案】 删除以元素值 x 为根的子树，只要能删除其左
31、右子树，就可以释放值为 x 的根结点，因此宜采用后序遍历。、删除值为 x 结点，意味着应将其父结点的左(或右)子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每一个元素值为 x 的结点的子树，因此要遍历完整棵二叉树。30 【正确答案】 若二叉树已用二叉链表表示，当结点的子女存在时，将子女结点加上指向双亲的指针(根结点的双亲指针为空)。下面给出建立用三叉链表表示的二叉树的算法。二叉树按完全二叉树格式输入，对非完全二叉树，要补上“虚结点” 。按完全二叉树双亲和子女存储下标间的关系，完成双亲和子女间指针的链接。是输入结束标志，$是虚结点标志。核心语句段如下：cinch ；while(ch!=#)p=null；if(ch!=$)p=new(nodetp)；p 一data=ch ；P 一Ichild=p 一rchild=null ；Q+rear=P； 元素或虚结点， Q 是队列，元素是二叉树结点指针；初值rear=0if(p)if(rear=1)root=p； root 一parent=null； 根结点elsefQrear一parent=Qrear 2 ； 双亲结点和子女结点用指针链上if(rear2=0)Qrear 2一ichild=Qrear；else Qrear2-rchild=Qrear ；cinch ； while
