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

　　參考解析：ACBDFEHGP

　　【分析】中序遍歷的原則是先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。因此本題中遍歷結(jié)果是ACBDFEHGP。

　　16[填空題]在深度為7的滿二叉樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)為(　　)。

　　參考解析：63

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

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

　　參考答案：D

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

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

　　參考答案：C

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

　　19[填空題]在深度為7的滿二又樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_______。

　　參考解析：63

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

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

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

　　參考答案：A

　　參考解析：二叉樹(shù)具有這樣一個(gè)性質(zhì)：在任意-顆二叉樹(shù)中，度為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è)，這顆二叉樹(shù)共有70+69+80=219個(gè)結(jié)點(diǎn)。因此本題的正確答案是A。

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

　　A.DYBEAFCZX

　　B.YDEBFZXCA

　　C.ABDYECFXZ

　　D.ABCDEFXYZ

　　參考答案：C

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

　　22[單選題]一棵度數(shù)為4的樹(shù)，它的4度結(jié)點(diǎn)有l(wèi)個(gè)，3度結(jié)點(diǎn)有2個(gè)，2度結(jié)點(diǎn)有3個(gè)，l度結(jié)點(diǎn)4個(gè)，問(wèn)它的葉子結(jié)點(diǎn)有多少個(gè)?(　　)。

　　參考答案：D

　　參考解析：

　　23[填空題]設(shè)一棵二叉樹(shù)的中序遍歷結(jié)果為DBEACF，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為_(kāi)_______。

　　參考解析：

　　DEBFCA【分析】我們可以根據(jù)前序遍歷的結(jié)果ABDECF，確定第l個(gè)元素A是根結(jié)點(diǎn)，再看中序遍歷的結(jié)果DBEACF，A前面的DBE應(yīng)該在左子樹(shù)，A后面的FC應(yīng)該在右子樹(shù)。根據(jù)前序遍歷的結(jié)果和中序遍歷的結(jié)果，我們可以推導(dǎo)出：A是根結(jié)點(diǎn)，B是A的左結(jié)點(diǎn)，D是B的左結(jié)點(diǎn)，E是B的右結(jié)點(diǎn).C是A的右結(jié)點(diǎn)，F(xiàn)是C的右結(jié)點(diǎn)，畫(huà)出的二叉樹(shù)如圖1.17所示。對(duì)圖進(jìn)行后序遍歷的結(jié)果為DEBFCA。

　　總結(jié)：先根據(jù)前序遍歷或后序遍歷的結(jié)果，確定根結(jié)點(diǎn)，根據(jù)根結(jié)點(diǎn)確定左右予樹(shù)上的結(jié)點(diǎn)，再根據(jù)兩種遍歷畫(huà)出對(duì)應(yīng)的二叉樹(shù)，最后遍歷二叉樹(shù)得到第三種遍歷結(jié)果。

　　24[填空題]樹(shù)是-種簡(jiǎn)單的________(線性月)線性)結(jié)構(gòu)，在樹(shù)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的________特性。

　　參考解析：非線性

　　25[填空題]一棵二叉樹(shù)第六層(根結(jié)點(diǎn)為第-層)的結(jié)點(diǎn)數(shù)最多為_(kāi)_______個(gè)。

　　參考解析：

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

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

　　參考答案：A

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

　　參考答案：C

　　28[填空題]擁有奇數(shù)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中有4個(gè)內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))，請(qǐng)問(wèn)它的葉子結(jié)點(diǎn)數(shù)是________。

　　參考解析：5

　　【分析】由于完全二叉樹(shù)是自上而下、自左而右的從l開(kāi)始連續(xù)編碼的，因此完全二又樹(shù)要么不存在-度結(jié)點(diǎn)(當(dāng)結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)個(gè)時(shí))，要么存在一個(gè)-度結(jié)點(diǎn)，而且唯-的一個(gè)-度結(jié)點(diǎn)就是最后編號(hào)為n(n為偶數(shù))的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。而在二叉樹(shù)中零度結(jié)點(diǎn)個(gè)數(shù)總比二度結(jié)點(diǎn)個(gè)數(shù)多l(xiāng)，因此擁有4個(gè)二度結(jié)點(diǎn)的二叉樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)是4+1=5。

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

　　29[填空題]一棵二又樹(shù)第六層(根結(jié)點(diǎn)為第一層)的結(jié)點(diǎn)數(shù)最多為(　　)個(gè)。

　　參考解析：32

　　30[填空題]某--y.樹(shù)中度為2的結(jié)點(diǎn)有l(wèi)8個(gè)，則該--y.樹(shù)中有(　　)個(gè)葉子結(jié)點(diǎn)。

　　參考解析：19

　　【分析】在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。

　　31[填空題]擁有奇數(shù)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中有4個(gè)內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))，請(qǐng)問(wèn)它的葉子結(jié)點(diǎn)數(shù)是(　　)。

　　參考解析：5

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

　　參考解析：DEBFCA

　　圖1.17

　　33[填空題]樹(shù)是一種簡(jiǎn)單的(　　)(線性月}線性)結(jié)構(gòu)，在樹(shù)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的(　　)特性。

　　參考解析：非線性、層次

　　[填空題]設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有(　　)個(gè)葉子結(jié)點(diǎn)。

　　參考解析：350

　　相關(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道