數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)-文庫吧
2025-03-10 03:01 本頁面
【正文】 2．深度為k的完全二叉樹至少有___ ____個結(jié)點，至多有___ ____個結(jié)點。3．高度為8的完全二叉樹至少有______個葉子結(jié)點。,一共有________個指針域,其中只有________個用來指向結(jié)點的左右孩子，其余的________個指針域為NULL。5．樹的主要遍歷方法有________、________、________等三種。6．一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是__ _；編號是i的結(jié)點所在的層次號是_ __（根所在的層次號規(guī)定為1層）。7．如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是______。8．二叉樹的先序序列和中序序列相同的條件是___ ___。9．一個無序序列可以通過構(gòu)造一棵___ ___樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。10．若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的____ __序列中的最后一個結(jié)點。四、應(yīng)用題1．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？2．分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。3．分別給出下圖所示二叉樹的先根、中根和后根序列。5．將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC6．設(shè)二叉樹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ù)域。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu)。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點序列。（3）畫出二叉樹的后序線索樹。 第六章 樹和二叉樹一、單項選擇題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é)點。2. 對于有N個結(jié)點的二叉樹，其高度為log2n。3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序?！?. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。5. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。6．中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列 √7．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。√8. 二叉樹只能用二叉鏈表表示。9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。√10. 用鏈表(llinkrlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n1個空指針。11．樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系?！?2．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹。13．度為二的樹就是二叉樹。14. 二叉樹中序線索化后，不存在空指針域。15．霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)?！?6．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近?！倘⑻羁疹}1．plchild==null amp。amp。 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。log2i+17．48．任何結(jié)點至多只有右子女的二叉樹。9．二叉排序樹10．前序11．6912． *count++, countleaf(lrchile,count)13．(1) p=plchild // 沿左子樹向下 （2）p=prchild 14．(1)0 （2）hlhr (3)hr=hl15．(1)prchild (2)plchild (3)plchild (4)ADDQ(Q,plchild) (5)ADDQ(Q,prchild)四、應(yīng)用題1．樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1