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

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

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

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

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

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

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