北郵C++數(shù)據(jù)結構課后習題 習題4參考答案

習題41.填空題（1）已知二叉樹中葉子數(shù)為50，僅有一個孩子的結點數(shù)為30，則總結點數(shù)為（___________）。答案：129（2）4個結點可構成（___________）棵不同形態(tài)的二叉樹。答案：12（3）設樹的度為5，其中度為1~5的結點數(shù)分別為6、5、4、3、2個，則該樹共有（___________）個葉子。答案：31（4）在結點個數(shù)為n（n>1）的各棵普通樹中，高度最小的樹的高度是（___________），它有（___________）個葉子結點，（___________）個分支結點。高度最大的樹的高度是（___________），它有（___________）個葉子結點，（___________）個分支結點。答案：2n-11n1n-1（5）深度為k的二叉樹，至多有（___________）個結點。答案：2k-1（6）有n個結點并且其高度為n的二叉樹的數(shù)目是（___________）。答案：2n-1（7）設只包含根結點的二叉樹的高度為1，則高度為k的二叉樹的最大結點數(shù)為（___________），最小結點數(shù)為（___________）。答案：2k-1k（8）將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點為X，其雙親PARENT（X）的編號為（）。答案：24（9）已知一棵完全二叉樹中共有768個結點，則該樹中共有（___________）個葉子結點。答案：384（10）已知一棵完全二叉樹的第8層有8個結點，則其葉子結點數(shù)是（___________）。答案：68（11）深度為8（根的層次號為1）的滿二叉樹有（___________）個葉子結點。答案：128（12）一棵二叉樹的前序遍歷是FCABED，中序遍歷是ACBFED，則后序遍歷是（___________）。答案：ABCDEF（13）某二叉樹結點的中序遍歷序列為ABCDEFG，后序遍歷序列為BDCAFGE，則該二叉樹結點的前序遍歷序列為（___________），該二叉樹對應的樹林包括（___________）棵樹。答案：EACBDGF22.選擇題（1）在一棵度為3的樹中，度為3的結點的個數(shù)為2，度為2的結點個數(shù)為1，則度為0的結點個數(shù)為（）。A.4B.5C.6D.7（2）下列陳述中正確的是（A.二叉樹是度為2的有序數(shù)）。B.二叉樹中結點只有一個孩子時無左右之分C.二叉樹中必有度為2的結點D.二叉樹中最多只有兩棵子樹，并且有左右之分（3）樹中如果結點M有3個兄弟，而且N是M的雙親，則N的度是（）A.3B.4C.5D.1（4）設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為（）。A.2h（5）高度為5的完全二叉樹至少有（A.16B.32C.31（6）具有65個結點的完全二叉樹的高度為（B.2h－1C.2h+1D.h+1）個結點。D.5）。（根的層次號為0）A.8B.7C.6D.5（7）對一個滿二叉樹，m個樹葉，n個結點，深度為h，則（無）。A.n=h+mC.m=h-1B.h+m=2nD.n=2h-1（8）任一棵二叉樹，其葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則存在關系（）。A.n2+1=n0C.2n2+1=n0B.n0+1=n2D.n2=2n0+1（9）某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是（）。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca（10）設m、n為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是（）。A.n在m右方C.n在m左方B.n是m祖先D.n是m子孫（11）一棵二叉樹的廣義表表示為a（b（c，d），e（f（g））），則得到的層序遍歷序列為（A.abcdefgB.cbdaegfC.cdbgfeaD.abecdfg（12）將一棵樹t轉換為二叉樹h,則t的后序遍歷是h的()。A.中序遍歷B.前序遍歷C.后序遍歷D.層序遍歷（13）對二叉樹進行（A.前序B.中序（14）設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非葉結點，則B中右指針域為空的結點有）。）遍歷，可以得到該二叉樹所有結點構成的排序序列。C.后序D.層序（）個。A.n-1B.nC.n+1D.n+2（15）利用3，6，8，12，5，7這6個值作為葉子結點的權，生成一棵哈夫曼樹，該樹的深度為（）。A.3B.4C.5D.6（16）若度為m的哈夫曼樹中，其葉結點個數(shù)為n，則非葉結點的個數(shù)為（）。A.n-1B.[n/m]-1D.[n/(m-1)]-1C.[(n-1)/(m-1)]說明：在這里度為m的哈夫曼樹是指僅含有度為