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

计算机专业基础综合数据结（树和二叉树历年真题试卷汇编14(分：58.00做题时间：分钟)一、设计(总题数：29，分数：58.00)1.用C语描述树的孩子兄弟链表结构，并编写递归程序求树中叶子结点数。【北京交通大学2004八10分)__________________________________________________________________________________________正确答案：(确答案：孩子兄弟链表表示的树中孩子指针为空的结点是叶子。intCount(CSTreet)／／统计以孩子兄弟链表表示的树的叶子结点个数(if(t==null)return(0)；if(t一>firstlchild==null)return(1+Count(t一nextsibling))；elsereturn(Count(t->firstchiid)+Count(t->nextsibling))；／／子女中叶子兄弟中叶子})2.设二叉树用二指结构存储(以是动态存储结构)元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶子结点。【华南理工大200323(2)(23／2)__________________________________________________________________________________________正确答案(确答案：首先设计一个函数，使用任何一种遍历方法，查找元素值等于某个给定的整数的结点，返回该结点指针。之后，再在遍历以该结点为根的子树的过程中求叶子结点。3.用类Pascal言编写一非递归算法求二叉树上叶子结点的数量二叉树用二叉链表存储左指针定义为lchild，指针定义为。【燕大学2000七2(8分)】__________________________________________________________________________________________正确答案：确答案：以二叉链表为存储结构的二叉树遍历的非递归算法，在“访问根结点”时，加上判断该结点是否是叶子结点的语句，对叶子结点进行计数就行了。)4.一棵二叉树以二链表来表示，求其指定的某一层k(k1)上的叶子结点个数。【上海大学、1(18)__________________________________________________________________________________________正确答案：(确答案：对某层上的结点进行运算，采用队列结构按层次遍历最适宜。核心语句段如下：BiTreeP=bt，；／／是列，元素是二叉树结点指针，容量足够大int0，rear：，leaf：0；／／frontrear是头和队尾指针，leaf叶子结点数int：1，level=1；Q[1]=P；／last是同层最右结点的指针，level是二树的层数while(front<=rear)if(1evel：=k&&!p一>Ichild&&!p>rchild)leaf++；／／叶子结点一>ichild)Q[++rear]-p一>Ichild／／左子女入队一rchild)Q[++rear]-p一>rchild／右子女入if(front==last)flevel++；／／同层最右结点已处理，层数增／／last移指向下层最右一元素；／／层数大于k后出运行}／／while0／k于二叉树的高度5.已知二叉树采用叉链表方式存放，要求对二叉树从1开进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号?给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法西北大学2003五13分)】__________________________________________________________________________________________正确答案(确答案：每个结点的编号大于其左右孩子的编号，结点左孩子的编号小于右孩子的编号，这正是后序遍历的顺序，故对二叉树进行后序遍历，在“访问根结点”时对结点进行编号。42题和16题后序遍历的非递归算法，可以参照。)6.设树T采用孩子兄链表表示，编写程序，计算树T的度，并写出算法思。【南京航空航天大2005七(10)__________________________________________________________________________________________

正确答案(确答案：在孩子兄弟链表表示中，结点和其兄弟的个数是该结点双亲的度，结点的度的最大值是树的度。设结点的度树的度设一队列，将树根入队，重复执行如下操作，直至队空：出队，沿兄弟链计数兄弟求出该结点双亲的度，计数兄弟的同时将其孩子入队，直至兄弟链空。若degree>maxdegree修改。7.树的存储结构如#defineMAX一TREE—SIZE100typedefstructCTNode{／孩子结点intstructCTNode*next;}*childPtr;typedefstruct{E1emtype；childPtr*firstchild;／／孩子链表头的指针}*CTBox;Typedefstruct{CTBoxnodes[MAX_rREE—SIZE]；intn;／n为结点数}*CTree写出求树的度的算法。【南京理工大学2004四5)__________________________________________________________________________________________正确答案(确答案：这是用孩子表示法存储的树，i个链表中孩子结点的数是结点的度。对n个结点，求出每个结点的度，取最大值为树的度。)8.设i是棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x的新结点插到t中已知地址为结点右侧作为结点右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学1996七15)__________________________________________________________________________________________正确答案：确答案：在线索二叉树上插入结点，破坏了被插入结点的线索。因此，插入结点时，必须修复线索。在结点y的右侧插入结点，为是后序线索树，要区分结点y有左子树的情况。本题假定y结点无右子树核心语句段如下if(y>ltag==0)／／有左子女{p=y一lchildif(p>rtag==1)p一>rchild=x；／／是y的左子女后序后继一ltag=1；x一>lchild=p；／／的左线索是y的左子女}else／／左子女{x>ltag=1一lchild=y一>1child／y的左线索成为x左线索if(y>1child一>rtag==1)／若y的后序前驱的标记为1y>1child一>rchild=x；／／则将y的序前驱的后继改为x}>rtag=1一>rchild=y；y>rtag=0y>rchild=x／x作y的子树)9.请用类C或用类Pascal语言编写算法编写在中序全线索二叉树T中的结P下插入一棵根为X的中序全线索二叉树的算法。如果尸左右孩子都存在，则插入失败并返FAI,SE；如果没有左孩子X作为尸的左孩子插入则X作为P的右孩子插入入完成后要求二叉树保持中序全线索并返回TRUE海大学2002七、1(10)】__________________________________________________________________________________________正确答案(确答案：在中序全线索T树的P点上，插入X为根的中序全线索化二叉树，要X有无左右子树进行讨论，并修改()子树上最左结点和右结点的线索。在中序线索树上查找某结点p的前驱的规律是：p一>ltag=1则p一>lchild指向前驱，否则，其前驱是p的子树上按中序遍历的最后一个结点；查找某结点p后继的规律是：若p一rtag=1p一>rchild就指向后继，否则，其后继是p的子树上按中序遍历的第一个结点。这里只讨论P有子女，将插为P右子女的情况。核心语句段如下一>ltag==0)／／有左子女x插p的右子女一ag==1)x一>lchild=P／／x无子树的线索(驱)Pelse／／寻找x的左子树上最左)的结点一>lchildwhile(q>ltag==0)q=q一>lchildq一>lchild=p}if(X一>rtag==1)>rchi．1d=P>rchild／／修改x的线索P的线索改为的右线索／找x右子树最右面的结点{q=x>rchildwhile(q>rtag==0)一>rchildq>rchild=P一rchild}一>rtag=0；p一>rch~Id=x；／／将x插为P的右子树}／／结束x插入为p的右子树)10.有序线索树T结点形式为：(LL，，RT,RL)，试编写非递归算法找到数据域为结点，并在其左子树中插入值为Q的已知新结X

注意：可A有左孩子或无左孩子，插入后考虑线索的状态应作何修改。【上海大学六(17分】__________________________________________________________________________________________正确答案(确答案：在中序线索树中，非递归查找数据域A结点(该结点存在，其指针为)将数据域为xQ结点插入左子树中无左子女Q为尸的左子女左线索成为Q的左线索，Q的右线索为PP左子树子树中最右结点的右线索是结点Q结点右线索是P。／／初值p=中线索二叉树根结点指针{while(P一LT==0&&p一>data!=A)p=p一>LL；／／沿左子树向下if(p>data==A)break；／找到数据域为A的点，退出循环wh~le(p一>RT==1)P=p>RL；／／还

没找到数据域为A的结点沿右线索找后P=P一RL)／／沿右子树向下if(P一>LT：=1)／／有左子树点插入作p左子女{Q一LL=P一>LL；一>LT=1／／P左线索作为Q的左线索else／／P左子树，应修改P的左子树最右结点的线索fQ一>LL=P一LLQ一>LT=0s=Q一LL／／成为p的子女，向原P的左子女while(s一RT==0)s=8一RL／／查找P的左子树最右边的结点s>RL：；／／原P左子树上最右结的右线索是新插入结点Qp->LT=0P一>LL=Q／／修改p的标记和指针Q>RT=1Q一RL=p；／将Q为p的左子女，其中序后继是p)11.编程序段，利用中序全线索树求其中任意结点p^的前后继结点，结果仍用p指出。要求描述结构和算法思路线索树不带头结点中序序列第一结点的左标志和最后结点的右标志皆为0(线索对应指针皆为空。【北京工业大2000七10分【哈尔滨工业大学2004五2(8)【上海交通大学2003(15分)__________________________________________________________________________________________正确答案(确答案：求中序全线索树任意结P的前序继的规则如下：P左子女，则左子女就是其前序后继；若P无左子女而有右子女则P的右子女就是前序后继；若P左右子女，这时沿P的右线索往上直到P的右标志0(非索这时若P右子女为空则表示是中序遍历最后一个结点，故指定结点无前序后继，否则，该结点就是指定结点的前序后继。程序段如下：一＆p一>Ich~id!=null)return(p一ichild)／／左子女p的前序后继elseif(p>rtag==0)&&p一>rch~id!=null)return(p一rchild)／／右子女是其前序后继else／／无左右子女。应沿右线索向上(其前序后继)某结点右标记0一rtag==1)p=p一rchild／／沿右向上一>rchild)return(p一rchild)；／指定结点的前序后继elsereturn(null)；})12.已一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学2001三8分)】__________________________________________________________________________________________正确答案确答案中序线索二叉树的指针是序遍历的核心语句段如下：一Ichild;／／p指二叉树的根结点叉树为空时向头结thrtwhild(p!=thrt){while(p一>ltag==0)p=p一>lchild／／沿左子女向下visit(tp)／／访问左子树为空的结点while(p一>rtag==l&&p一>rchild!=thrt){p=p一rchildvisit(。p)；}／沿右线索访问后继结点p=p一rchild；／／转向右子树})13.已指针p指向带表头的中根次序线索二又树中的某结点，试写一算法FFApq)该算法寻找结点p的父亲结g索二叉树的结点结构结点结构和空树结构分别为(LTAGLLINK且规定线索树的最左下结点的域最右下结点的RLINK域指向表头吉林大学1999二1(16)__________________________________________________________________________________________正确答案(确答案：在中序线索树中找结点的双亲，最简单情况是结点有左右子女，且左右子女都是叶子。结点的左子女的右线索和右子女的左线索都指向双亲。对于有左右子女且左右子女不是叶子的结点来说，则要利用中序线索树中线索“向上”指向祖先的特点：若结点结点子树中中序遍历最左下的结点，P左线索指向q若结点P是结点q左子树上中遍历最右下的结点，右线索指向是反过来，通过祖先找子女就容易了。另外，若结点后继是中序线索树的头结点，则应特殊考虑)14.给中序线索树的结点结构并画出一个具有头结点的中序线索树使其树结点至少应有6写一算法在不使用栈和递归的情况下前序遍历一中序线索树并分析其时间复杂性东南大学(20分)1997三(18)1998六(14分)【东北大学(20分)__________________________________________________________________________________________正确答案确答案头结点的中序线索树其头结点的指向二叉的根结点结点的域指向中序遍历的最后一个结点。而二叉树按中序遍历的第一个结点的和后一个结点的指向头结点。故从头结点找到根结点后，顺“后继”访问二叉树。在中序线索树中，找前序的后继，已在第78题行了详细的讨论，这里不再赘述。15.试写一算法对二叉树按前序线索化。【东南大学1999六15分__________________________________________________________________________________________正确答案：确答案：线索化是在遍历中完成的，因此，对于二叉树进行前序、中序、后序遍历，在“访问根结点”处进行加线索的改造，就可实现前序、中序和后序的线索化。核心语句段如下if(BT!=null)／／BT是叉树指针，是全局变量初值为null{if(BT一>ichild==null){BT一>Itag=lBT一>ichild=pre；／／设置左线索if(pre!=null＆＆一>rtag==1)pre一>rchild=BT；／设置前驱

的右线索if(BT>rchild==null)BT一rtag=l／／为建立右链作准备pre=BT／／煎驱后移if(BT一>itag==0)preOrderThreat(BT一ichild);／／左子树前序线索化preorderThreat(BT一rchild);／／右子树前序线索化})16.写中序线索二叉树的线索化过程知二叉树T)。【山东大学2000、2(10)】南京邮电学院1999(18分)__________________________________________________________________________________________正确答案：(确答案：在中序遍历中完成线索化。下面只给对“访问根结点”进行改造的语句段：if(T一>ichild==null){T一Itag=1T一>ichild=pre}／／左线索为if(pre!=null＆一>rtag==1)pre>rchild=T；／／给前驱加后继线索if(T>rchild==null)T一>rtag=1／／置右标记，为右线索作准备pre=T；／／前驱指针后移)17.已一个二叉树如下图者略修改结点(node)的连接方式以致可以不借助辅助堆栈实现中序遍历的非递归方法修改后的结点连接图并写出其实现中序遍历的非递归算法学2002五分】__________________________________________________________________________________________正确答案：(确答案：不借助堆栈实现中序遍历，必须解决如何查找后继的问题。使用线索树就可完成。为此，将结点结构修改为(1taglchild，data，rchild，rtag)。18.已中序线索二叉树T右树不空设计算法将S指的结点作为右子树中的一个叶子结点插入进去使之成为T的右子树(序序列)一个结点(时要修改相应的线索关系)工业大学五、2(8)__________________________________________________________________________________________正确答案(确答案若使新插入的叶子结点成T右子中序序列的第一个结点则应在T右子树中最左面的结点(为p)处插入使为结点P左子女则S的驱是T后继是P一>rchild／／p向T的右子女while(p一>itag==0)p=p一>Ichild；／／P最终指向T的右子树中最左面结点S一>itag=1；s一；／／是子，其左右标记均为1s一>ichild=T；一>rchild=p／s的前驱是根结点T后继是结点P一ichild=Sp->itag=0;／／将P的左女指向S，修改左标志为0)19.写算法求出中序线索二叉树中给定值为x结点之后继结点返回该后继结点的指针线索树中结点结构为：(1tag，lc，data，，aag)。其中，data存放结点的值；rc指向左、右孩子或该结点前驱或后继的指针ltag，rtag为标志域，若值为则lc，rc为指向左、孩子的指针；若值为1，则1crc为指向其前驱、后继结点的指针。【北京邮电大1996八20分)】__________________________________________________________________________________________正确答案：(确答案：首先查找值为的结点，设结点存在，且指p向该结点。若P>rtag=1，一>RC为空，则P>rc指向其后继若P一>rtag=0，点有右子女，则其右子树上按中序遍历的第一个结点是其后继。前面几个题已有涉及找中序后继的内容，这里不再赘述。20.设算法求中序线索二叉树中指针指结点的前驱结点的指针。【东南大2004五(10分)】__________________________________________________________________________________________正确答案(正确案中序线素二叉树中指针P指结点的前驱结点的特征是若P->lchild指向其前驱否则左子树上按中序遍历的最后结点是其中序前驱if(p一>itag==1)q=p一>ichild；／／若P的标志为1用其左指针指向前驱else(q=p>lchildwhile(q>rtag==0)q=q>rchild／／P前驱为其左子树中最右下的结点}return(q);)21.设序线索树中结点构造为LtagLchildRtag)中Ltag为时、Rchild分为儿子指针；否则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点p^的直接前驱q的法。【武汉交通科技大学1966、1(13分__________________________________________________________________________________________正确答案：确答案：二叉树的后序遍历是“左—右一根”，因此，若结点有右子女，则右子女是其后序前驱，否则，左子女(左线索)向其后序前驱。核心语句如下：一>Rtag==0)return(p->Rchild);／／若P有子女，则右子女为其前驱elsereturn(p一>Lchild)；／若P无右子女，左子女或左线索就是P的序前驱)22.用法说明在对称序线索树中如何任意给定的结点直接找出该结点的对称序后继山东大学1999六、3(10)

__________________________________________________________________________________________正确答案(确答案：中序线索树任意给定的结点P中后继的特点是，若则P->rchild向其后继，否则，其右子树最左结点是其中序后继。)23.写在中序线索二叉树中找指定结点在后序下的前驱结点的算法。【河海大学1998七10分)__________________________________________________________________________________________正确答案：(确答案：在后序序列中，若结点有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点左右子女均无，设其中序左线索指向某祖先结点f(p厂右子树中按中序遍历的第一个结点)若f有左子女，则其左子女是结P在序下的前驱；若厂无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女(时左子女是P的前)还有一种情况，若P是中序遍历第一个结点，结点P在序和后序下均无前驱。24.设序线索二又树的结点由五个域构成：info：给出结点的数据场之值。当LT为1时，则给出该结点的左儿子之地址当为0则给出按中序遍历的前驱结点的地址LT标志域为或为0RL：当RT1时则给出该结点的右儿子的地址；当RT为，则给出按中序遍历的后继结点地址。RT：志域为0或l请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点p的按后遍历次序的后继结点的地址q设该中序线索二叉树的根结点地址为r。另外，请注意必须满足：额外空间的使用只能为O(1)(2)序为非递归。【上海交通大学2000(20)】__________________________________________________________________________________________正确答案确答案中序线索二叉树中求某结点的后序后继g要知道的双亲结点f的信息。(序线索树的性质；P是f的左子女，DJf是p最右子孙的右线索；若p是f的右子女，f是p的最左子孙的左线索。)到后，若p是f的右子女，则p的后继是若p是f的子女，且无右子女，则p的继也是f;若pf的左子女，且右子女，f的右子树中最左边的叶子结点是的后继。因此，算法思路是，先找p的双亲f,据p是f左／右子女再确定的后序后继。)25.写按后序序列遍历中序线索树的算法。【东南大学2000(15分)】__________________________________________________________________________________________正确答案(确答案上题讨论了中序线索树中查找结点p的后序后继问，本题要求在中序线索树上进行后序遍历。因后序遍历是“左一右一根”，最后访问根结点，即只有从右子树返回时才能访问根结点，为此设一标志flag，当其1时表示从右侧返回，可以访问根结点。为了找当前结点的后继，需知道双亲结点的信息，在中序线索树中，某结点最左子孙的左线索和最右子孙的右线索均上指双亲或祖先，因此设立两个函数LeftMostRightMost求结的最左和最右子孙为了判定是否是从右子树返回再设一函数IsRightChild面是求结点t最子孙的左线索BiThrTreep=twhile(p一>Itag==0)p=p>Ichild；／／沿左分支向下if(p->ichild!=null)return(p一Ichild)；elsereturn(null)下是求结点t最右子孙的右线索：BiThrTreep=twhile(p一rtag==0)p=p>rchild／沿右分向下if(p->rchild!=null)return(p一rchild)；elsereturn(null)；下面的数，若t是的孩子返回1则返回0intIsRightChild(BiThrTreet(father=LeftMost(t)if(father&&father一>rchiid==t)return(1)；elsereturn(0)；voidPostOrderInThr(BiThrTreebt)／／后序遍历中序线索二叉bt{BiThrTreefatherflagwhile(p!=null){while(p一>itag==0)p=P一>ichild；／／沿左分支向下if(p一rtag==0)flag=0／／左子为线索，右孩子为链，相-3于从左返回elseflag=1；为叶子相当于从右返回while(flag==1){visit(+p)／／访问结点if(IsRightChild(pfather)){p=father；flag=1；／／改P向双亲／／左子女，用最右子孙的右线索找双亲{p=RightM。st(p)；if(p&&p一>；flag=0；}}／while(flag==1)if(flag==0&&P!=null)p--p一>rchild；／转向当前结点右分支}／结束PostorderInThr)26.从盘上输入一串正整数，最后输入一为结束标志。如：7，122，98，46…，，1请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为：

其中：data域结点的数据场ltag=0，那left中存放的是该结点的左儿子结点的地址。ltag=1，那么域中存放的是该结点按中序周游次序的前驱结点的地址。，那么fight域存放的是该结点的右儿子结点的地址。rtag=1，那么fight中存放的是该结点的按中序周游次序的后继结点的地址。【上海交通大学二20)__________________________________________________________________________________________

正确答案(确答案：二叉排序树建立过程如下：设输入第一个数据，用二叉排序树根结点指针st向该结点根结点的数域赋值将右子女指针和左右标记初始化bst一>left=-bst>right=nullbst一>ltag=bst>nag=1。接着对输入数据做如下处理：若该数据小于根结点的数据，则在左子树上查找其插入位置，否则在右子树上查找其插入位置。查找时记住其双亲结点的指针厂。插入的结点一定是叶子，设p指已申请空间的叶子结点。p>data＜f-data，f左子女插入，否则，f右子女插入，同时，修改双亲和叶子的线索和标记。核心语句段如下：cin>>x；／输入数据／／flag是束标记{if(bst==null)／／处理根结{bst=new(BstNode)／／建立根结点并初始化一>left=bst>right=nullbst->itag=bst->rtag=1bst->data=x}else／非根结点的插入s=bst／／双亲指针while(s){if(s一>data>x){f=s；一>left；}／沿左分支向下elseif(S->dataright；／／沿右分支向下else{tout<<输入数据不允许重复”<data=x／／申结点空间，填入数据if(f>data>x)／插入为左子女{p>left=f一>left；f一left=p；一>ltag=0／／修改双亲线索和标记p->itag=p->rtag=lp->right=f／／建立叶子结点的线索和标记}else／／插入为右子女{p一right=f一>rightf->right=p一>rtag=0一>Itag=p一>rtag=l一left=f}cin>>x／／输入数据}／／else结束非根结点的插入／／结束while(x!=flag))27.给一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为Huffman。(1)出构造Huffman的算法。(2)定项及相应的权如下表，画出执行上述算法后得到的Huffman。(3)用C言编写构造Huffman树的程序。【浙江大学七18分)】_____________________________________________________________________