第六章樹習題1單項選擇題1、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則葉子結點個數是（B）。A、9 B、11 C、15 D、無法確定2、設給定權值總數有n個，其哈夫曼樹的結點總數為（D）。A、不確定 B、2n C、2n+1 D、2n13、有關二叉樹下列說法正確的是（B）。A、二叉樹的度為2 B、一棵二叉樹的度可以小于2C、二叉樹中至少有一個結點的度為2D、二叉樹中任何一個結點的度都為24、一棵二叉樹高度為h，所有結點的度或為0，或為2,則這棵二叉樹最少有（）結點。A、2h B、2h-1 C、2h+1 D、h+15、對于有n個結點的二叉樹，其高度為（）。A、n10g2n B、10g2n C、Log2n-D、不確定6、利用二叉鏈表存儲樹，則根結點的右指針是（）。A、指向最左孩子 B、指向最右孩子C、空 D、非空7、樹的后根遍歷序列等同于該樹對應的二叉樹的（）。A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層序遍歷8、在下列存儲形式中，哪一個不是樹的存儲形式？（）人、雙親表示法 B、孩子鏈表表示法C、孩子兄弟表示法 D、順序存儲表示法9、已知一棵二叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果為（）。A、CBEFDA B、FEDCBA C、CBEDFA 口、不定10、某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A、空的或只有一個結點 B、任一結點無左子樹C、高度等于其結點數 D、任一結點無右子樹11、一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數是：（）。A、不確定 B、0 C、1 D、212、若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，則x的前驅為（）。A、X的雙親 B、X的右子樹中最左的結點C、X的左子樹中最右結點 D、X的左子樹中最右葉結點13、引入二叉線索樹的目的是（）.A、加快查找結點的前驅或后繼的速度8、為了能在二叉樹中方便的進行插入和刪除^為了能方便的找到雙親D、使二叉樹的遍歷結果唯一14、下述編碼中哪一個不是前綴碼（）。A、（00，01，10，11） B、（0，1，00，11）C、（0，10，110，111） D、（1，01，000，001）TOC\o"1-5"\h\z15、按照二叉樹的定義，具有3個結點的二叉樹有（ ）種。A、6 B、5 C、4 D、316、在具有n個結點的二叉鏈表中，空指針域的個數為（ ）。A、2n-1 B、2n+1 C、n-1 D、n+117、深度為4的二叉樹至多有（ ）個結點。A、17 B、18 C、15 D、1318、樹最適合用來表示（ ）。A、有序數據元素 B、無序數據元素C、元素之間具有層次關系的數據D、元素之間無聯系的數據19、一棵具有n個結點的樹，所有結點的度之和為（ ）。A、n B、n-1 C、n+1 D、無法確定20、一棵完全二叉樹上有1001個結點，其中葉子結點個數是（ ）。A、250B、501C、254D、50521、先序序列和后序序列正好相反的二叉樹是（ ）。A、二叉排序樹 B、平衡二叉樹 C、左斜樹D、以上都不對22、在任何一棵二叉樹中，如果結點q的左孩子為b，右孩子為c，則在結點的先序遍歷、中序遍歷和后序遍歷中（）。A、結點b一定在結點a的前面B、結點a一定在結點c的前面

C、結點b一定在結點c的前面 D、結點a一定在結點b的前面TOC\o"1-5"\h\z23、下面哪個選項可以唯一地確定一棵二叉樹。（ ）A、先序序列 B、中序序列C、中序后序序列 D、先序和后序序列24、判斷線索二叉樹上指針p所指結點有右孩子的條件是（ ）。A、p!=NULL B、p->rchild!=NULL C、p->rtag==0 D、p->rtag==125、設一棵哈夫曼樹共有35個結點，則該哈夫曼樹共有（ ）個葉子。A、18 B、35 C、20 D、3026、對應哈夫曼樹，下面說法錯誤的是（ ）。A、哈夫曼樹一定是完全二叉樹B、哈夫曼樹中沒有度為1的結點C、樹中兩個權值最小的結點一定是兄弟結點D、樹中任一非葉子結點的權值一定不小于下一層任一結點的權值2填空題TOC\o"1-5"\h\z1、已知一棵二叉樹的先序序列為ABCD，中序序列為BCAD，則其后序序列為（ ）。2、在n個結點的線索二叉鏈表中，有（ ）個線索指針。3、若一棵滿三叉樹中含有121個結點，則該樹深度為（ ）。4、在有n個葉子結點的哈夫曼樹中，總結點數是（ ）。5、樹T采用二叉鏈表存儲，如果樹T中某結點為葉子結點，則在二叉鏈表BT中該結點一定（ ）。6、在一棵高度為h的三叉樹中，最多含有（ ）個結點。7、判斷線索二叉樹中某結點指針p所指結點有左孩子的條件是（ ）。8、在有n個結點的哈夫曼樹中，度為1的結點數是（ ）。9、深度為n的二叉樹最少有（ ）個結點，最多有（）個結點。10、若對一棵具有n個結點的二叉樹，采用二叉鏈表存儲時，其指針總數為（ ），其中（ ）個用于指向孩子，（ ）個指針是空閑的。11、若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲在一維數組A中，則：A[i]若有左孩子，其左孩子在數組中的位序號為（ ），若有右孩子，其右孩子在數組中的位序號為（），其雙親在數組中的位序號為（）。12、后綴表達式12、后綴表達式923+-102/-的值為（達式為（ ）。），中綴表達式（3+4x）-2y/2對應的后綴表13、一棵高度為3的二叉樹中最少含有（ ）個結點，最多含有（ ）個結點；一棵高度為3的平衡二叉樹中最少含有（）個結點，最多含有（ ）個結點。14、已知一棵完全二叉樹共有768個結點，則該樹共有（ ）個葉子。15、設哈夫曼樹中共有99個結點，則該樹有（ ）個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有（ ）個空指針。16、一棵深度為6的滿二叉樹有（ ）個分支結點和（）個葉子。3問答題1、給出圖6-7所示的二叉樹的先根、中根和后根遍歷序列。AEBCFD圖AEBCFD圖6-72、設二叉樹BT的存儲結構如下:12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中BT為樹根結點的指針，其值為6,Lchild和Rchild分別為結點的左右孩子指針域，data為結點的數據域。完成下列各題：（1）畫出二叉樹BT的邏輯結構；（2）寫出按前序、中序和后序遍歷該二叉樹所得到的結點序列；（3）畫出二叉樹的后序線索樹。3、已知一棵完全二叉樹的第6層有8個葉子結點，求該完全二叉樹有多少個結點？4、若二叉樹采用順序存儲結構表示，則編號為i和j的兩個結點處于同一層的條件是什么？5、已知高度為8的完全二叉樹的第8層有8個結點，則葉子結點有多少個？6、若某非空二叉樹，分別寫出滿足下列條件的二叉樹是什么形態的二叉樹？（1）先序序列和中序序列正好相反；(2)先序序列和中序序列正好相同；(3)中序序列和后序序列正好相同；(4)中序序列和后序序列正好相反。7、一棵滿k叉樹上的葉子結點數。和非葉子結點數b之間滿足下面的關系式:a=(k-1)b+1,請給出推導證明過程。8、一棵樹有3度結點100個，2度結點200個，該樹有多少個葉子結點？有多少個度為1的結點？9、已知樹如圖6-8所示：(1)寫出該樹的后序序列；(2)畫出由該樹轉換得到的二叉樹。10、假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別是0.10、0.07、0.16、0.05、0.19、0.23、0.12、0.08,試為這8個字母設計哈夫曼編碼。4算法填空題下面函數的功能是返回二叉樹BT中值為e的結點所在的層號，請在畫有橫線的地方填寫適當的內容完成該功能。intNode_Level(BinTreeNode*BT,ElemTypee)(if(!BT)return0; 〃空樹層號為0elseif()return1; 〃根結點層號為1else(int