【文章內(nèi)容簡(jiǎn)介】 195 C. 197 D. 1965. 二維數(shù)組A的元素都是6個(gè)字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圈從1到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲(chǔ)敘述中（）內(nèi)的正確答案。（1）存放A至少需要（ E ）個(gè)字節(jié)；（2）A的第8列和第5行共占（ A ）個(gè)字節(jié)；（3）若A按行存放，元素A[8，5]的起始地址與A按列存放時(shí)的元素（ B ）的起始地址一致。（1） （2） （3）[8,5] [3,10] [5,8] D. A[0,9]6. 設(shè)A是n*n的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為( B )。(il)/2+j (jl)/2+i (jl)/2+i1 (il)/2+j1第6章 樹(shù)和二叉樹(shù)一、考研知識(shí)點(diǎn)（一）樹(shù)的概念（二）二叉樹(shù)（三）樹(shù)、森林（四）樹(shù)與二叉樹(shù)的應(yīng)用哈夫曼（Huffman）樹(shù)和哈夫曼編碼二、考研真題（一）選擇題1.（09年）給定二叉樹(shù)如圖所示。設(shè)N代表二叉樹(shù)的根，L代表根結(jié)點(diǎn)的左子樹(shù)，R代表根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列為3,7,5,6,1,2,4，則其遍歷方式是（ ）。 分析：答案是D，此題考查二叉樹(shù)的遍歷。2.（09年）已知一棵完全二叉樹(shù)的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是（ ）。 分析：答案是C，此題考察二叉樹(shù)的性質(zhì)2以及完全二叉樹(shù)的概念。3.（09年）將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來(lái)的森林中，u和v可能具有的關(guān)系是（ ）。 、II和III分析：答案是B，此題考查樹(shù)與二叉樹(shù)的轉(zhuǎn)換，因?yàn)閡是v的父結(jié)點(diǎn)，若v是u的左子樹(shù)，則u與v是父子關(guān)系，若v是u的右子樹(shù)，則u與v是兄弟關(guān)系。4.（10年）下列線索二叉樹(shù)中（用虛線表示線索），符合后序線索樹(shù)定義的是（ ）。分析：答案是D，此題考查二叉樹(shù)的線索化。5.（10年）在一棵度為4的樹(shù)T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹(shù)T的葉節(jié)點(diǎn)個(gè)數(shù)是（ ）。 分析：答案是B，此題考查二叉樹(shù)的性質(zhì)，利用二叉樹(shù)的性質(zhì)3的證明思路進(jìn)行求解。6.（10年）對(duì)n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的敘述中，錯(cuò)誤的是（ ）。 分析：答案是A，此題考查哈夫曼樹(shù)的構(gòu)造，以及哈夫曼樹(shù)的特點(diǎn)。7．（11年）若一棵完全二叉樹(shù)有768個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是（ ）。 分析：答案是C，考查二叉樹(shù)的性質(zhì)，葉結(jié)點(diǎn)個(gè)數(shù)為你n則度為2的結(jié)點(diǎn)個(gè)數(shù)為n1，總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為1，因此2n=768。8．（11年）若一棵二叉樹(shù)的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹(shù)的中序遍歷序列不會(huì)是（ ）。,2,3,4 ,3,4,1 ,2,4,1 ,3,2,1分析：答案是C，考查二叉樹(shù)的遍歷。此題可以用畫(huà)圖的方式進(jìn)行判斷。9．（11年）已知一棵有2011個(gè)結(jié)點(diǎn)的樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)116，該樹(shù)對(duì)應(yīng)的二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)是（ ）。 分析：答案是D，此題考查二叉樹(shù)和樹(shù)的轉(zhuǎn)換?？紤]一種特殊的情況，設(shè)題意中的樹(shù)是如下圖所示的結(jié)構(gòu)，則對(duì)應(yīng)的二叉樹(shù)中僅有前115個(gè)葉結(jié)點(diǎn)有右孩子。（二）綜合題近兩年沒(méi)有考查二叉樹(shù)的題目，如果考的話一般應(yīng)該是二叉樹(shù)的遍歷和哈夫曼樹(shù)以及哈夫曼編碼。三、考查重點(diǎn)1．二叉樹(shù)的定義與特點(diǎn)；2．二叉樹(shù)的性質(zhì)及應(yīng)用；3．二叉樹(shù)的遍歷（遍歷過(guò)程及算法實(shí)現(xiàn)）；4．線索二叉樹(shù)的構(gòu)造；5．樹(shù)的存儲(chǔ)及樹(shù)與二叉樹(shù)的轉(zhuǎn)換；6．哈夫曼樹(shù)構(gòu)造和哈夫曼編碼。分析：此章知識(shí)點(diǎn)比較多，并且每個(gè)知識(shí)點(diǎn)都可能出題，因此要做到對(duì)每一個(gè)知識(shí)點(diǎn)的理解和掌握，選擇題和綜合題都可以出。雖然近兩年沒(méi)有出綜合題，同學(xué)們也不要忽視，綜合題一般會(huì)現(xiàn)在二叉樹(shù)的遍歷及其應(yīng)用、樹(shù)與二叉樹(shù)的轉(zhuǎn)換和哈夫曼樹(shù)的構(gòu)造及哈夫曼編碼。四、練習(xí)題（一）選擇題（ C ）。A．11 B．10 C．11至1025之間 D．10至1024之間2．一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則這棵二叉樹(shù)最少有( B )結(jié)點(diǎn)。A．2h B．2h1 C．2h+1 D．h+1，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( C )次序的遍歷實(shí)現(xiàn)編號(hào)。A．先序 B．中序 C．后序 D．從根開(kāi)始按層次遍歷，則該二叉樹(shù)一定是（ C ）的二叉樹(shù)。A．空或只有一個(gè)結(jié)點(diǎn) B．任一結(jié)點(diǎn)無(wú)左子樹(shù) C．高度等于其結(jié)點(diǎn)數(shù) D．任一結(jié)點(diǎn)無(wú)右子樹(shù)，且X不為根，則X的前驅(qū)為( C ) 。 ，其中空的鏈域的個(gè)數(shù)是( B )。 （二）綜合題（1）二叉樹(shù)前序、中序、后序和層次遍歷的非遞歸算法前序void PreOrder(Bitree T){InitStack(S)。 Push(S,T)。 while(!StackEmpty(S)) {pop(S,p)。 visit(pdata)。 if (prchild!=NULL) push(S,prchild)。 if (plchild!=NULL) push(S,plchild)。 }}中序void InOrder(Bitree T){InitStack(S)。 p=T。 while(!StackEmpty(S)||p!=NULL){while(p!=NULL) { push(S,p)。 p=plchild。 } if(!StackEmpty(S)) { pop(S,p)。 visit(pdata)。 p=prchild。 }}}后序void PostOrder(Bitree T){Bitree stack[], p。 int tag[], top=0。 p=T。 while(top0||p!=NULL) {while(p!=NULL) { top++。 stack[top]=p。 tag[top]=0。 p=plchild。 } if(top0) { p=stack[top]。 while(tag[top]==1) { top。 visit(pdata)。 p=stack[to} if(top0) { p=stack[top]。 p=prchild。 tag[top]=1。} }}}層次void LayerOrder(Bitree T) {InitQueue(Q)。 EnQueue(Q,T)。 while(!QueueEmpty(Q)) {DeQueue(Q,p)。 visit(pdata)。 if(plchild) EnQueue(Q,plchild)。 if(prchild) EnQueue(Q,prchild)。 }}（2）二叉樹(shù)遍歷遞歸算法的應(yīng)用求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目int LeafCount_BiTree(Bitree T){if(!T) return 0。 //空樹(shù)沒(méi)有葉子 else if(!Tlchildamp。amp。!Trchild) return 1。 else return Leaf_Count(Tlchild)+Leaf_Count(Trchild)。}交換所有結(jié)點(diǎn)的左右子樹(shù)。void Bitree_Revolute(Bitree T){ if(T!=NULL) TlchildTrchild。 if(Tlchild) Bitree_Revolute(Tlchild)。 if(Trchild) Bitree_Revolute(Trchild)。 }求二叉樹(shù)中以值為x的結(jié)點(diǎn)為根的子樹(shù)深度。int Get_Sub_Depth(Bitree T,int x){if(Tdata==x) { printf(%d\n,Get_Depth(T))。 exit 1。 } else{if(Tlchild) Get_Sub_Depth(Tlchild,x)。if(Trchild) Get_Sub_Depth(Trchild,x)。 }}int Get_Depth(Bitree T){if(!T) return 0。 else {m=Get_Depth(Tlchild)。 n=Get_Depth(Trchild)。 return (mn?m:n)+1。 }}判斷兩棵樹(shù)是否相似的遞歸算法。int Bitree_Sim(Bitree B1,Bitree B2){if(!B1amp。amp。!B2) return 1。 else if(B1amp。amp。B2) return(Bitree_Sim(B1lchild,B2lchild) amp。amp。Bitree_Sim(B1rchild,B2rchild))else return 0。}（1）判斷一二叉樹(shù)是否為完全二叉樹(shù)。int Full_Bitree(Bitree T){InitQueue(Q)。 flag=0。 EnQueue(Q,T)。 while(!QueueEmpty(Q)) { DeQueue(Q,p)。 if(!p) flag=1。 else if(flag) return 0。 else { EnQueue(Q,plchild)。 EnQueue(Q,prchild)。 } } return 1。}（2）在二叉樹(shù)中查找值為x的結(jié)點(diǎn)，編寫(xiě)算法輸出x的所有祖先。void PostOrder(Bitree T，int x){Bitree stack[], p。int tag[], top=0。 p