二級(jí)MSOffice高級(jí)應(yīng)用(新大綱)選擇題題目、解析及答案(樹(shù)、二叉樹(shù)

1、二級(jí)MS OffiCe高級(jí)應(yīng)用(新大綱)選擇題題目、解析及答案(樹(shù)、二叉樹(shù))1. 某二叉樹(shù)有 5 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是()。A ) 10B ) 8C ) 6D) 4 參考答案： C解析：二叉樹(shù)中，葉子結(jié)點(diǎn)(度為 0的結(jié)點(diǎn))是度為 2的結(jié)點(diǎn)個(gè)數(shù)加 1。2. 下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是( )。A) 循環(huán)隊(duì)列B) 帶鏈隊(duì)列C) 二叉樹(shù)D) 帶鏈棧 參考答案： C 解析：隊(duì)列、棧是線性結(jié)構(gòu)；樹(shù)是非線性結(jié)構(gòu)。3. 下列敘述中正確的是( )。A) 有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B) 只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C) 循環(huán)鏈表是非線性結(jié)構(gòu)D) 雙向

2、鏈表是非線性結(jié)構(gòu) 參考答案： B 解析：例如，只有一個(gè)根結(jié)點(diǎn)的樹(shù)，其是非線性結(jié)構(gòu)。4. 一棵二叉樹(shù)共有 25個(gè)結(jié)點(diǎn)，其中 5 個(gè)是葉子結(jié)點(diǎn)，則度為 1的結(jié)點(diǎn)數(shù)為( )A) 16B) 10C) 6D) 4參考答案：A解析：在一棵二叉樹(shù)中只有度為0、1、2三種結(jié)點(diǎn)。且二叉樹(shù)中，葉子結(jié)點(diǎn) （度為0的結(jié)點(diǎn)）是度為2的結(jié)點(diǎn)個(gè)數(shù)加1。所以，度為2的結(jié)點(diǎn)是4,度為1的結(jié)點(diǎn) 是 25-5-4=16。5. 某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹(shù)的深度為（假 設(shè)根結(jié)點(diǎn)在第1層）（）。A）3B）4C）6D）7參考答案：D解析：在一棵二叉樹(shù)中只有度為 0、1、2三種結(jié)點(diǎn)。且二叉樹(shù)中，葉子結(jié) 點(diǎn)（度為0

3、的結(jié)點(diǎn)）是度為2的結(jié)點(diǎn)個(gè)數(shù)加1。所以，度為2的結(jié)點(diǎn)是0,度為 1的結(jié)點(diǎn)是7-1-0=6。除葉結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)都有一個(gè)分支。每個(gè)結(jié)點(diǎn)在一層， 共7層，如下圖所示：6. 對(duì)下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為（）A) DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ 參考答案： C 解析：先（前）序遍歷的遞歸算法定義： 若二叉樹(shù)非空，則依次執(zhí)行如下操作： 訪問(wèn)根結(jié)點(diǎn)； 遍歷左子樹(shù)； 遍歷右子樹(shù)。遍歷過(guò)程發(fā)下：1：先訪問(wèn)根結(jié)點(diǎn)： A2:遍歷A的左子樹(shù)（遞歸調(diào)用）；2_1:先訪問(wèn)A的左子樹(shù)的根結(jié)點(diǎn)：2_2:遍歷B的左子樹(shù)（遞歸調(diào)用）；2_2_1:先訪問(wèn)B的左子樹(shù)的根結(jié)點(diǎn)

4、:2_2_2:遍歷D的左子樹(shù)（遞歸調(diào)用）2_2_3:遍歷D的右子樹(shù)（遞歸調(diào)用）2_2_3_1:遍歷D的右子樹(shù)的根結(jié)點(diǎn): 溯。2_3:遍歷B的右子樹(shù)（遞歸調(diào)用）；2_3_1:先訪問(wèn)B的右子樹(shù)的根結(jié)點(diǎn): 溯。3:遍歷A的右子樹(shù)（遞歸調(diào)用）；BD, 沒(méi)有左子樹(shù)；Y;至此，B的左子樹(shù)遍歷完，向上回E;至此，B的右子樹(shù)遍歷完，向上回依次類(lèi)推:7. 某二叉樹(shù)的前序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為（ ）。A）FEDCBAB）BCDEFAC）DEFABCD）ABCDEF參考答案：D解析：先（前）序遍歷的遞歸算法定義：若二叉樹(shù)非空，則依次執(zhí)行如下操作：訪問(wèn)根結(jié)

5、點(diǎn)；遍歷左子樹(shù)；遍歷右子樹(shù)。中序遍歷的遞歸算法定義：若二叉樹(shù)非空，則依次執(zhí)行如下操作：遍歷左子樹(shù)；訪問(wèn)根結(jié)點(diǎn)遍歷右子樹(shù)。通過(guò)前序遍歷和中序遍歷可以確定一棵二叉樹(shù)，（1）前序遍歷確定根結(jié)點(diǎn)（2）中序遍歷確定左、右子樹(shù)（3）依次循環(huán)，直到確定整棵二叉樹(shù)解題過(guò)程：1. 前序：ABCDEJF可知A是根結(jié)點(diǎn)；2. 中序：A右子樹(shù)（BCDEF ；3. 對(duì)右子樹(shù)BCDEF前序遍歷：可知B是根結(jié)點(diǎn)；4. 中序：B右子樹(shù)（CDEF ；依此類(lèi)推：可知該樹(shù)所有結(jié)點(diǎn)均在右子樹(shù)上，且每一個(gè)父結(jié)點(diǎn)均只有右子樹(shù), 如下圖所示。所以，答案選DO8. 某二叉樹(shù)的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF,貝U按層次輸

6、出(同一層從左到右)的序列為()。A) ABCDEFB) CBAFEDC) DEFCBAD) FEDCBA參考答案：D解析：后序遍歷的遞歸算法定義：若二叉樹(shù)非空，則依次執(zhí)行如下操作：遍歷左子樹(shù)；遍歷右子樹(shù)；訪問(wèn)根結(jié)點(diǎn)。中序遍歷的遞歸算法定義：若二叉樹(shù)非空，則依次執(zhí)行如下操作：遍歷左子樹(shù)；訪問(wèn)根結(jié)點(diǎn)遍歷右子樹(shù)。通過(guò)后序遍歷和中序遍歷可以確定一棵二叉樹(shù)，(1) 后序遍歷確定根結(jié)點(diǎn)(2) 中序遍歷確定左、右子樹(shù)(3) 依次循環(huán)，直到確定整棵二叉樹(shù)解題過(guò)程：1. 后序：ABCDE,可知F是根結(jié)點(diǎn)；2. 中序：左子樹(shù)（ABCDE F;3. 對(duì)左子樹(shù)ABCDE后序遍歷：可知E是根結(jié)點(diǎn)；4. 中序：左子樹(shù)（

7、ABCD E；依此類(lèi)推：可知該樹(shù)所有結(jié)點(diǎn)均在左子樹(shù)上，且每一個(gè)父結(jié)點(diǎn)均只有左子樹(shù), 如下圖所示。9. 某完全二叉樹(shù)按層次輸出（同一層從左到右）的序列為ABCDEFGH亥完全叉樹(shù)的前序序列為（）。A）ABCDEFGHB）ABDHECFGC）HDBEAFCGD）HDEBFGCA參考答案：B 解析：滿二叉樹(shù)：除最后一層無(wú)任何子 節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的完全二叉樹(shù)：設(shè)二叉樹(shù)的深度為h,除第h層外，其它各層（1h-1）的結(jié)點(diǎn) 數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉 樹(shù)。示例見(jiàn)下圖：若二叉樹(shù)非空，則依次執(zhí)行如下操作：訪問(wèn)根結(jié)點(diǎn)；遍歷左子樹(shù)；遍歷右子樹(shù)。則完全

8、二叉樹(shù)的前序遍歷為：1.根（A）- 1.1根（A）的左子樹(shù)-1.2根（A）的右子樹(shù);1.1遍歷根（A）的左子樹(shù)：根（B）- 1.1.1根（B）的左子樹(shù)-1.1.2 根（B） 的右子樹(shù)；1.1.1遍歷根（B）的左子樹(shù)：根（D）- 1.1.1.1根（D）的左子樹(shù)-1.1.1.2 根（D）的右子樹(shù)；1.1.1.1遍歷根（D）的左子樹(shù)：根（H）- 根（H）的左子樹(shù)為空-根（H）的 右子樹(shù)為空；1.1.1.2遍歷根（D）的右子樹(shù)為空1.1.2遍歷根（B）的右子樹(shù)：根（E）- 根（ E的左子樹(shù)為空-根（D）的右 子樹(shù)為空；1.2遍歷根（A）的右子樹(shù)：根（C）- 1.2.1根（C）的左子樹(shù)-1.2.2 根（

9、C） 的右子樹(shù)；1.2.1遍歷根（C）的左子樹(shù)：根（F）- 根（ F）的左子樹(shù)為空-根（F）的右 子樹(shù)為空；I. 2.2遍歷根（C）的右子樹(shù)：根（G）- 根 （ Q的左子樹(shù)為空-根（Q的右 子樹(shù)為空；至此，前序遍歷結(jié)束，依次訪問(wèn)到的結(jié)點(diǎn)為：ABDHECFG10. 設(shè)非空二叉樹(shù)的所有子樹(shù)中，其左子樹(shù)上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值，而右子 樹(shù)上的結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值，則稱該二叉樹(shù)為排序二叉樹(shù)。對(duì)排序二叉樹(shù) 的遍歷結(jié)果為有序序列的是（）。A）中序序列B）前序序列C）后序序列D）前序序列或后序序列 參考答案：A前序遍歷：訪問(wèn)根結(jié)點(diǎn)- 遍歷左子樹(shù)- 遍歷右子樹(shù)。中序遍歷：遍歷左子樹(shù)- 訪問(wèn)根結(jié)點(diǎn)- 遍歷右子

10、樹(shù)。后序遍歷：遍歷左子樹(shù)- 遍歷右子樹(shù)- 訪問(wèn)根結(jié)點(diǎn)。根據(jù)前面3種遍歷特點(diǎn)可知，該排序樹(shù)使用中序遍歷為從小到大排序，符合要求。II. 在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，葉子結(jié)點(diǎn)個(gè)數(shù)為（）A) n/2B) n-1C) nD) n+1參考答案：C 解析:滿二叉樹(shù)：除最后一層無(wú)任何子 節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的h,除第h層外，其它各層（1h-1）的結(jié)點(diǎn)17數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉此處，依據(jù)完全二叉樹(shù)的定義，設(shè) n=1 ,畫(huà)出2n=2個(gè)結(jié)點(diǎn)的完全二叉樹(shù)如下圖 所示:通過(guò)觀察可知，葉子結(jié)點(diǎn)個(gè)數(shù)為1,即n個(gè)。12.某二叉樹(shù)的中序遍歷序列為 CBAD

11、E ,后序遍歷序列為CBADE ,則前序遍歷 序列為（）。A）CBADEB）CBEDAC）EDABCD）EDCBA參考答案：C解析：前序遍歷：訪問(wèn)根結(jié)點(diǎn)- 遍歷左子樹(shù)- 遍歷右子樹(shù)。中序遍歷：遍歷左子樹(shù)- 訪問(wèn)根結(jié)點(diǎn)- 遍歷右子樹(shù)。后序遍歷：遍歷左子樹(shù)- 遍歷右子樹(shù)- 訪問(wèn)根結(jié)點(diǎn)。后序遍歷確定根結(jié)點(diǎn)，中序遍歷確定左右子樹(shù)。貝1. 后序遍歷序列為CBADE根結(jié)點(diǎn)為EO2. 中序遍歷序列為CBADE有左子樹(shù)（CBAD -根（E）-右子樹(shù)（空）。2.1左子樹(shù)（CBAD的后序遍歷為：CBAD根結(jié)點(diǎn)為DO2.2左子樹(shù)（CBAD的中序遍歷為CBAD有左子樹(shù)（CBA-根（D）-右子樹(shù)（空）。2.2.1左子樹(shù)

12、（CBA的后序遍歷為：CBA,根結(jié)點(diǎn)為Ao2.2.2左子樹(shù)（CBA的中序遍歷為CBA有左子樹(shù)（CB -根（A）-右子樹(shù)（空）。2.2.2.1左子樹(shù)（CB）的后序遍歷為：CB,根結(jié)點(diǎn)為Bo2.2.2.2左子樹(shù)（CB的中序遍歷為CB有左子樹(shù)（C）-根（B）-右子樹(shù)（空）。 則此二叉樹(shù)如下圖所示：前序遍歷：1.訪問(wèn)根結(jié)點(diǎn)E-2.遍歷左子樹(shù)2.1訪問(wèn)根結(jié)點(diǎn)D-2.2遍歷左子樹(shù)2.2.1訪問(wèn)根結(jié)點(diǎn) A-2.2.2遍歷左子樹(shù) 2.2.2.1 訪問(wèn)根結(jié)點(diǎn)B-2.2.2.2 遍 歷左子樹(shù) 2.2.2.2.1 訪問(wèn)根結(jié)點(diǎn)C-2.2.2.2.2 遍歷左子樹(shù)（空）-2.2.2.2.3 遍歷右子樹(shù)（空） -2.2.2

13、.3 遍歷右子樹(shù)（空） -2.2.3 遍歷右子樹(shù)（空） -2.3遍歷右子樹(shù)（空）-3.遍歷右子樹(shù)（空）。13. 設(shè)一棵樹(shù)的度為4,其中度為4, 3, 2, 1的結(jié)點(diǎn)個(gè)數(shù)分別為2, 3, 3, 0。 則該棵樹(shù)中的葉子結(jié)點(diǎn)數(shù)為（）。A）16B）15C）17D）不可能有這樣的樹(shù)參考答案：A解析：結(jié)點(diǎn)的度：有根樹(shù)T中，結(jié)點(diǎn)X的子女?dāng)?shù)目稱為X的度。也就是：在樹(shù)中，結(jié)點(diǎn) 有幾個(gè)分叉，度就是幾。樹(shù)的度：有根樹(shù)T中，結(jié)點(diǎn)的最大度數(shù)即為樹(shù)的度。樹(shù)中結(jié)點(diǎn)數(shù)=總分叉數(shù)+1。（這里的分叉數(shù)就是所有結(jié)點(diǎn)的度之和）樹(shù)中結(jié)點(diǎn)數(shù)=4 2+3 3+2 3+1 0+ 仁8+9+6+ 仁24設(shè)葉子結(jié)點(diǎn)為X,則有：2+3+3+X=2

14、4所以X=1614. 某二叉樹(shù)共有399個(gè)結(jié)點(diǎn)，其中有199個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉 子結(jié)點(diǎn)數(shù)為（）。A）不存在這樣的二叉樹(shù)B）200C）198D）199參考答案：B解析：二叉樹(shù)中，葉子結(jié)點(diǎn)（度為 0的結(jié)點(diǎn)）是度為2的結(jié)點(diǎn)個(gè)數(shù)加115. 下列敘述中錯(cuò)誤的是（）。A）向量是線性結(jié)構(gòu)B）非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有前件C）非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有后件D）只有一個(gè)根結(jié)點(diǎn)和一個(gè)葉子結(jié)點(diǎn)的結(jié)構(gòu)必定是線性結(jié)構(gòu)參考答案：D解析：如下所示二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)和一個(gè)葉子結(jié)點(diǎn)，其是非線性結(jié)構(gòu)。16. 設(shè)某二叉樹(shù)中共有140個(gè)結(jié)點(diǎn)，其中有40個(gè)度為1的結(jié)點(diǎn)。則（）A）該二叉樹(shù)中有51個(gè)葉子結(jié)點(diǎn)B）該

15、二叉樹(shù)中有50個(gè)葉子結(jié)點(diǎn)C）該二叉樹(shù)中有51個(gè)度為2的結(jié)點(diǎn)D）不可能有這樣的二叉樹(shù)參考答案：D解析：二叉樹(shù)中，葉子結(jié)點(diǎn)（度為0的結(jié)點(diǎn)）是度為2的結(jié)點(diǎn)個(gè)數(shù)加1。設(shè)度為2的結(jié)點(diǎn)個(gè)數(shù)為X,則葉子結(jié)點(diǎn)個(gè)數(shù)為X+1；40+X+X+1=1402X=99X=44.5顯然沒(méi)有這樣的二叉樹(shù)。17. 設(shè)二叉樹(shù)的前序序列為 ABDEGHCFIJ中序序列為DBGEHACIFJ則按層次輸 出（從上到下，同一層從左到右）的序列為（ ）。A）ABCDEFGHIJB）DGHEBIJFCAC）JIHGFEDCBAD）GHIJDEFBCA參考答案： A 解析：前序遍歷：訪問(wèn)根結(jié)點(diǎn) -遍歷左子樹(shù) - 遍歷右子樹(shù)。 中序遍歷：遍歷左

16、子樹(shù) - 訪問(wèn)根結(jié)點(diǎn) - 遍歷右子樹(shù)。 后序遍歷：遍歷左子樹(shù) - 遍歷右子樹(shù) - 訪問(wèn)根結(jié)點(diǎn)。前序序列為ABDEGHCF,可知根為A。給定答案中只有選項(xiàng)A符合。18. 設(shè)二叉樹(shù)的前序序列為 ABDEGHCFIJ中序序列為DBGEHACIFJ則后序序列 為（ ）。A）DGHEBIJFCAB）JIHGFEDCBAC）GHIJDEFBCAD）ABCDEFGHIJ 參考答案： A解析：前序遍歷：訪問(wèn)根結(jié)點(diǎn) -遍歷左子樹(shù) - 遍歷右子樹(shù)。 中序遍歷：遍歷左子樹(shù) - 訪問(wèn)根結(jié)點(diǎn) - 遍歷右子樹(shù)。 后序遍歷：遍歷左子樹(shù) - 遍歷右子樹(shù) - 訪問(wèn)根結(jié)點(diǎn)。前序序列為ABDEGHCF，可知根為AO中序序列可知：左

17、子樹(shù)（DBGE）-根（A）-右子樹(shù)（CIFJ）O根據(jù)后序遍歷的定義可知，只有選項(xiàng)A符合定義。19. 設(shè)某棵樹(shù)的度為 3，其中度為 3,2,1 的結(jié)點(diǎn)個(gè)數(shù)分別為 3,0,4 。 則該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為（ ）。A）6B）7C）8D) 不可能有這樣的樹(shù) 參考答案： B解析：結(jié)點(diǎn)的度：有根樹(shù)T中，結(jié)點(diǎn)X的子女?dāng)?shù)目稱為X的度。也就是：在樹(shù)中， 結(jié)點(diǎn)有幾個(gè)分叉，度就是幾。樹(shù)的度：有根樹(shù)T中，結(jié)點(diǎn)的最大度數(shù)即為樹(shù)的度。樹(shù)中結(jié)點(diǎn)數(shù) = 總分叉數(shù) +1。 (這里的總分叉數(shù)就是所有結(jié)點(diǎn)的度之和 ) 樹(shù)中結(jié)點(diǎn)數(shù) =3 3+2 0+14+1=9+4+1=14設(shè)葉子結(jié)點(diǎn)為X,則有：3+4+X=14所以X=720. 度為

18、 3的一棵樹(shù)共有 30個(gè)結(jié)點(diǎn)，其中度為 3、1 的結(jié)點(diǎn)個(gè)數(shù)分別為 3、4。 則該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為( )。A) 14B) 15C) 16D) 不可能有這樣的樹(shù) 參考答案： B解析：結(jié)點(diǎn)的度：有根樹(shù)T中，結(jié)點(diǎn)X的子女?dāng)?shù)目稱為X的度。也就是：在樹(shù)中， 結(jié)點(diǎn)有幾個(gè)分叉，度就是幾。樹(shù)的度：有根樹(shù)T中，結(jié)點(diǎn)的最大度數(shù)即為樹(shù)的度。 樹(shù)中結(jié)點(diǎn)數(shù) = 總分叉數(shù) +1 。 (這里的總分叉數(shù)就是所有結(jié)點(diǎn)的度之和 )設(shè)度為2的結(jié)點(diǎn)個(gè)數(shù)為X,樹(shù)中結(jié)點(diǎn)數(shù)=3 3+2X+1 4+仁9+2X+4+1=30X=8設(shè)葉子結(jié)點(diǎn)為丫，則有：3+8+4+Y=30所以丫=1521. 設(shè)某棵樹(shù)的度為 3，其中度為 3、1、0的結(jié)點(diǎn)個(gè)數(shù)分

19、別為 3、4、15。則該樹(shù) 中總結(jié)點(diǎn)數(shù)為( )。A) 22B) 30C) 35D) 不可能有這樣的樹(shù)參考答案： B 解析：見(jiàn)上題。22. 某完全二叉樹(shù)有 256 個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為( )。A) 7B) 8C) 9D) 10參考答案： C解析：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為匚log 2j +1。23. 設(shè)二叉樹(shù)中有 20個(gè)葉子結(jié)點(diǎn)， 5個(gè)度為 1的結(jié)點(diǎn)，則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù) 為( )。A) 46B) 45C) 44D) 不可能有這樣的二叉樹(shù)參考答案： C解析：二叉樹(shù)中度為 0 的結(jié)點(diǎn)(葉子結(jié)點(diǎn))數(shù)是度為 2 的結(jié)點(diǎn)數(shù) +1；所以度為 2 的結(jié)點(diǎn)數(shù)為 19；樹(shù)中的總結(jié)點(diǎn)數(shù)為： 20+19+5=44。24. 樹(shù)的度為 3，且有 9 個(gè)度為 3 的結(jié)點(diǎn)， 5個(gè)度為 1 的結(jié)點(diǎn)，但沒(méi)有度為 2的 結(jié)點(diǎn)。則該樹(shù)總的結(jié)點(diǎn)數(shù)為( )。A) 32B) 14C) 33D) 19參考答案： C解析：結(jié)點(diǎn)的度：有根樹(shù)T中，結(jié)點(diǎn)X的子女?dāng)?shù)目稱為X的度。也就是：在樹(shù)中， 結(jié)點(diǎn)有幾個(gè)分叉，度就是幾。樹(shù)的