樹和二叉樹 練習題.ppt

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

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

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