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