點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)測(cè)試題匯總

　　樹與二叉樹

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

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

　　參考答案：C

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

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

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

　　參考答案：C

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

　　3[單選題]具有8個(gè)結(jié)點(diǎn)的完全二叉樹中編號(hào)為4的結(jié)點(diǎn)的右子結(jié)點(diǎn)的編號(hào)為(　　)

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

　　參考答案：C

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

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

　　參考答案：A

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

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

　　A.結(jié)點(diǎn)的度

　　B.結(jié)點(diǎn)的層次

　　C.結(jié)點(diǎn)的高度

　　D.結(jié)點(diǎn)的深度

　　參考答案：A

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

　　參考答案：A

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

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

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

　　參考答案：A

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

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

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

　　參考答案：C

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

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

　　參考答案：A

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

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

　　參考解析：16

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

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

　　參考解析：16

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

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

　　A.ACBDFEG

　　B.ACBDFGE

　　C.ABDCGEF

　　D.FCADBEG

　　參考答案：A

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

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

　　參考答案：A

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

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

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

　　相關(guān)推薦：

　　2015年9月計(jì)算機(jī)等級(jí)考試成績(jī)查詢時(shí)間通知

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考前沖刺練試題匯總

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)精選選擇題專項(xiàng)練習(xí)

　　2015計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》精選選擇題90道