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

　　樹與二叉樹

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

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

　　參考答案：C

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

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

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

　　參考答案：C

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

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

　　A.8B.9C.無此結(jié)點D.8或是9

　　參考答案：C

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

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

　　參考答案：A

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

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

　　A.結(jié)點的度

　　B.結(jié)點的層次

　　C.結(jié)點的高度

　　D.結(jié)點的深度

　　參考答案：A

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

　　參考答案：A

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

　　7[單選題]下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是(　　)

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

　　參考答案：A

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

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

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

　　參考答案：C

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

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

　　參考答案：A

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

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

　　參考解析：16

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

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

　　參考解析：16

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

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

　　A.ACBDFEG

　　B.ACBDFGE

　　C.ABDCGEF

　　D.FCADBEG

　　參考答案：A

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

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

　　參考答案：A

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

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

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

　　相關推薦：

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

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

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

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