樹和二叉樹 練習題.ppt

1、1.對于一顆具有n個結點，度為4的樹來說，( ) A.樹的高度至多是n-3 B.至少在某一層上正好有4個結點 C.樹的高度至多是n-4 D.第i層上至多有4*(i-1)個結點 2. 按照二叉樹的定義，具有三個節(jié)點的二叉樹有( )種。 A、3 B、4 C、5 D、6 3.若一棵二叉樹具有8個葉子結點，6個度為1的結點，則度為2的結點個數是( ) A.5 B.7 C.8 D.9 4.一棵完全二叉樹具有600個結點，則它有( ) 個度為1的結點。 A. 25 B. 26 C. 1 D. 50,第6章 測試題,5.在任何一棵二叉樹中，如果結點a有左孩子b，右孩子c，則在結點的先序序列、中序序列、后序序

2、列中， ( ) A.結點b一定在結點a的前面 B.結點a一定在結點c的前面 C.結點b一定在結點c的前面 D.結點a一定在結點b的前面 6.設森林T中有3棵樹，第一、二、三棵樹的結點個數分別是n1、n2、n3，那么當把森林T轉換成一棵二叉樹后，根結點的右子樹上有( ) 個結點。 A. n1+n2+n3 B. n2+n3 C. n1+n2 D. n1+n3,7.如果在樹的孩子兄弟鏈存儲結構中有6個空的左指針域，7個空的右指針域，則該樹中樹葉的個數為( ) A.7個 B.6個 C.13個 D.不能確定 8.如果T1是由樹T轉換而來的二叉樹，那么T中結點的后根序列就是T1中結點的( ) 序列 A.先

3、序 B.中序 C.后序 D.層次 9.由權值為7，19，2，6，32，3，21，10的結點構成的赫夫曼樹的帶權路徑長度為 ( ) A. 271 B. 261 C. 241 D. 231 10.在有n個葉子結點的哈夫曼樹中，其結點總數為( ) 。 A. 不確定 B. 2n C. 2n+1 D. 2n-1,1.在具有9個結點的二叉鏈表中，非空的鏈域個數為( 8 ) 2.已知完全二叉樹的第七層有32個葉子結點，則整個二叉樹的結點最多有( 95 )個。 3.有100個結點的完全二叉樹深度為( 7 ) ；有( 50 ) 個葉子。 4.在采用二叉鏈表結構存儲的二叉樹中，結點結構為(lchild, data, rchild)，其中l(wèi)child和rchild為指針域。指針p所指結點為葉子結點的條件是( lchild和rchild都為空 ) 5.已知二叉樹的先序遍歷序列為ADBECF，中序遍歷序列為BDEACF ，則這棵二叉樹的后序遍歷序列為( BEDFCA ) ，該樹對應的森林包括( 3 )棵樹。,1.已知一棵二叉樹的后序遍歷序列為DGEBHFCA，中序遍歷序列為DBEGAHCF，畫出該二叉樹，并寫出二叉樹的先序遍歷序列。,先序遍歷序列：ABDEGCHF,2.畫出下列存儲結構對應的二叉樹，并將其轉換成對應的森林。,3.畫出以1, 8, 2, 10, 12, 4，11為權值的哈夫曼樹（權值大的為