數(shù)據(jù)結(jié)構(gòu)樹和二叉樹練習(xí)及答案

1、一、選擇題1、設(shè)T是一棵樹，T’是對應(yīng)于x的二叉樹，則T的先根次序遍歷和T’的（）次序遍歷相同。A、先根B、中根C、后根D、以上都不是2、3、若二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序序列遍歷為（）。A、acbedB、decabC、deabcD、cedba4、具有35個結(jié)點的完全二叉樹的深度為（）A、5B、6C、7D、85、將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點的編號為1，

2、則編號為49的結(jié)點的左孩子結(jié)點編號為（）A、98B、99C、50D、486、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A、空或只有一個結(jié)點B、高度等于其結(jié)點數(shù)C、任一結(jié)點無左孩子D、任一結(jié)點無左孩子7、二叉樹在線索化后，仍不能有效求解的問題是（）A、先根線索二叉樹中求先根后繼B、中根線索二叉樹中求中根后繼C、中根線索二叉樹中求中根前驅(qū)D、后根線索二叉樹中求后根后繼8、在線索化二叉樹中，t所指結(jié)點沒有左子樹的充足條件

3、是（）A、tlchild==NULLB、tltag==1C、tltag==1&&tlchild==NULLD、以上都不對9、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（）A、2hB、2h1C、2h1D、h110、深度為5的二叉樹至多有（）個結(jié)點。A、16B、32C、31D、1011、在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（）A、只有右子樹上的所有結(jié)點B、只有右子樹上的部分結(jié)點C、只有左子樹上的

4、所有結(jié)點D、只有左子樹上的部分結(jié)點12、樹最適合用來表示（）A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)13、任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序（）A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對14、設(shè)nm為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是（）A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫15、線索二叉樹是一種（）結(jié)構(gòu)A、邏輯B

5、、邏輯和存儲C、物理D、線性16、森林的后根遍歷序列與其對應(yīng)二叉樹的（）遍歷序列一致。A、先根B、后根C、中根D、不可能二、填空題1、由一棵二叉樹后序序列和（中序）可唯一確定這棵二叉樹。2、含有n個結(jié)點的二叉樹用二叉鏈表表示時，有（N1）個空鏈域。3、有m個葉子結(jié)點的哈夫曼樹有（2M1）個結(jié)點。4、前序為abc且后序cba的二叉樹共有（4）棵。5、已知完全二叉樹的第4層有6個結(jié)點，則其葉子結(jié)點數(shù)是（7）。6、已知二叉樹有31個葉子結(jié)點，

6、且僅有一個孩子的結(jié)點數(shù)為40，則總結(jié)點數(shù)為（101）。7、樹和二叉樹的兩個主要差別是（二叉樹是有序樹）和（二叉樹的度最大為2）。8、從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化成二叉樹的基本目的是（通過與樹對應(yīng)的二叉樹的操作來實現(xiàn)樹的操作）。9、深度為k的完全二叉樹至少有（2k1）個結(jié)點，至多有（2k1）個結(jié)點，若按自上而下，從左至右的次序給結(jié)點編號從1開始，則編號最小的葉子結(jié)點的編號是（2k1）。10、結(jié)點最少的樹為（空樹），