數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)-wenkub
2023-04-09 03:01:32 本頁面
【正文】 叉樹BT的存儲結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中BT為樹根結(jié)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。四、應(yīng)用題1．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？2．分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。7．如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是______。3．高度為8的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。( )12．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。( )8. 二叉樹只能用二叉鏈表表示。( )4. 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。A．a(chǎn)cbed B．decab C．deabc D．cedba 14．在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（ B ）A．都不相同 B．完全相同 C．先序和中序相同，而與后序不同 D．中序和后序相同，而與先序不同 15．在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（ C ）。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ D ）。A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ E ）A． 250 B． 500 C．254 D．505 E．以上答案都不對 8．二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（ C ）A．2I B． 2I11 C． 2I1 D．2I 110．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( B )結(jié)點(diǎn)A．2h B．2h1 C．2h+1 D．h+1 11. 利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（ B ）。A．左子結(jié)點(diǎn) B．右子結(jié)點(diǎn) C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) D．左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)20．由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ D ）A．2 B．3 C．4 D．5 22. 一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A[1..n]中，則二叉樹中第i個(gè)結(jié)點(diǎn)（i從1開始用上述方法編號）的右孩子在數(shù)組A中的位置是（ D ）A．A[2i](2i=n) B．A[2i+1](2i+1=n) C．A[i2] D．條件不充分，無法確定二、判斷題（在各題后填寫“√”或“”）1. 完全二叉樹一定存在度為1的結(jié)點(diǎn)。( )5. 用一維數(shù)組存儲二叉樹時(shí)，總是以前序遍歷順序存儲結(jié)點(diǎn)。( )9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。( )13．度為二的樹就是二叉樹。,一共有________個(gè)指針域,其中只有________個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的________個(gè)指針域?yàn)镹ULL。8．二叉樹的先序序列和中序序列相同的條件是___ ___。3．分別給出下圖所示二叉樹的先根、中根和后根序列。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu)。2. 對于有N個(gè)結(jié)點(diǎn)的二叉樹，其高度為log2n。6．中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列 √7．完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。11．樹形結(jié)構(gòu)中元素之間存在一個(gè)對多個(gè)的關(guān)系。15．霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。 prchlid==null 2.(1)2k1 (2)2k13．644. 2n n1 n+1 5． 先序遍歷 后序遍歷 中序遍歷 6．.(1)2k2+1（第k層1個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是2H1，其雙親是2H1/2=2k2）(2) 235。二叉樹不是樹的特例。4．(1)kh1(h為層數(shù))（2）因?yàn)樵摌涿繉由暇蠯h1個(gè)結(jié)點(diǎn)，從根開始編號為1，則結(jié)點(diǎn)i的從右向左數(shù)第２個(gè)孩子的結(jié)點(diǎn)編號為ki。 (3) 結(jié)點(diǎn)n(n1)的前一結(jié)點(diǎn)編號為n1（其最右邊子女編號是(n1)*k+1），故結(jié)點(diǎn) n的第 i個(gè)孩子的編號是(n1)*k+1+i。7．字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。scanf(“%d”,amp。btdata=x。}//結(jié)束 BiTree
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1