數(shù)據(jù)結(jié)構(gòu)樹的測(cè)試題(二)(完整版)
【正文】 分析]后序遍歷最后訪問根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。 //首次出現(xiàn)結(jié)點(diǎn)為空 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)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n1個(gè)空指針。 第六章 樹和二叉樹一、單項(xiàng)選擇題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é)點(diǎn)。四、應(yīng)用題1．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？2．分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。3．高度為8的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。( )8. 二叉樹只能用二叉鏈表表示。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 ）。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．以上答案都不對(duì) 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. 利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（ B ）。( )5. 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。( )13．度為二的樹就是二叉樹。8．二叉樹的先序序列和中序序列相同的條件是___ ___。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu)。6．中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列 √7．完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。15．霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。二叉樹不是樹的特例。 (3) 結(jié)點(diǎn)n(n1)的前一結(jié)點(diǎn)編號(hào)為n1（其最右邊子女編號(hào)是(n1)*k+1），故結(jié)點(diǎn) n的第 i個(gè)孩子的編號(hào)是(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é)點(diǎn)q時(shí)，將棧中元素從棧頂開始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配（即相等）的元素就是結(jié)點(diǎn)p 和q的最近公共祖先。 while(bt!=null ||top0){while(bt!=null amp。i=top。j0。//ｑ、p無公共祖先｝//結(jié)束Ancestor3．解答：本算法要借用隊(duì)列來完成，其基本思想是，只要隊(duì)列不為空，就出隊(duì)列，然后判斷該結(jié)點(diǎn)是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊(duì)列。 /*入隊(duì)列*/ } } } }4．【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/{ InitStack(amp。S,amp。 printf(pdata)。} return(bt)。 btrchild==null) //葉子結(jié)點(diǎn) if(pre==null) {head=bt。刪除值為x結(jié)點(diǎn)，意味著應(yīng)將其父結(jié)點(diǎn)的左(右)子女指針置空，用層次遍歷易于找到某結(jié)點(diǎn)的父結(jié)點(diǎn)。}//若根結(jié)點(diǎn)的值為x，則刪除整棵樹 {QueueInit(Q)。} //父結(jié)點(diǎn)的右子女置空else Enqueue (Q,prchild)。 qRtag= =0。 succ= q。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1