二級MSOffice高級應(yīng)用(新大綱)選擇題題目、解析及答案(樹、二叉樹_第1頁
二級MSOffice高級應(yīng)用(新大綱)選擇題題目、解析及答案(樹、二叉樹_第2頁
二級MSOffice高級應(yīng)用(新大綱)選擇題題目、解析及答案(樹、二叉樹_第3頁
二級MSOffice高級應(yīng)用(新大綱)選擇題題目、解析及答案(樹、二叉樹_第4頁
二級MSOffice高級應(yīng)用(新大綱)選擇題題目、解析及答案(樹、二叉樹_第5頁
已閱讀5頁,還剩12頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐ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é)點有幾個分叉,度就是幾。樹的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論