樹(shù)和二叉樹(shù) 練習(xí)題.ppt

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

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

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