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