點擊查看：2015年計算機二級公共基礎知識考點測試題匯總

　　樹與二叉樹

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

　　A.32B.31C.64D.63

　　參考答案：C

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

　　2[單選題]翻某二叉樹有5個度為2的結點，則該項樹中的葉子結點數是(　　)。

　　A.10B.8C.6D.4

　　參考答案：C

　　參考解析：根據二叉樹的性質，在任意二叉樹中，度為0的結點(即葉子結點)數總是比度為2的結點數多一個。

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

　　A.8B.9C.無此結點D.8或是9

　　參考答案：C

　　4[單選題]某二又樹中有n個度為2的結點，則該二叉樹中的葉子結點為(　　)

　　A.n+1B.n-1C.2nD.n/2

　　參考答案：A

　　參考解析：二叉樹具有這樣一個性質：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。所以某二叉樹中有n個度為2的結點，則該二叉樹中的葉子結點數為n+1。因此本題的正確答案是A。

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

　　A.結點的度

　　B.結點的層次

　　C.結點的高度

　　D.結點的深度

　　參考答案：A

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

　　參考答案：A

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

　　7[單選題]下列數據結構中，能用二分法進行查找的是(　　)

　　A.順序存儲的有序線性表B.線性鏈表C.二叉鏈表D.有序線性鏈表

　　參考答案：A

　　參考解析：二分法又叫折半(對分)查找法，只適合于順序存儲的有序表(是指線性表中的元 素按值非遞減排列)。二分法的基本思想是：設有序線性表的長度為n，被查元素為X，則二分查找的方法如下：

　　將X與線性表的中間項進行比較：若中間項的值等于x，則說明找到，查找結束;若x小于中間項的值，則在線性表的前半部分(即中間項以前的部分)以相同的方法進行查找;若X大于中間項的值，則在線性表的后半部分(即中間項以后的部分)以相同的方法進行查找、這個過程-直進行到查找成功或于表長度為0,(說明線性表中沒有這個元素為止)順序存儲的線性袁在計算機中-般用一個-維數組來表示，在數組中我們可以通過數組名和下標來對數組中的任意一個元素進行訪問，而在鏈表(不管是有序還是無序)中，要對元 素進行訪問必須從表頭結點開始， 順著鏈條一個一個結點進行搜索，因此選項A正確。

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

　　參考答案：C

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

　　9[單選題]某二又樹中有n個度為2的結點，則該二叉樹中的葉子結點為(　　)。

　　參考答案：A

　　參考解析：二叉樹具有這樣一個性質：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個。所以某二叉樹中有n個度為2的結點，則該二叉樹中的葉子結點數為n+1。因此本題的正確答案是A。

　　10[填空題]深度為5的滿二叉樹有________個葉子結點。

　　參考解析：16

　　【分析】在滿二叉樹中每層的結點數都達到最大值，而且葉子結點全部出現在最底層。第1層(根結點所在的層)有20個結點，第2層有21個結點，……第n層有25-1點。在深度為5的滿二叉樹中，第5層有2n-1=16個結點(全部是葉子結點)。

　　11[填空題]深度為5的滿二叉樹有(　　)個葉子結點。

　　參考解析：16

　　【分析】在滿二叉樹中每層的結點數都達到最大值，而且葉子結點全部出現在最底層。第1層(根結點所在的層)有20個結點，第2層有21個結點，……第n層有25-1點。在深度為5的滿二叉樹中，第5層有2n-1=16個結點(全部是葉子結點)。

　　12[單選題]對右上圖二叉樹進行中序遍歷的結果是(　　)

　　A.ACBDFEG

　　B.ACBDFGE

　　C.ABDCGEF

　　D.FCADBEG

　　參考答案：A

　　參考解析：中序遍歷的基本思想是先中序遍歷左子樹，后訪問根結點，再中序遍歷右子樹。針對本題中序遍歷左子樹的結果是ACBD，中序遍歷右子樹的結果是EG。所以本題的中序遍歷結果是ACBDFEG，前序遍歷結果是FCADBEG，后序遍歷結果是ABDCGEF。因此本題的正確答案是A。

　　13[單選題]對右上圖二叉樹進行中序遍歷的結果是(　　)。

　　參考答案：A

　　參考解析：中序遍歷的基本思想是先中序遍歷左子樹，后訪問根結點，再中序遍歷右子樹。針對本題中序遍歷左子樹的結果是ACBD，中序遍歷右子樹的結果是EG。所以本題的中序遍歷結果是ACBDFEG，前序遍歷結果是FCADBEG，后序遍歷結果是ABDCGEF。因此本題的正確答案是A。

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

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

　　相關推薦：

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

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

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

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