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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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