15[填空題]對右圖二叉樹進行中序遍歷的結果為(　　)。

　　參考解析：ACBDFEHGP

　　【分析】中序遍歷的原則是先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。因此本題中遍歷結果是ACBDFEHGP。

　　16[填空題]在深度為7的滿二叉樹中，度為2的結點個數為(　　)。

　　參考解析：63

　　【分析】滿二叉樹的定義是除最后一層外，每一層上的所有結點都有兩個子結點(即每一層上的結點數均達到最大值)。第l層(根結點在第l層)擁有的結點數是20=1，第2層擁有的結點數是21=2，第3層擁有的結點數是22=4，……，第n層擁有的結點數是2n-1。在深度為7的滿二叉樹中，葉子結點全部在第7層，其余結點都是2度結點。在滿二叉樹中，第7層擁有的結點數是27-1=64。二叉樹具有這樣一個性質：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。所以度為2的結點個數為64—1=63。

　　17[單選題]對右下圖二叉樹進行后序遍歷的結果為(　　)。

　　參考答案：D

　　參考解析：后序遍歷的方法是：若二叉樹為空，則結束返回。否則先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根結點。本題后序遍歷左子樹的結果是DEB，后續遍歷右子樹的結果是FC，最后根是A，所以后續遍歷的結果是DEBFCA。因此本題的正確答案是D。

　　18[單選題]在深度為7的滿二叉樹中，葉子結點的個數為(　　)。

　　參考答案：C

　　參考解析：在滿二叉樹中每層的結點數都達到最大值， 而且葉子結點全部出現在最底層。第l層(根結點所在的層)有20個結點，第2層有21個結點，……第n層有2n-1個結點。在深度為7的滿二叉樹中，第7層有2 7-l=64個結點(全部是葉子結點)、在深度為7的滿二叉樹中，共有27—1=127個結點、因此本題的正確答案是C

　　19[填空題]在深度為7的滿二又樹中，度為2的結點個數為________。

　　參考解析：63

　　【分析】滿二叉樹的定義是除最后-層外，每-層上的所有結點都有兩個子結點(即每-層上的結點數均達到最大值)。第l層(根結點在第l層)擁有的結點數是20=1，第2層擁有的結點數是21=2，第3層擁有的結點數是22=4，……，第n層擁有的結點數是2n-1。在深度為7的滿二叉樹中，葉子結點全部在第7層，其余結點都是2度結點。在滿二叉樹中，第7層擁有的結點數是27-1=64。二叉樹具有這樣一個性質：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。所以度為2的結點個數為64—1=63。

　　20[單選題]一棵二叉樹中共有70個葉子結點與80個度為1的結點，該二叉樹中的總結點數為(　　)

　　A.219B.221C.229D.231

　　參考答案：A

　　參考解析：二叉樹具有這樣一個性質：在任意-顆二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。本題告知，葉子結點有70個，那度為2的結點就有69個，度為l的結點有80個，這顆二叉樹共有70+69+80=219個結點。因此本題的正確答案是A。

　　21[單選題]對右圖二叉樹進行前序遍歷的結果為(　　)

　　A.DYBEAFCZX

　　B.YDEBFZXCA

　　C.ABDYECFXZ

　　D.ABCDEFXYZ

　　參考答案：C

　　參考解析：前序遍歷(DLR)的基本思想是：先訪問根結點，后前序遍歷dzq-樹，再前序遍歷右子樹。本題根結點是A，前序遍歷左子樹得到的序列為BDYE，前序遍歷右子樹得到的序列為CFXZ，所以對本題二叉樹進行前序遍歷的結果為ABDYECFXZ。因此本題的正確答案是C。

　　22[單選題]一棵度數為4的樹，它的4度結點有l個，3度結點有2個，2度結點有3個，l度結點4個，問它的葉子結點有多少個?(　　)。

　　參考答案：D

　　參考解析：

　　23[填空題]設一棵二叉樹的中序遍歷結果為DBEACF，前序遍歷結果為ABDECF，則后序遍歷結果為________。

　　參考解析：

　　DEBFCA【分析】我們可以根據前序遍歷的結果ABDECF，確定第l個元素A是根結點，再看中序遍歷的結果DBEACF，A前面的DBE應該在左子樹，A后面的FC應該在右子樹。根據前序遍歷的結果和中序遍歷的結果，我們可以推導出：A是根結點，B是A的左結點，D是B的左結點，E是B的右結點.C是A的右結點，F是C的右結點，畫出的二叉樹如圖1.17所示。對圖進行后序遍歷的結果為DEBFCA。

　　總結：先根據前序遍歷或后序遍歷的結果，確定根結點，根據根結點確定左右予樹上的結點，再根據兩種遍歷畫出對應的二叉樹，最后遍歷二叉樹得到第三種遍歷結果。

　　24[填空題]樹是-種簡單的________(線性月)線性)結構，在樹中，所有數據元素之間的關系具有明顯的________特性。

　　參考解析：非線性

　　25[填空題]一棵二叉樹第六層(根結點為第-層)的結點數最多為________個。

　　參考解析：

　　32【分析】根據二叉樹的性質，我們可以得出一棵二又樹第n層(根結點為第-層)的結點數最多為2n-1個，因此第6層的結點數最多為25=32個，總結：二叉樹第1層只有一個根結點(20)，第2層最多只有兩個結點(21)，第3層最多只有4個結點(22)，……，第n層最多為有2n-1個結點(不是2n個)。考生還需要了解一棵深度(高度)為n的二叉樹最多擁有的結點總數是2n-1(20+21+22+…+2n-1=2n-l).這種類型的試題不要死記硬背，有時是2n-1，有時是2n-l，所以考生最好采用我們介紹的方法來推導。

　　26[單選題]在表示樹的多重鏈表中，除了要存儲結點的值和多個指針之外，還必須需要存儲(　　)。

　　參考答案：A

　　27[單選題]具有8個結點的完全二：叉樹中編號為4的結點的右子結點的編號為(　　)。

　　參考答案：C

　　28[填空題]擁有奇數個結點的完全二叉樹中有4個內部結點(非葉子結點)，請問它的葉子結點數是________。

　　參考解析：5

　　【分析】由于完全二叉樹是自上而下、自左而右的從l開始連續編碼的，因此完全二又樹要么不存在-度結點(當結點個數為奇數個時)，要么存在一個-度結點，而且唯-的一個-度結點就是最后編號為n(n為偶數)的葉子結點的父結點。而在二叉樹中零度結點個數總比二度結點個數多l，因此擁有4個二度結點的二叉樹的葉子結點的個數是4+1=5。

　　總結，設n為完全二叉樹的結點數，n0為葉子結點數，nl為度為1的結點數，n2為度2的結點數，則n=n0+nl+n2,n0=n2+1。若n為奇數，則nI=0;若n為偶數，則nl=l(注意-定要是完全二又樹)。

　　29[填空題]一棵二又樹第六層(根結點為第一層)的結點數最多為(　　)個。

　　參考解析：32

　　30[填空題]某--y.樹中度為2的結點有l8個，則該--y.樹中有(　　)個葉子結點。

　　參考解析：19

　　【分析】在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。

　　31[填空題]擁有奇數個結點的完全二叉樹中有4個內部結點(非葉子結點)，請問它的葉子結點數是(　　)。

　　參考解析：5

　　32[填空題]設一棵二叉樹的中序遍歷結果為DBEACF，前序遍歷結果為ABDECF，則后序遍歷結果為(　　)。

　　參考解析：DEBFCA

　　圖1.17

　　33[填空題]樹是一種簡單的(　　)(線性月}線性)結構，在樹中，所有數據元素之間的關系具有明顯的(　　)特性。

　　參考解析：非線性、層次

　　[填空題]設一棵完全二叉樹共有700個結點，則在該二叉樹中有(　　)個葉子結點。

　　參考解析：350

　　相關推薦：

　　2015年9月計算機等級考試成績查詢時間通知

　　2015計算機二級公共基礎知識考前沖刺練試題匯總

　　2015計算機二級公共基礎知識精選選擇題專項練習

　　2015計算機二級《公共基礎知識》精選選擇題90道