廣州大學松田學院7數據結構復習題-樹-參考答案

數據結構復習題（二叉樹）一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打╳）（√）（1）樹結構中每個結點最多只有一個直接前驅。（ㄨ）（2）完全二叉樹一定是滿二查樹。（ㄨ）（3）在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。（√）（4）一棵二叉樹中序遍歷序列的最后一個結點，必定是該二叉樹前序遍歷的最后一個結點。（√）（5）二叉樹的前序遍歷中，任意一個結點均處于其子女結點的前面。（√）（6）由二叉樹的前序遍歷序列和中序遍歷序列，可以推導出后序遍歷的序列。（√）（7）在完全二叉樹中，若一個結點沒有左孩子，則它必然是葉子結點。（ㄨ）（8）在哈夫曼編碼中，當兩個字符出現的頻率相同，其編碼也相同，對于這種情況應該做特殊處理。（ㄨ）（9）含多于兩棵樹的森林轉換的二叉樹，其根結點一定無右孩子。（√）（10）具有n個葉子結點的哈夫曼樹共有2n-1個結點。二．填空題在樹中，一個結點所擁有的子樹數稱為該結點的度。度為零的結點稱為葉（或葉子，或終端）結點。樹中結點的最大層次稱為樹的深度（或高度）。對于二叉樹來說，第i層上至多有2i-1個結點。深度為h的二叉樹至多有2h-1個結點。由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。有20個結點的完全二叉樹，編號為10的結點的父結點的編號是5。哈夫曼樹是帶權路徑長度最小的二叉樹。由二叉樹的后序和中序遍歷序列，可以唯一確定一棵二叉樹。某二叉樹的中序遍歷序列為:DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為：DABEC。設一棵二叉樹結點的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結點是：E、F、H。已知完全二叉樹的第8層有8個結點，則其葉結點數是68。由樹轉換成二叉樹時，其根結點無右子樹。采用二叉鏈表存儲的n個結點的二叉樹，一共有2n個指針域。采用二叉鏈表存儲的n個結點的二叉樹，共有空指針n+1個。前序為A，B，C且后序為C，B，A的二叉樹共有4種。AACBABCABCACB（17）三個結點可以組成2種不同形態(tài)的樹。（18）將一棵完全二叉樹按層次編號，對于任意一個編號為i的結點，其左孩子結點的編號為：2*i。（19）給定如下圖所示的二叉樹，其前序遍歷序列為：ABEFHCG。AABFGHDCE（20）給定如下圖所示的二叉樹，其層次遍歷序列為：ABCEFGH。AABFGHDCE三．選擇題（1）樹最適合用來表示（D）。A．有序數據元素B．無序數據元素C．元素之間無聯系的數據D．元素之間有分支的層次關系（2）前序為A，B，C的二叉樹共有（D）種。A．2 B．3 C．4 D（3）根據二叉樹的定義，具有3個結點的二叉樹有（C）種樹型。A．3 B．4 C．5 D．6（4）在一棵具有五層的滿二叉樹中，結點的總數為（B）A．16B．31C．32D．33（5）具有64個結點的完全二叉樹的深度為（C）A．5 B．6 C．7 D．（6）任何一棵二叉樹的葉結點在前序、中序、后序遍歷序列中的相對次序（A）。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對（7）A，B為一棵二叉樹上的兩個結點，在中序遍歷時，A在B前的條件是（C）。A．A在B右方B．A是B祖先C．A在B左方D．A是B子孫（8）下列4棵樹中，（B）不是完全二叉樹。A．B．C．D．ABECABECDABCDABEFCDABEGFDCD（9）如右圖所示的二叉樹，后序遍歷的序列是（D）ABADECFGHIA．A、B、C、D、ABADECFGHIB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A（10）對于下邊的二叉樹，其中序序列為（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGH（11）某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為:DEBAC，則前序遍歷序列為（D）。A．ACBED B．DECAB C．DEABCD．CEDBA（12）具有n（n>1）個結點的完全二叉樹中，結點i（2i>n）的左孩子結點是（D）。A．2i B．2i+1 C．2i-1 D．不存在（若2i<=n，則答案為A）（13）把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是（A）。A．唯一的B．有多種C．有多種，但根結點都沒有左孩子D．有多種，但根結點都沒有右孩子（14）將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為45的結點的左孩子編號為（B）。A．46 B．47 C．90 D（15）將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為49的結點的右孩子編號為（B）。A．98 B．99 C．50 D．100（16）二叉樹按某種順序線索化后，任一結點均有指向其前驅和后繼的線索，這種說法（B）。A．正確B．錯誤 C．不確定D．都有可能（17）下列陳述正確的是（D）。A．二叉樹是度為2的有序樹 B．二叉樹中結點只有一個孩子時無左右之分C．二叉樹中必有度為2的結點 D．二叉樹中最多只有兩棵子樹，且有左右子樹之分（18）用5個權值{3,2,4,5,1}構造的哈夫曼樹的帶權路徑長度是（B）。Ａ．32Ｂ．33Ｃ．34Ｄ．15（先構造哈夫曼樹，WPL=（1+2）*3+（3+4+5）*2=33）（19）在樹結構中，若結點B有4個兄弟，A是B的父親結點，則A的度為為（C）。A．3B．4C．5（20）二叉樹的葉結點個數比度為2的結點的個數（C）。A．無關 B．相等 C．多一個 D．少一個四.簡答題1．已知一棵樹邊的集合如下，請畫出此樹，并回答問題。{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)}（1）哪個是根結點？（2）哪些是葉結點？（3）哪個是G的雙親？（4）哪些是G的祖先？（5）哪些是G的孩子？（6）哪些是E的子孫？（7）哪些是E的兄弟？哪些是F的兄弟？（8）結點B和N的層次各是多少？（9）樹的深度是多少？（10）以結點C為根的子樹的深度是多少？（11）樹的度數是多少？答：（1）A是根結點。（2）葉結點：M，N，D，J，K，F，I。（3）G的雙親：C。（4）G的祖先：A，C。（5）G的孩子：J，K。（6）E的子孫：L，M，N。（7）E的兄弟：D；F的兄弟：G，H。（8）結點B的層次為2；結點N的層次是5。（9）樹的深度是5。（10）以結點C為根的子樹的深度是3。（11）樹的度數是3。2．設下列二叉樹是與某森林對應的二叉樹，試回答下列問題。DADABEGICFHJLK （2）每一棵樹的根結點分別是什么？ （3）第一棵樹有幾個結點？ （4）第二棵樹有幾個結點？ （5）森林中有幾個葉結點？解：（1）4（2）A，C，G，K（3）6（4）2（5）73．二叉樹按中序遍歷的結果為：ABC，試問有幾種不同形態(tài)的二叉樹可以得到這一遍歷結果？并畫出這些二叉樹。答：（1）5種。ABABCAADCBBABCACCB4.分別畫出具有3個結點的樹和三個結點的二叉樹的所有不同形態(tài)。答：三個結點的樹三個結點的二叉樹樹五.應用題1．已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。請畫出該二叉樹，并寫出它的前序遍歷的序列。BCHDDBCHDDFGEIA其前序遍歷的序列為：EBADCFHGI2．已知一棵二叉樹的前序遍歷和中序遍歷的序列分別為：A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。請畫出此二叉樹，并寫出它的后序遍歷的序列。。GHAGHABDCEFI其后序遍歷的序列為：GHDBEIFCA3．已知一棵樹的層次遍歷的序列為：ABCDEFGHIJ，中序遍歷的序列為：DBGEHJACIF，請畫出該二叉樹，并寫出它的后序遍歷的序列。ABABCHDDFGEIJ后序遍歷的序列：DGJHEBIFCA4.把下列一般樹轉換為二叉樹1212435678AABFEGHIJCD124124688D537ABCHDDFGEIJ（1）（2）5.把下列森林轉換為二叉樹FGKFGKIJHACBDEKAKABCHDDFGEIJ6．把下列二叉樹還原為森林AADBICHFGE解：還原后的二叉樹為：AABCHDDFGEI7．某二叉樹的結點數據采用順序存儲，其結構如下：1234567891011121314151617181920EAFDHCGIB（1）畫出該二叉樹（3分）（2）寫出按層次遍歷的結點序列（2分）解：ADADHFGECBI（2）層次遍歷的結點序列：EAFDHCGIB8．某二叉樹的存儲如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000 其中根結點的指針為6，lchild、rchild分別為結點的左、右孩子的指針域，data為數據域。（1）畫出該二叉樹（3分）（2）寫出該樹的前序遍歷的結點序列（2分）解：BDBDJHGACFEIABCEDFHGIJ9．給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。080828D25D33D40D60D08D54D55D3333解：（1）中序遍歷序列：5540256028083354（2）中序線索二叉樹：NULLNULLNULL0828D25D33D40D60D08D54D55D10.畫出表達式：-A+B-C+D的標識符樹，并求它們的后綴表達式。解：++ˉ+ˉBDCAD0后綴表達式：0A–B+C–D+11．畫出表達式：（A+B/C-D）*（E*（F+G））的標識符樹，并求它們的后綴表達式。ABABC+DDFGE/+*ˉ*后綴表達式：ABC/+D–EFG+**12．對于算術表達式（A+B*C/D）*E+F*G，畫出標識符樹，并求它們的后綴表達式。解：**EGFD*B++*AD/C后綴表達式：ABCD/*+E*FG*+13．給定一個權集W={4，5，7，8，6，12，18}，試畫出相應的哈夫曼樹，并計算其帶權路徑長度WPL。351325D126351325D12660181798D45791317253560WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15914．給定一個權集W={3，15，17，14，6，16，9，2}，試畫出相應的哈夫曼樹，并計算其帶權路徑長度WPL。4917491733D1698229201514D56113D22369141516175293311204982WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=22915．假設用于通信的電文僅由A、B、C、D、E、F、G8個字母組成，字母在電文中出現的頻率分別為7，19，2，6，32，3，21，10。試為這8個字母設計哈夫曼編碼。解：以權值：2、3、6、7、10、19、21、32構造哈夫曼樹：6651911281740D213260D10000D023D710D0000011111101字母編號字母編號對應編碼出現頻率A10107B0019C100002D10016E1132D100013E0121F101110六．算法設計題以二叉鏈表為存儲結構，設二叉樹BT結構為：typedefstructBT{ chardata; BT*lchild; BT*rchild;}BT;1．求二叉樹中的度數為2的結點。2．求二叉樹中值為最大的元素。3．將二叉樹各結點存儲到一維數組中。4．前序輸出二叉樹中各結點及其結點所在的層號。5．求二叉樹的寬度6．交換二叉樹各結點的左右子樹。7．寫出在二叉樹中查找值為x的結點在樹中層數的算法。解：求二叉樹中的度數為2的結點。voidcount(BTt){if(t){if(t->lchild&&t->rchild)k++;count(t->lchild);count(t->rchild);}}求二叉樹中值為最大的元素。intmaxnode(BTt,intmax){if(t){if(t->data>max)max=t->data;max=maxnode(t->lchild,max);max=maxnode(t->rchild,max);}}3．將二叉樹各結點存儲到一維數組中。voidcreate(BTt,inta[],inti){if(t){a[i]=t->data;create(t->lchild,a,2*i);create(t->rchild,a,2*i+1);}}4．前序輸出二叉樹中各結點及其結點所在的層號。voidpreorderlevel(BTt,inth)//t的層數為h{if(t!=NULL){printf(“%d,%d”,t->data,h);preorderlevel(t->lchild,h+1);preorderlevel(t->rchild,h+1);}}求二叉樹的寬度思想：按層遍歷二叉樹，采用一個隊列q，讓根結點入隊列，最后出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反復，直到隊列為空。intWidth(BT*T){intfront=-1,rear=-1;//隊列初始化intflag=0,count=0,p;//p用于指向樹中層的最右邊的結點，標志flag記錄層中結點數的最大值if(T!=NULL){rear++;q[rear]=T;flag=1;p=rear;}while(front<p){front++;T=q[front];if(T->lchild!=NULL){rear++;q[rear]=T->lchild;count++;}if(T->rchild!=NULL){rear++;q[rear]=T->rchild;count++;}if(front==p) //當前層已遍歷完畢{if(flag<count)flag=count;count=0;p=rear; //p指向下一層最右邊的結點}} //endwhilereturn(flag);}6．解：借助棧來進行對換。Swap(BinTree*T){BinTree*stack[100],*temp;inttop=-1;root=T;if(T!=NULL){top++;stack[top]=T;while(top>-1){T=stack[top];top--;if(T->child!=NULL||T->rchild!=NULL){//交換結點的左右指針temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}if(T->lchild!=NULL){top++;stack[top]=T->lchild;}if(T->rchild!=NULL){top++;stack[top]=T->rchild;}}}}main(){intI,j,k,l;printf(“\n”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(root);l=Width(root);printf(“\nTheNode’sNumber:%d”,i);printf(“\nTheLeafs’sNumber:%d”,j);printf(“\nTheDepthis:%d”,k);printf(“\nThewidthis:%d”,l);Swap(root);Printf(“\nTheswapTreeis:”);Inorder(root);}7．解：inth=-1,lh=1,count=0;charx=’c’;//賦初值Level(BinTreeT,inth,intlh)//求X結點在樹只的層樹{if(T==Null)h=0;elseif(T->data==x){h=lh;count=h;}else{h++;Level(T->lchild,h,lh);if(h==-1)Level(T->rchild,h,lh);}}main(){BinTree*(*newroot);Printf(“\n”);Root=CreateBinTree();Inorder(root);Printf(“\n”);Level(root,h,lh);Printf(“%d”,count);}

模擬考題一．讀程序，寫出運行結果1．二叉樹的結構如圖所示，試寫出執(zhí)行下列算法后的輸出結果：。（用大寫的英文字母表示，字母之間不要任何間隔符號，最后一個字母后面也不要間隔符號）CFCFBDADGE{datatypedata;BT*lchild;BT*rchild;}BT;voidPreorder(BT*T){ if(T!=NULL){ cout<<T->data; Preorder(T->lchild); Preorder(T->rchild);}}解：ABCEDFG先序遍歷2．二叉樹的結構如圖所示，試寫出執(zhí)行下列算法后的輸出結果：。typedefstructBTCFCFBDADGEBT*lchild;BT*rchild;}BT;intBTD(BT*T){ intldep,rdep; if(T==NULL) return0; else {ldep=BTD(T->lchild); rdep=BTD(T->rchild); if(ldep>rdep) returnldep+1; else returnrdep+1;}}解：4（求二叉樹深度）3．二叉樹的結構如圖所示，試寫出執(zhí)行下列算法后，count的值為多少？CFCFBDADGE{datatypedata;//定義結點BT*lchild;BT*rchild;}BT;intcount=0;voidLeafnum(BT*T){ if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL) count++; Leafnum(T->lchild); Leafnum(T->rchild);}}解：3（求葉結點數）(2，3，4改為程序填空)二．程序填空1．填空完成二叉樹按層次遍歷的程序typedefstructBT{datatypedata;//定義結點BT*lchild;BT*rchild;}BT;voidLevelorder(BT*T) //層次遍歷{ inti,j; BT*q[100],*p; p=T; if(p!=NULL){i=1;q[i]=p;j=2;} while(i!=j){p=q[i];cout<<p->data; if(p->lchild!=NULL) {q[j]=p->lchild;j++;} if(p->rchild!=NULL) {q[j]=p->rchild;j++;} i++; }}}

三．應用題1．將下列二叉樹轉換為森林。DDABEGICFHJK解：DDABIHDECFGJK2．畫出和下列二叉樹相應的森林。DADABHCJEKGFIM（根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟）3．某二叉樹的結點數據采用順序存儲，其結構如下：1234567891011121314151617181920EAFDHCGIB（1）畫出該二叉樹（2分）（2）寫出結點值為D的父結點及左、右子樹（3分）解：ADADHFGECBI（2）D的父結點為AD的左子樹為CD的右子樹為空4．某二叉樹的存儲如下：12345678910Lchild00237580101DataJHFDBACEGIRch