各大高校真題1000第六章二叉樹

已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( B.-A+B*CD/E D.-+A*BC/DE19993（2算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ 【中山大學(xué)1999一、5】 ， A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F- 20008（1.5 【南京理工大學(xué)1999一、4（1分 樹是結(jié)點(diǎn)的有限集合，它（(1）Tm（m>0）個(gè)(（2）)的集合T1，T2mTTi，TiT（1≤i≤m。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的(（3）)。二叉樹與樹是兩個(gè)不同的概念，二叉樹也是結(jié)（(5)（1）(4)A.有0個(gè)或1個(gè)B.有0個(gè)或多個(gè)C.有且只有一 D.有1個(gè)或1個(gè)以A.互不相 C.允許葉結(jié)點(diǎn)相交D.允許樹枝結(jié)點(diǎn)相A. （5）A.豐滿樹 D．20017(3）D．7【哈爾濱工業(yè)大學(xué)20012（2設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的 【北方交通大學(xué)2001一、16（2分】 【西安交通大學(xué)1996三、A． B． 設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為( )【福州大學(xué)1998一、5(2分)】 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ 【青島大學(xué)2002二、1（2分】 D．n/(m-1)- 【南京理工大學(xué)2000一、11（1.5分】A．二叉樹的度為2 B．一棵二叉樹的度可以小于2 【中山大學(xué)1998二、7（2分【北京理工大學(xué)2001六、5（2分】 B．2I-1- C．2I- D．2I- 【南京理工大學(xué)1999一、19（2分 C．11至1025之間 D．10至1024之間19．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( 20．對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹,其高度為（ 【武漢交通科技大學(xué)1996一、5(4分)】 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ 【南京理工大學(xué)1996一、8（2 hmk（）個(gè)結(jié)點(diǎn)。(1=<k=<h)20004（2 在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ 【北京工商大學(xué)2001一、3(3分)】 高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（ 【山東大學(xué)2001二、3(1分)】 C．2k-1 一棵樹高為K的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)【南京理工大學(xué)1998一、3（2分】A．2k–1 B.2k-1–1C.2k-1 D.2k 利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（2001五、5（2】A．指向最左孩子B．指向最右孩子C．空D．非空點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用()次序的遍歷實(shí)現(xiàn)編號(hào)?！颈本├砉ご髮W(xué)2000一、4（2分】A.先序 B.中序 C.后序 D.從根開始按層次遍歷 ).【北京理工大學(xué)2001六、6（2分】 B.中序序列 C.后序序列30．若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用()遍歷方法前序 D．按層次【北京航空航天大學(xué)1999一、4（2分】 【北方交通大學(xué)2001一、23（2分】雙親表示法B．C．D一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是 【北京工業(yè)大學(xué)一、2(2 已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果（ B．FEDCBA C．CBEDFA 【浙江大學(xué)1999四、24已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷是（ 【山東大學(xué)2001二、7(1 某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是： 200014（1.5 【南京理工大學(xué)2000一、15（1.5分 200121（2】A、 B、 C、 D、 ）【北京郵電大學(xué)2001一、2（2 )編號(hào)的A.B.C.后序遍歷序列D19981(2 D．(1)、(2200110（1.5】 D．根結(jié)點(diǎn)無右孩子的二叉樹EF樹 20002樹 D．中序和后序相同，而與先序不同200125（24 【北方交通大學(xué)2001一、22（2分】 點(diǎn) B.哈夫曼 樹

D.每個(gè)結(jié)點(diǎn)只有一棵右子 E．以上答案都不對(duì)【西安交通大學(xué)1996三、 A.不確 B. C. D. 【合肥工業(yè)大學(xué)1999一、5（2分 )A.0 B.1 C.2 D.20005（2 B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了 D．使二叉樹的遍歷結(jié)果唯一【南京理工大學(xué)1998一、5（2分 B．邏輯和存儲(chǔ) C．物理 D．線性【西安電子科技大學(xué)1996一、9（2 D．n【中山大學(xué)1998二、8（2分】53．（ C．后序線索樹【中科院計(jì)算所1999一、1（2分】 A．前（先）序線索二叉樹中求前（先）序后繼B．5設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏? C．n+1 D．n+2199810（2如果T2TTT2中結(jié)點(diǎn)的（ D．層次序【西安電子科技大學(xué)1996一、2（2由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹 D．5【北方交通大學(xué)20016（2由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹 【北方交通大學(xué)2001一、7（2分】（A．二叉排序樹B．C．AVL樹D 正確n 結(jié)點(diǎn)數(shù)B．葉結(jié)點(diǎn)數(shù)C．非葉結(jié)點(diǎn)數(shù)D．2的結(jié)點(diǎn)數(shù)E．nF．需要對(duì)n個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)插入 G．需要n個(gè)關(guān)鍵字的查找概率表 【中科院計(jì)算所2000一、2（2分】A（00011011）B（010011）C（010110111）D（101000001） D．{b,c,aa,ac,aba,abb,abc}20016（2當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[l..n]中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（ 【南京理工大學(xué)1999一、18(2分】 B.A[2i+1](2i+1 則二叉樹中第i個(gè)結(jié)點(diǎn)（i從1開始用上述方法編號(hào)）的右孩子在數(shù)組A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i- 從下列有關(guān)樹的敘述中,選出5條正確的敘述(共5分) B．當(dāng)K≥1時(shí)高度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。19978（220026（119954（11996一、6（1】19991-1（21996二、2(32i(2in)2i+1（2i+1<n199711（2】20015（11997一、7（1】19973(2（2（a）1+1（k≥1199596,97一、7（119956（1】19995（2 針。()19996（1二叉樹由_(1)，(2)_，_(3)19985（3樹在計(jì)算機(jī)內(nèi)的表示方式有_(1)，_(2)，_(3)?！竟枮I工業(yè)大學(xué)20004(3 【合肥工業(yè)大學(xué)1999三、7（2分a+b*3+4*（c-d）1)_a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_(2)。【西南交通大學(xué)2000一、6】 【燕山大學(xué)1998一、9(1 【燕山大學(xué)1998一、4（1分20002（16%/3 20014（14%/519995（4H_(1_(2)；HN是(3)?！局锌圃河?jì)算所1998一、3（3分）1999二、4（3分【中國科技大學(xué)1998一、3(4分】10．在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是 20023（4在完全二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件 20006（2n(1)_1(2)_個(gè)分支（結(jié)點(diǎn)和(3)_個(gè)葉子，該滿二叉樹的深度為_(4)2000一、6（3） 【北方交通大學(xué)2001二、1N0,2N2,N0設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù) 設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A[1:N]中，其下標(biāo)值最大的分支結(jié)點(diǎn) 199732 個(gè)葉子結(jié)點(diǎn)【合肥工業(yè)大學(xué)1999二、6（2分 個(gè)葉子結(jié)點(diǎn)【合肥工業(yè)大學(xué)2001三、6（2分 【南京理工大學(xué)1997三、2（1分n1,n2和n3B的左子樹中有(1)_個(gè)結(jié)點(diǎn)，右子樹中有_(2)個(gè)結(jié)點(diǎn)。20009（3點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是(1)_i_(2)（根所在的層次120012（2】203020013（2A3BABh2-319996（2n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為20003(2 【北京科技大學(xué)1998一、320013(2 個(gè)空鏈域【重慶大學(xué)2000一、8 【西南交通大學(xué)2000一、1 200162T2001三、2(2n（n1）個(gè)結(jié)點(diǎn)的各棵樹中，其深度最小的那棵樹的深度是_(1)。它共有_(2)個(gè)葉子結(jié)點(diǎn)和_(3)個(gè)非葉子結(jié)點(diǎn)，其中深度最大的那棵樹的深度是_(4)，它共有_(5)個(gè)葉子結(jié)點(diǎn)和FEBGCHD，則它的后序序列是_(1)。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是_(2)1997二、(6先根次序周游樹林正好等同于按_(1)周游對(duì)應(yīng)的二叉樹，后根次序周游樹林正好等同于按(2)_19991（4】 棵樹【北京大學(xué)1997一、2（4分】 【合肥工業(yè)大學(xué)2000三、7（2分】，左子樹中有_(2)，右子樹中有_(3)1996二、1（6】_(1);后序遍歷二叉樹時(shí)，訪問的結(jié)點(diǎn)序列為_(2)?！灸暇├砉ご髮W(xué)19993（4 【青島大學(xué)2000六3(2分abc，問有_(1二叉樹分別是_(2)2000一、5（3】 行排序的過程。【西安電子科技大學(xué)1999軟件一、4（2分】 【重慶大學(xué)2000一、920002 周游對(duì)應(yīng)的二叉樹【山東大學(xué)1999二、１(４分)】 ?！局袊嗣翊髮W(xué)2001一、4（2分）】一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個(gè)數(shù)為：20021（4n1994是y的左孩子。則確定x的后繼最多需經(jīng)過中間結(jié)點(diǎn)（x）20008（1.5線索二元樹的左線索指向其，右線索指向其20003(2(lchild,rchild分別代表左，右孩子)x^.ltag:= ;x^.lchild:= ;y^.ltag:= y^.lchild:= ;x^.rtag:= ;x^.rchild:= IF(x^.lchild<>NIL)AND(x^lchild^.rtag=1)THENx^.lchild^.rchild:= 19977（9 【北京理工大學(xué)2001七、4（2【長沙鐵道學(xué)院1998二、3(2分) 有數(shù)據(jù)WG={7，19，2，6，32，3，21，10Huffman_(1)，帶權(quán)路徑長度WPL_(21999三、6（4】6:a,b,c,d,e,f,2,3,4,7,8,9，試構(gòu)造一棵設(shè)n0為哈夫曼樹的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹共有57．①二叉樹用來表示表達(dá)式，因?yàn)樾枰４娓髯訕涞闹?，修改二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為(Lchild,Data,Val,Rchild)。其中Lchild,RchildVal算，且已表示成相應(yīng)的二叉樹。算法所計(jì)算的表達(dá)式值放在根結(jié)點(diǎn)的Val域中。PROCPostorder-eval(t:ptrType)BEGINIF(t!=NULL)BEGIN(1);(2)CASE‘+’:t^.Val:=t^.Lchild^.Val+t^.Rchild^.Val;BREAK;‘-’:t^.Val:=t^.Lchild^.Val-t^.Rchild^.Val;BREAK;‘*’:t^.Val:=t^.Lchild^.Val*t^.Rchild^.Val;BREAK;‘/’:t^.Val:=t^.Lchild^.Val/t^.Rchild^.Val;BREAK;otherwise:(3);BREAK;ENDCASE②PROCDelete(x:datatype,A:tree)BEGINtempA:=(4) WHILE(tempA^.Item!=x)AND(tempA!=NULL)IF(x<tempA^.item)BEGINr:=tempA;tempA:= ;親

IF IF(tempA^.Lchild!=NULL)AND(tempA^.rchild!=NULL)BEGINt:=tempA;q:=tempA^.Rchild;WHILEq^.Lchild!=NULLDOBEGINt:=qq:=q^.Lchild;END;t^.Lchild:=(7) ;//刪去qq^.Lchild:=tempA^.Lchild;IFtempA^.item<r^.item)r^.Lchild:=(8)_ELSEr^.Rchild:=q//用qELSEIF(tempA^.Lchild!=NULL)IF(tempA^.item<r^.item)ELSEELSEIF(tempA^.Rchild!=NULL)IF(tempA^.item<r^.item)r^.Rchild:=ELSEELSE//tempAIF(10)_r^.Lchild:=NULLELSEr^.Rchild:=NULLEND;【中山大學(xué)1999四、(20分)】TYPEnode=RECORDkey:keytype;l,r:link;END;VARall:boolean;n:integer;root:link;BEGIN(1) PROCchk(t:link;m{t所指結(jié)點(diǎn)應(yīng)有序號(hào)}:integer)BEGIN(2) {建二叉樹，其根由root指出}n:=num(root);{求結(jié)點(diǎn)數(shù)}all:=true;chk(root,1);writeln）ELSE）END；【北京工業(yè)大學(xué)1997二、2(10typedefstruct{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,if{p=DELQ(Q); ;p- ; if(p->lchild) ;if(p->rchild) } 個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedefstruct{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node{if(t->lchild!=NULL)if(1) N2++;elseNL++;elseif(2) NR++;else(3) ;if(t->rchild!=NULL) }/*callform:if(t!=NULL)2000310 為根的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最后返回。{if {if(p->lchild==null);else;if(p->rchild==null)if(lh>rh)hi=(6)；else;else;;} }//【南京理工大學(xué)19978（15將隊(duì)頭元素返回并退隊(duì)，notempty在隊(duì)不空時(shí)返回true，否則為false，將算法補(bǔ)充完整:PROCIF(1)THEN[write(p＾.data);(2) ＾.data); WHILEnotempty()[r:=delx();processnode(r＾.lchild);processnode((4) ENDP;【南京理工大學(xué)1999三、5（4分】63【程序說明】本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示（編者略typedefstructnode*tree;structnode{intdata;treelchild,rchild;}exchange(treet){treer,p;treestack[500];inttp=0;while {r=p->lchild;p->lchild=p->rchild;p->rchild=r }19942（15TYPEpointer=^tnodetp;tnodetp=RECORDdata:char;llink,rlink:pointer；END;linknodet=RECORDdata:pointer；next;linkstack；END;PROCunknown(VARt:pointer);VARBEGINIFp<>NILunknown(p^.llink);unknown(p^.rlink);]unknown1PROCinistack(VARFUNCemptyIF(2) THENempty:=trueELSEempty:=false;gettop:=(3) FUNCpop(VARs:linkstack)：pointer;VARp:linkstack;pop:=s^.next^.data;p:=s^.next;(4) PROCpush(VARs:linkstack;x:pointer);VARp:linkstack;new(p);p^.data:=x;(6) PROCunknown1(VARVARp,temp:pointer;finish:boolean;inistack(s);finish:=false;p:=t;WHILEp<>NIL[temp:=p^.llink;p^.llink:=p^.rlink; ; IF THEN[p:=gettop(s);temp;=pop(s);]ELSEUNTILENDP200025具有n個(gè)結(jié)點(diǎn)的完全二叉樹，已經(jīng)順序存儲(chǔ)在一維數(shù)組A[1..n]中，下面算法是將A中順序存儲(chǔ) TYPEar=ARRAY[1..n]OFpointer=RECORDdata:datatype;lchild,rchild:pointer;END;PROCEDUREbtree(VARa:ar;VARp:pointer);VARPROCEDUREcreatetree(VARt:pointer;i:BEGIN;THEN)ELSETHEN)ELSEj:=(6) END;【北京郵電大學(xué)199815 structElemTypedata;BinTreeNode*leftchild,*rightchild;

GA（B（D，E（G，C（，F(xiàn)元素pvoidCreatBinTree(BinTreeNode*&BT,charls){Stack<BinTreeNode*>s; BinTreeNodeintk;istreamins(ls)； //把串ls定義為輸入字符串流對(duì)象ins;charch;ins>>ch; //從ins順序讀入一個(gè)字符while(ch!=‘#’){ case‘(’: ；k=1;case‘)’: case’,’: default:p=newBinTreeNode;(3);p->leftChild=NULL;p->rightChild=NULL;if(BT==NULL)(4)；elseif(k==1)top(s)->leftChild=p;elsetop(s)->rightChild=p;} }2001(15FUNCTIONequal(l:pointer):boolean;VARp,q:pointer;result:BEGINresult=true;p:=l^.link;q:=l^.pre;WHILE(p<>q)AND((1) IFp^.data=q^.dataTHENBEGIN ; ;ELSEresult=false btree*b;{btree*stack[20],*p；inttop;if{top=1;stack[top]=b;while(top>0){p=stack[top];top--if(p->rchild!=null) ; }if(p- ;(4)200110

PROCEDUREVARstack:ARRAY[1..20]OFbtree;top:integer;p:btree;IFb<>NILBEGINtop:=1;stack[top]:=b;WHILEtop>0DOIFp^.rchild<>NILTHENBEGIN;(2)_;IFTHEN (3)4)ENDENDENDPROCEDUREcreatBT(i,j,x,y:integer;VARs:link);VARk,L:integer;BEGINs:=IF(1)BEGINnew(s);s^.data:=a[i];k:=x; DOk:=k+1;L:=(3) IFk=xTHENs^.lchild:=NIL;ELSE(4) IFk=yTHENs^.rchild:=NIL; END;199619PROCinorder(bt:bitreptr);inistack(s); WHILENOTempty(s)[WHILEgettop(s)<>NILDOpush(s,gettop(s)↑.lchild); IFNOTempty(s)THEN[visit(gettop(s)^);p:=pop(s);(3) ENDP;{inorder}【北京輕工業(yè)學(xué)院1999一、(9分)】typedefstruct {chardata;structnodevoidvst(bitree {bitreep;p=bt;initstack(s); while(p||!empty(s)) /*棧s不為空*/if(ppushs,p elsep=pop(sprintf(“%c”,p->data /*棧頂元素出棧200010intdepth(bitreebt) /*bt為根結(jié)點(diǎn)的指針*/{intif(bt==NULL) )(3) 200011PROCpreorder(a);BEGINtop:=0;WHILE(t<=n)OR BEGINWHILEt<=nDOBEGINwrite(a[t]);top:=top+1;s[top]:=t;t:=(2)_;END;IFtop>0THENBEGINt:=s[top]*2+1;top:=(3);END;END;19983（6TYPEbitreptr=^bnodetp;bnodetp=RECORDdata:datatype;lchild,rchild:bitreptrTYPEstacktyp=RECORDdata:ARRAY[1..maxsize]OFbitreptr；top：0..maxsize；END；PROCEDUREposterorder（bt：bitreptr；WHILEp<>NILDOBEGINS.top:=S.top+1;IFS.top>maxsizeTHENELSEBEGINS.data[S.top]:=p；(1);IFS.data[S.top]^.rchild<>NILTHENELSEBEGINREPEATwrite(S.data[S.top]^.data);S.top=S.top-UNTILS.top=0ORS.data[S.top]^.rchild<>S.data[S.top+1];IFS.data[S.top]^.rchild<>S.data[S.top+1]THEN(3); END；19991(7#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int{TNODE*root;if(argc<3)exit0;}TNODE*restore(char*ppos,char*ipos,int{TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL; ;rpos<ipos+n;rpos++)if(*rpos==*ppos)break; ,kptr->rlink=restore((5) returnptr;}{if(ptr=NULL)postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr-200010TYPEtree=^nodenode=RECORDdatainteger;leftright:treeEND;以下過程實(shí)現(xiàn)對(duì)二叉樹t前序遍歷的非遞歸算法：PROCEDUREpreorder(t:treeVARstack:ARRAY[1..100]OFtree;nd:tree;top:integer;BEGINtop:=1;stack[top]:=t; BEGINnd:=stack[top];top:=top-1;writeIF(nd^.right<>NIL)THENBEGINtop:=top+1;(2) IF(3) THENBEGIN(4) END;20001（8data，lchild、rchildltag,rtag1索，O是指向孩子的指針。while((1) {while((2) )p=(3) ){p=(5) p=(6)_;}20001（6PROC(1)IFp＾.rtag=0THEN DOq:= 19981（610c語言的具體語法與約定，線索化前所有的標(biāo)志tag。/*pretreenull*/thread_inorder(tree){{thread_inorder((1)if(tree->lchild==(2)){tree->ltag=1;tree->lchild=pre;}if((3)==null){(4);(5);}pre=p;thread-inorder((6)}20015（6node格處填上正確的語句。設(shè)線索二叉樹的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為(lflag,left,data,right,rflag)，其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驅(qū)；rflag=0，right指向其右孩子，rflag=1，right指向其后繼。{if(nodeif )*x=node->right;else*x=node-}next(bt,node, if(node!=bt&&if(node->rflag) else{dot=*x; ;while(*x==node);*x=t;1996820011（5】三、該樹的多重鏈表中有多少個(gè)空鏈域?為什么?【長沙鐵道學(xué)院1998四、1(6分)】1998319981（5K1開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，求：各層的結(jié)點(diǎn)的數(shù)目是多少？1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(3分)2i（若存在）19991220015（4（N＞０ 2001五、(８分)19991（320003（420013（3頂點(diǎn)編號(hào)的規(guī)則（按何種順序編號(hào)1992一、1（3】20013(12分)20012(1520016（2Sbinarysearchtree)中,任意一條從根到葉結(jié)點(diǎn)的路(8分)】n0和n2n0=f(n219988199710(1)試問這種二叉樹的結(jié)點(diǎn)總數(shù)是多少？（5分）n2(li 199515最大值和最小值各為多少？【北京郵電大學(xué)1996一、1（4分】1999一、2（7】 系可用公式表示s=(1+1/n)u-1,n>=1?！厩迦A大學(xué)1998四、(10分)】一棵非空的有向樹中恰有一個(gè)頂點(diǎn)入度為0,其它頂點(diǎn)入度為1,但一個(gè)恰有一個(gè)頂點(diǎn)入度(union是合并運(yùn)算，在以前的書中命名為merge) 按i和j為根的樹的高度實(shí)現(xiàn)union(i,j),高度大者為高度小者的雙親 200115【天津大學(xué)19991，2，3（即n=3）19981(71998二、2（5(10分)】DBEAFGCDEBGFCA19983ABDGECFH，中序序列為：DGBEAFHC1996820013（420011（4【大連海事大 2001九、(８分) 二、4（5分唯一確定此二叉樹?若不能,試畫出兩樣具有同樣上述遍歷序列的二叉樹.【武漢交通科技大學(xué)1996二8（3分】先序序列與后序序列相同2）3）先序序列與中序序列相同4）1999419951,2（7 2）先序遍歷和后序遍歷【北京理工大學(xué)1999三(6分)1）先序序列和中序序列相同2） A A GHIJ GHIJ P個(gè)它指向空樹，圖中指針root用以指向二叉樹的根結(jié)點(diǎn)。問題：【上海海運(yùn)學(xué)院1997（13分】ABDFCEGHBFDAGEH 后序：Itag=

199715已知二叉樹的先序序列: 中序序列:HBGEACF,試構(gòu)造該二叉20012（4【山東師范大學(xué) 五、1(2分)19995棵二叉樹?！緩B門大學(xué)1998六、1（7分)】19986【東南大學(xué)1996一、2（7分 1998一、3已知一棵二叉樹的后序遍歷序列為EICBGAHDF，同時(shí)知道該二叉樹的中序遍歷序列為CEIFGBADH，試畫出該二叉樹【重慶大學(xué)2000 19978GFBEANHMGEBFHNMA19995（519981(6GDBEIHFCA中序遍歷序列：DGBAECHI20001（20%/3中序：ABCDEFGHI 后序：ACDBHJIGF19981（10后序序列：CDEBFHIJGAMLONK【合肥工業(yè)大學(xué)20001（5(1)按先根序遍歷二叉樹順序?yàn)锳BCDE。__CDE_GHI_KCB__FA_JKI_EFDB_JIH_A20021（6先序序列:_B ICEH KFIA EJC后序序列： FBH A【西安電子科技大學(xué)2000計(jì)應(yīng) 五、2（5分)先序：_BC_EFG_IJK_中序：CBED_GAJ_H_后序：_E_FD_J_L_HA20011（5先根序遍歷_23_5_7中根序遍歷3_41_78后根序遍歷_42__65 【東北大學(xué)1996一、3（5分20002（42001二、3（5】下表中M﹑Ni=1，2，3，4M﹑N比m先被訪問，則在（3，2）格內(nèi)打上對(duì)號(hào)NMNMNMNM【南京理工大學(xué)2001四、(10分)】ABCDEFGHIJKL19964（6 數(shù)20012（4三n1n2002375801JHFDBACEGI 0094000001994(8【山東大學(xué)1999六、１(２分】ABE DABE DIGJ P 002375801JHFDBACEGI000940000074p的直接后繼結(jié)點(diǎn)，請(qǐng)寫出相關(guān)浯句。結(jié)點(diǎn)結(jié)構(gòu)為(ltag,lc,data,rtag,rc)?！疚鞅贝髮W(xué)2000二、6（5分】接前驅(qū)？【西北工業(yè)大學(xué)1998一、4（4分】ABCDEFGHIJK0000000000020578000000000000000003406009001997一、5（419985（4】2001七、1（5分)】20001020022（10】HUFFMANHUFFMAN199510設(shè)用于通信的電文由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別1999(5長壓縮多少？【北京郵電大學(xué)2001四、2（5分)】WPL1993（12實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)?！敬筮B海事大學(xué)1996五、2(80.03，0.20，0.06,0.22，0.02，0---7Huffman2000一、2（419965(2W1,W2,…，Wmk,199910wpl1992一、3】BEGINtop:=1;s[top]:=T;WHILEs[top]<>NILDOBEGINs[top+1]:=s[top]^.lchild;top:=top+1;IFtop>1THENBEGINtop:=top-1;WRITE(s[top]^.data);s[top]:=s[top]^.rchild;END;UNTILtop=02000102000三、2（10】20013（10++/V1999141至N2000122000141997四(16樹，根由tree指向?！灸暇├砉ご髮W(xué)1998七、1（6分】式，其中i表示結(jié)點(diǎn)的編號(hào),L(i)的值是i的左兒子的編號(hào)，R(i)的值是i的右兒子的編號(hào)。若L(i),R(i)的值為0，表示結(jié)點(diǎn)i無左兒子或右兒子。試設(shè)計(jì)算法：你所采用的語言名稱1992三、(13分)】T199915ABFABF E1A262B343C004D505E006F077G00也有三個(gè)字段：data，lchild，rchild。所不同的是，lchild和rdhild為integer型，分別用于存儲(chǔ)左右孩子的下標(biāo)，如果沒有左右孩子，則相應(yīng)的值為0。例如，下面左圖所示的二叉樹的靜態(tài)二叉n20003（8】. TYPEbnode=RECORDdata:datatype;lch,rch:btre【西北大學(xué)2001五高度（要求用非遞歸方法實(shí)現(xiàn)2000九】pqr20003（121994六（15】20001】20015（8】x199620打印數(shù)據(jù)域值為x的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域。如果根結(jié)點(diǎn)的xx印。例如右圖所示的二叉樹，則打印結(jié)點(diǎn)序列為A、C、E。

A

D 的元素?！旧綎|科技大學(xué)2002四、(10分)】 設(shè)一棵完全二叉樹使用順序存儲(chǔ)在數(shù)組bt[1..n]中,請(qǐng)寫 出進(jìn)行非遞歸的前序遍歷算法【西安電子科技大學(xué)1998四(8分)】ABCDEF ABCDEFDCADCAFBE-302--19992（824．對(duì)于二叉樹的鏈接實(shí)現(xiàn),完成非遞歸的中序遍歷過程。【中山大學(xué)1999五、(15分)】序遍歷二叉樹【西安電子科技大學(xué)1999計(jì)應(yīng)用四(10分)】TYPEARRAY1..maxn]OFRECORD ABCDEFGHI240008000356079000T=A（B（D，E,(#,G)，C（#，F(xiàn)（H，I）度為1的結(jié)點(diǎn)數(shù)目的算法。二叉鏈表的類型定義為：TYPEbnodetp=RECORDdata:char;lchild,rchild:bitreptr20002（1219991（8,1996五、(1420011519993（12push（S，P，pop（StopS）1996】TYPEbnodetp=RECORDdata:integer;lchild,rchild:bitreptrEND;data501998(10來。如右圖：（PASCAL。1999(6right值，并假定二叉