二叉樹筆試題目及答案

一、單項選擇題（每題2分，共10題）1.在二叉樹的第i層上至多有（）個結(jié)點。A.2^iB.2^(i-1)C.2^(i+1)D.2^(i-2)答案：B2.深度為k的二叉樹至多有（）個結(jié)點。A.2^k-1B.2^(k-1)C.2^k+1D.2^(k-2)答案：A3.對于一個有n個結(jié)點的二叉樹，其高度為（）。A.log?nB.log?n+1C.?log?(n+1)?D.?log?(n+1)?答案：C4.二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的（）。A.前面B.后面C.中間D.不確定答案：A5.二叉樹的中序遍歷序列中，根結(jié)點將（）。A.第一個被訪問B.第二個被訪問C.中間被訪問（若存在）D.最后被訪問答案：C6.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（）遍歷方法最合適。A.先序B.中序C.后序D.層次答案：C7.設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點值均小于根結(jié)點值，而右子樹上的結(jié)點值均不小于根結(jié)點值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是（）。A.先序B.中序C.后序D.前三種均可以答案：B8.具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點。A.8B.9C.10D.11答案：B9.一棵完全二叉樹共有360個結(jié)點，則在該二叉樹中度為1的結(jié)點個數(shù)為（）。A.0B.1C.180D.181答案：B10.若二叉樹的前序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則后序遍歷序列為（）。A.DEBFCAB.DEFBCAC.DEBCFAD.DEBFCA答案：A二、多項選擇題（每題2分，共10題）1.以下關(guān)于二叉樹的說法正確的是（）。A.二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)B.二叉樹的子樹有左右之分，次序不能顛倒C.滿二叉樹一定是完全二叉樹D.完全二叉樹一定是滿二叉樹答案：ABC2.二叉樹的存儲結(jié)構(gòu)可以是（）。A.順序存儲結(jié)構(gòu)B.鏈?zhǔn)酱鎯Y(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)答案：AB3.二叉樹的遍歷方法有（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD4.在二叉樹中（）。A.度為0的結(jié)點稱為葉結(jié)點B.度為1的結(jié)點稱為單分支結(jié)點C.度為2的結(jié)點稱為雙分支結(jié)點D.度為3的結(jié)點稱為三分支結(jié)點答案：ABC5.以下關(guān)于完全二叉樹的特性正確的是（）。A.葉子結(jié)點只能出現(xiàn)在最下兩層B.最下層的葉子結(jié)點一定集中在左部連續(xù)位置C.倒數(shù)第二層，若有葉子結(jié)點，一定都在右部連續(xù)位置D.如果結(jié)點度為1，則該結(jié)點只有左孩子答案：ABCD6.以下關(guān)于二叉排序樹的說法正確的是（）。A.左子樹結(jié)點值小于根結(jié)點值B.右子樹結(jié)點值大于根結(jié)點值C.中序遍歷二叉排序樹可以得到一個遞增的有序序列D.先序遍歷二叉排序樹可以得到一個遞增的有序序列答案：ABC7.二叉樹的先序遍歷可以用于（）。A.求二叉樹的根結(jié)點B.復(fù)制二叉樹C.判斷二叉樹是否對稱D.求二叉樹的高度答案：AB8.二叉樹的層次遍歷需要用到（）。A.隊列B.棧C.遞歸算法D.非遞歸算法答案：AD9.對于二叉樹的中序線索化，以下說法正確的是（）。A.利用空的左指針指向前驅(qū)B.利用空的右指針指向后繼C.是為了方便遍歷二叉樹D.線索化后中序遍歷不需要棧答案：ABC10.以下關(guān)于二叉樹的平衡調(diào)整的說法正確的是（）。A.目的是為了保持二叉樹的相對平衡B.有LL型調(diào)整、LR型調(diào)整等多種類型C.調(diào)整后二叉樹的高度可能會降低D.調(diào)整后二叉樹的結(jié)點個數(shù)會改變答案：ABC三、判斷題（每題2分，共10題）1.二叉樹中每個結(jié)點最多有兩個子樹。（）答案：對2.完全二叉樹就是滿二叉樹。（）答案：錯3.二叉樹的先序遍歷序列和后序遍歷序列能唯一確定一棵二叉樹。（）答案：錯4.二叉樹的中序遍歷序列和后序遍歷序列能唯一確定一棵二叉樹。（）答案：對5.二叉樹的度為2的結(jié)點個數(shù)比葉結(jié)點個數(shù)少1。（）答案：錯6.二叉樹的層次遍歷是按從上到下、從左到右的順序訪問結(jié)點。（）答案：對7.二叉排序樹插入新結(jié)點時不需要保持排序特性。（）答案：錯8.滿二叉樹的葉結(jié)點個數(shù)為2^(h-1)，其中h為樹的高度。（）答案：對9.二叉樹的先序遍歷、中序遍歷和后序遍歷都是遞歸算法。（）答案：對10.對于二叉樹的后序線索化，空的左指針指向前驅(qū)，空的右指針指向后繼。（）答案：錯四、簡答題（每題5分，共4題）1.簡述二叉樹的先序遍歷過程。答案：先訪問根結(jié)點，然后先序遍歷左子樹，最后先序遍歷右子樹。2.什么是完全二叉樹？答案：若設(shè)二叉樹的深度為h，除第h層外，其它各層(1～h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層所有的結(jié)點都連續(xù)集中在最左邊，這樣的二叉樹稱為完全二叉樹。3.二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有什么特點？答案：二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)用鏈表來表示二叉樹，每個結(jié)點有數(shù)據(jù)域和指向左、右孩子的指針域。它便于插入、刪除等操作，能很好地反映二叉樹的邏輯結(jié)構(gòu)，但占用的存儲空間相對較多。4.如何根據(jù)二叉樹的中序遍歷和后序遍歷序列確定二叉樹？答案：后序遍歷的最后一個結(jié)點為根結(jié)點，在中序遍歷中找到根結(jié)點，其左邊為左子樹，右邊為右子樹，然后遞歸構(gòu)建左右子樹。五、討論題（每題5分，共4題）1.討論二叉樹在數(shù)據(jù)結(jié)構(gòu)中的重要性。答案：二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。它可以用于高效地存儲和查找數(shù)據(jù)，如二叉排序樹。二叉樹的遍歷方法可用于對數(shù)據(jù)的有序訪問。在很多算法中，如哈夫曼樹用于數(shù)據(jù)壓縮，二叉樹的結(jié)構(gòu)特性能夠優(yōu)化算法效率。2.比較二叉樹的順序存儲和鏈?zhǔn)酱鎯Φ膬?yōu)缺點。答案：順序存儲節(jié)省存儲空間，可隨機訪問，但對于非完全二叉樹會浪費大量空間。鏈?zhǔn)酱鎯δ莒`活表示各種二叉樹結(jié)構(gòu)，便于插入和刪除操作，但占用更多存儲空間，不能隨機訪問。3.闡述二叉樹的平衡調(diào)整的意義。答案：二叉樹的平衡調(diào)整可