數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)(完整版)
【正文】 分析]后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。 //首次出現(xiàn)結(jié)點為空 if (prchild amp。QueueInit(Q)。else if(x0) {bt=(BiNode *)malloc(sizeof(BiNode))。前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ（3）圖略。后根序列：D C B F J I H G E A。amp?！?0. 用鏈表(llinkrlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n1個空指針。 第六章 樹和二叉樹一、單項選擇題3．A4．C5．B6．D7．E 8. D9．C10．B11. C12．A13．D14．B15．C16．B 17. B18. A19．C20．D21．B22. D23．C二、判斷題（在各題后填寫“√”或“”）1. 完全二叉樹一定存在度為1的結(jié)點。四、應(yīng)用題1．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？2．分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。3．高度為8的完全二叉樹至少有______個葉子結(jié)點。( )8. 二叉樹只能用二叉鏈表表示。A．a(chǎn)cbed B．decab C．deabc D．cedba 14．在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（ B ）A．都不相同 B．完全相同 C．先序和中序相同，而與后序不同 D．中序和后序相同，而與先序不同 15．在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（ C ）。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 ）。( )5. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。( )13．度為二的樹就是二叉樹。8．二叉樹的先序序列和中序序列相同的條件是___ ___。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu)。6．中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列 √7．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。15．霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。二叉樹不是樹的特例。 (3) 結(jié)點n(n1)的前一結(jié)點編號為n1（其最右邊子女編號是(n1)*k+1），故結(jié)點 n的第 i個孩子的編號是(n1)*k+1+i。scanf(“%d”,amp。}//結(jié)束 BiTreeint JudgeComplete(BiTree bt) //判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0{int tag=0。 !tag) QueueIn(Q,plchild)。 } //whilereturn 1。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配（即相等）的元素就是結(jié)點p 和q的最近公共祖先。 while(bt!=null ||top0){while(bt!=null amp。i=top。j0。//ｑ、p無公共祖先｝//結(jié)束Ancestor3．解答：本算法要借用隊列來完成，其基本思想是，只要隊列不為空，就出隊列，然后判斷該結(jié)點是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊列。 /*入隊列*/ } } } }4．【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/{ InitStack(amp。S,amp。 printf(pdata)。} return(bt)。 btrchild==null) //葉子結(jié)點 if(pre==null) {head=bt。刪除值為x結(jié)點，意味著應(yīng)將其父結(jié)點的左(右)子女指針置空，用層次遍歷易于找到某結(jié)點的父結(jié)點。}//若根結(jié)點的值為x，則刪除整棵樹 {QueueInit(Q)。} //父結(jié)點的右子女置空else Enqueue (Q,prchild)。 qRtag= =0。 succ= q。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1