发布时间 : 星期四 文章计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13更新完毕开始阅读
标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二又树的静态二叉链表如右图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二又链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。【合肥工业大学2000五、3(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：静态链表中结点是按动态二叉链表的前序遍历顺序存放的。首先对动态二叉链表的二叉树进行前序遍历，填写静态链表的“下标”和data域，再对动态二叉链表的二叉树进行层次遍历，设队列Q，填写静态链表的lchild域和rchild域。) 解析：
14.假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注：已知树中结点数)【清华大学1994七(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：以双亲表示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至(根)结点，就可求出每一结点的层次，取其结点的最大层次就是树的深度。核心语句段如下： int maxdepth=0； for(i=1；io){temp++； t=t．nodes[f]．parent ；} ／／深度加1，并取新的双亲 if(temp>maxdepth) maxdepth=temp； ／／最大深度更新 } return(maxdepth)； ／／返回树的深度) 解析：
15.设一棵二叉树用二叉链表表示，求该树的高度。【南京航空航天大学2004二、2(12分)】【北京理工大学2000四3(4)】【北京轻工业学院1997一(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树是递归定义的，其运算最好采取递归方式。 int Height(btre bt) ／／求二叉树bt的深度 fint hl，hr； ／／hl和hr分别是左子树和右子树的深度 if(bt==null)return(0)； else(hl=Height(bt一>ich)；hr=Height(bt一>rch)； if(h1>hr)return(hl+1)； else return(hr+1)； } }) 解析：
16.二叉树以链接形式(1eft，data，right)存储，给出求二叉树宽度的算法，所谓宽度是二又树的各层上，具有结点数最多的那一层上的结点总数。 【吉林大学2006四(10分)】【华南理工大学2004三、1(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：求最大宽度可采用层次遍历的方法，记下各层结点数，取其最大宽度。 Q[rear]=bt； ／／根结点入队列 while(front<=last) ／／front，rear初值为1，last同层最右结点在队列中的位置 (p=Q[front++]；temp++； ／／同层元素数加1，temp记当前层宽度 if(p一>ichild!=null) Q[++rear]=p一>Ichild； ／／左子女入队 if(p一>rchild!=null) Q[++rear]=p一>rchild； ／／右子女入队 if(front>last) ／／一层结束 {last=rear； ／／last指向下层最右元素 if(temp>maxw)maxw=temp； ／／更新当前最大宽度，maxw记最大宽度 temp=0； ／／准备下层 }／／if }while) 解析：
17.以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学1999五(18分)】【南京航空航天大学2000九】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：由孩子兄弟链表表示的树高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。递归算法的核心语句段如下： if(bt==null)return(0)； else if(1bt->firstchild)return(max(1，height(bt->nextsibling)))； else(hc=height(bt一>firstchild)； ／／第一子女树高 hs=height(bt一>nextsibling)； ／／兄弟树高 if(hc+l>hs)return(hc+1)； else return(hs)； }／／else 非递归遍历求以孩子兄弟链表表示的树的深度的核心语句段如下： Q[rear]=t；
／／Q是以树中结点为元素的队列 while(front<=last) ／／初始front=rear=1 {t=Q[front++]； ／／队头出列 while(t｜=null) ／／层次遍历 fif(t一>firstchild)Q[++rear]=t一>firstchild；／／第一子女入队 t=t一>nextsibling； ／／同层兄弟指针后移 } if(front>last) ／／本层结束，深度加1(初始深度为0) {h++；last=rear；} ／／last再移到指向当前层最右一个结点 }) 解析：
18.设一棵二叉树的结点结构为(LLINK，INFO，RLINK)，ROOT为指向该二叉树根结点的指针，p和g分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR(RDOT，p，q，r)，该算法找到p和q的最近共同祖先结点r。【吉林大学2000二、3(12分)】【中山大学1994六(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：本题到22题是在以二叉链表存储的二叉树上找某结点的所有祖先，某两个结点的最近公共祖先，从根结点到某结点的路径，根结点到每个叶子结点以及最远叶子的路径等。均应采取后序非递归遍历。因为后序遍历最后访问根结点，当访问到某结点时，栈中所有元素均为该结点的祖先。这里只对16题进行分析。找p和q的最近共同祖先结点r，不失一般性，设P在q的左边。后序遍历必然先遍历到结点P，栈中元素均为P的祖先。将栈复制到另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配(即相等)的元素就是结点p和q的最近公共祖先。其核心语句段如下： while(bt!=null ｜｜ top>0) {while(bt!=null＆＆bt!=p＆&bt!=q) ／／结点入栈 {S[++top].t=bt ； s[top]．tag=0；bt=bt一>ichild；} ／／沿左分支向下 if(bt==p)／／假定P在q的左侧，遇结点P时，栈中元素均为P的祖先结点 for(i=1；i<=top； i++)sl[i]=S[i]；topl=top； ／／栈S元素转入辅助栈s1 if(bt==q) ／／找到q结点 for(i：top； i>0 ； i一) ／／将栈中元素到sl去匹配 {pp=s[i]．t； for(j=topl；j>0；j—-) if(sl[j]．t==pp){cout
19.当一棵有n(0<=100)个结点的二叉树按顺序存储方式存储在bf[1..n]中时，试写一个算法，求出二叉树中结点值分别为x和y的两个结点的最近的公共祖先结点的值。【同济大学2003四(10分)】【武汉大学2000五】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系进行求解。设结点值为x和y的两个结点的下标分别是i和j，求下标为i和j的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 while(i!=j) ／／直到i=j时，就是原来两个结点的最近的公共祖先 if(i>j)i=i／2 ； ／／下标为x的结点的双亲结点的下标 else j=j／2； ／／下标为Y的结点的双亲结点的下标) 解析：
20.设一棵完全二叉树使用顺序存储在数组6f[1..n]中，请写出进行非递归的前序遍历算法。【西安电子科技大学1998四(9分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树的顺序存储一般按完全二叉树的顺序存储格式，双亲与子女结点下标间有确定关系。顺序存储结构的二叉树用结点下标大于n(对于完全二叉树)或0(对一般二叉树的“虚结点”)来判空。本题是完全二叉树，核心语句段如下： while(i<=n｜｜ top>0) ／／初始调用时，i=1，top=0 {while(i<=n) fcout<<=n)S[++top]*2*i+1； ／／右子女的下标位置进栈 i：2*i； ／／沿左子女向下 } if(top>0)i=s[top一一]； ／／取出栈顶元素 }) 解析：
21.若二叉树用以下存储结构表示，试给出求前序遍历的算法：TYPE Tree=ARRAY[1．．max] OF RECORD data：char ; parent：integer； END；（分数：2.00）
【北京邮电大学2002五、4(15分)】
__________________________________________________________________________________________ 正确答案：(正确答案：另一种双亲表示法存储结构，结点结构是(dam,parent)。对每个结点，直接给出其双亲(的下标)，用正或负表示该结点是双亲的右子女或左子女，0表示该结点是根，无双亲。该类结构不适于直接进行前序遍历(即若直接前序遍历，算法要很复杂)，较好的办法是将这类结构转为结点及其左右子女的顺序存储结构。转换的核心语句段如下： for(i=1；i<=max； i++)(bt[i]．1c=bt[i]．rc=0；) ／／先将结点的左右子女初始化为0 for(i=1；i<=max； i++) ／／填入结点数据和结点左右子女的信息 {bt[i]．data=t[i]．data； ／／t[]是原结构，bt[]是转换后的结构 if(t[i]．parent0)
bt[t[i]．parent]．rc=i； ／／右子女 else root=i； ／／root记住根结点的下标 } 前序递归和非递归遍历上面已有，不再赘述。这类问题的求解方法值得注意。当给定数据存储结构不合适时，可由已给结构来构造好的数据结构，以便于运算。像上面第6题也是这样，先根据L和R数组，构造一个结点的双亲的数组T。) 解析：
22.设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。【合肥工业大学1999五、2(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树先序序列最后一个结点的特征是：从根开始的任何结点，若有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结点。核心语句段如下： while(p) ／／设p是二叉树根结点的指针 f(p->rchild)p=p一>rchild； ／／若右子树不空，沿右子树向下 else if(p一>1child)p=p一>lchild； ／／右子树空，左子树不空，沿左子树向下 else return(p)； ／／p即为所求) 解析：
23.已知一棵高度为k具有n个结点的二叉树，按顺序方式存储：(1)编写用先根遍历树中每个结点的非递归算法；(2)编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学1997六(20分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：高度为K的二叉树，按顺序方式存储，要占用2 一1个存储单元，与实际结点个数n关系不大，对不是完全二叉树的二叉树，要增加“虚结点”，使其在形态上成为完全二叉树。二叉树中最大序号的叶子结点是在顺序存储方式下编号最大的结点。核心语句段如下：while(bt[c]==0)c一一； ／／初值c=2 一1，从后向前滤去虚结点找最大序号叶子 f=c／2 ； ／／c的双亲结点f while(f!=0) ／／从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点 {cout＜cbt[f])；f=f／2 ；} ／／逆序输出，最老的祖先最后输出) 解析：
24.在二叉链表表示的二叉树中，增设一个指针域，初值为空，试给出算法在不使用堆栈又不破坏原二叉树的情况下，前序遍历该二叉树。【北京邮电大学2004五、2(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：将空指针(下面的pre)域改成指向双亲(或祖先)。核心语句段如下： while(t) ／／t初值是二叉树根结点的指针 {while(t) {cohtpre=f； ／／指向双亲，初值f=null f=t；t=t一>lchild； ／／沿左侧向下 } t=f； ／／回退 while(t&&t一>rchild==null) t=t一>pre； ／／回返 if(t&&t一>rchild) {f=t一>pre； ／／避免从右侧返回时，再重复访问左侧 t=t一>rchild； ／／右转 } }) 解析：
25.对于二叉树的链接实现，完成非递归的中序遍历过程。【中山大学1999五、2(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：wh5．1e(p ｜｜ top>0) ／／p是二叉树指针，top是栈顶指针，初值为0 {while(p) {s[++top]=p；p=p一>lchild；) ／／沿左子树向下 if(top)>0) {p=s[top一]；cout
k
k
解析：
26.已知二叉树用下面的顺序存储结构，写出中序遍历该二叉树的算法。C(#,F(H,I))存储如上图。【北京邮电大学1999九(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：二叉树用顺序方式存储，其遍历方法与用二叉链表方式存储类似。0表示空指针。顺序存储方式下，要告诉根结点的下标。 void InOrder(int i) ／／对顺序存储的二叉树进行中序遍历，i是根结点的下标 {if(i!=0) {InOrder(ar[i]．Lc)； ／／中序遍历左子树 cout< 解析：
27.试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学2001二、2(8分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设一队列Q和栈S。将根结点入队。当队列不空，做如下操作：Q出队；出队元素入栈S；出队结点的非空左、右子女依次入队Q。队列空后，弹出栈S中元素即为所求。) 解析：
如树T=A(D，E(#,，G))，