武漢軟件工程職業(yè)學(xué)院軟件技術(shù)專業(yè)大二2019數(shù)據(jù)結(jié)構(gòu)二測

武漢軟件工程職業(yè)學(xué)院軟件技術(shù)專業(yè)大二2019數(shù)據(jù)結(jié)構(gòu)二測.樹形結(jié)構(gòu)中元素之間存在一個(gè)對多個(gè)的關(guān)系。［判斷題］*對（正確答案）錯(cuò).先根遍歷樹正好等同于按―遍歷對應(yīng)的二叉樹［單選題］*A.先根（正確答案）B.中根C.后根D層次.將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。［判斷題］*對錯(cuò)（正確答案）.后根遍歷樹正好等同于按—遍歷對應(yīng)的二叉樹。［單選題］*A.先根.中根（正確答案）C.后根D層次.赫夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。［判斷題］*對（正確答案）錯(cuò)

.赫夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。［判斷題］*對（正確答案）錯(cuò)為奇數(shù)答案解析：n個(gè)權(quán)值構(gòu)成的赫夫曼樹共有2n-1個(gè)節(jié)點(diǎn),為奇數(shù).樹最適合用來表示（）［單選題］*A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)（正確答案）D、元素之間無聯(lián)系的數(shù)據(jù).下面那個(gè)是完全二叉樹（）*B

BC（正確答案）D（正確答案）.以下關(guān)于樹和二叉樹的描述，正確的是（）［單選題］*各結(jié)點(diǎn)的度均為2的樹即為二叉樹任一遍歷序列可唯一確定一棵二叉樹任何樹都可以轉(zhuǎn)換為唯一的二叉樹與之對應(yīng)（正確答案）樹和二叉樹都只能用鏈?zhǔn)酱鎯?shí)現(xiàn).3個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有（）種［單選題］*345（正確答案）.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。［單選題］*24487253（正確答案）.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n-1個(gè)非空指針域。［判斷題］*對（正確答案）錯(cuò).二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。［判斷題］*對錯(cuò)（正確答案）.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。［判斷題］*對錯(cuò)（正確答案）.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。［判斷題］*對錯(cuò)（正確答案）.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。［判斷題］*對錯(cuò)（正確答案）.用二叉鏈表法（link-rlink）存儲包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。［判斷題］*對（正確答案）錯(cuò).具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。［判斷題］*對（正確答案）錯(cuò).二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）。［單選題］*A.它不能用順序存儲結(jié)構(gòu)存儲B.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲；C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲;（正確答案）D.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用18.設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說法不正確的是（）。［單選題］*A.T有n條邊（正確答案）B.T是連通的C.T是無環(huán)的D.T有n-1條邊14.高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0,如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（）。［單選題］*A.10B.11（正確答案）C.12D.135.如果樹根算第1層，那么一棵n層的二叉樹最多有（）個(gè)結(jié)點(diǎn)。［單選題］*A.2n-1（正確答案）B.2nC.2n+1D.2n+114、一個(gè)包含n個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空二叉樹，它的葉結(jié)點(diǎn)數(shù)目最多為（）。［單選題］*A.2n+1B.2n-1C.n-1D.n+1（正確答案）7.如果根結(jié)點(diǎn)的深度記為1,則一棵恰有2011個(gè)葉結(jié)點(diǎn)的二叉樹的深度最少是（）。［單選題］*A.10B.11C.12（正確答案）D.139.已知一棵二叉樹有10個(gè)節(jié)點(diǎn)，則其中至多有（）個(gè)節(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)。［單選題］*A.4（正確答案）B.5C.6D.75.完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是()。［單選題］*A.N-1B.N(正確答案)C.2*ND.2*N-116.一棵具有5層的滿二叉樹中結(jié)點(diǎn)數(shù)為()。［單選題］*A.31(正確答案)B.32C.33D.1617.如果根的高度為1,具有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為()。［單選題］*A.5B.6(正確答案)C.7D.819.完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點(diǎn)從上至下、從左至右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號位置，則第k號結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組的()號位置。［單選題］*A.2kB.2k+1C.k/2下取整(正確答案)D.(k+1)/2下取整20.已知6個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是123456（數(shù)字為結(jié)點(diǎn)的編號，以下同）,后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）［單選題］*A.321465B.321546（正確答案）C.213546D.23146520.已知7個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是1245637（數(shù)字為結(jié)點(diǎn)的編號，以下同），中根遍歷是4265173,則該二叉樹的后根遍歷是（）［單選題］*A.4652731（正確答案）B.4652137C.4231547D.465317213.二叉樹T，已知其先根遍歷是1243576（數(shù)字為結(jié)點(diǎn)的編號，以下同），中根遍歷是2415736,則該二叉樹的后根遍歷是（）。［單選題］*A.4257631B.4275631（正確答案）C.7425631D.427653117.一棵二叉樹的前序遍歷序列是ABCDEFG,后序遍歷序列是CBFEGDA,則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是（）。［單選題］*A.2（正確答案）B.3C.4D.56.如果一棵二叉樹的中序遍歷是BAC,那么它的先序遍歷不可能是（）。［單選題］*A.ABCB.CBAC.ACB（正確答案）D.BAC11.二叉樹的（）第一個(gè)訪問的節(jié)點(diǎn)是根節(jié)點(diǎn)。［單選題］*A.先序遍歷（正確答案）B.中序遍歷C.后序遍歷D.以上都是16.前序遍歷序列與中序遍歷序列相同的二叉樹為（）。［單選題］*A.根結(jié)點(diǎn)無左子樹B.根結(jié)點(diǎn)無右子樹C.只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有左子樹的二叉樹D.只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有右子樹的二叉樹（正確答案）13、表達(dá)式a*（b+c）-d的后綴表達(dá)式是：［單選題］*A.abcd*+-B.abc+*d-（正確答案）C.abc*+d-D.-+*abcd9.前綴表達(dá)式“+3*2+512的值是（）。［單選題］*A.23B.25C.37（正確答案）D.65.樹最適合用來表示（）［單選題］*A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)（正確答案）D、元素之間無聯(lián)系的數(shù)據(jù).在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（）。［單選題］*A、左子結(jié)點(diǎn)B、右子結(jié)點(diǎn)C、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)（正確答案）D、以上說法都不對.有三個(gè)結(jié)點(diǎn)的二叉樹有（）種形態(tài)。［單選題］*4正確答案，（ ）6.下面那個(gè)是完全二叉樹（）*

D（正確答案）43.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）［單選題］*A、9B、11（正確答案）C、15D、不確定.在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多是多少（）個(gè)？［單選題］*141516（正確答案）17答案解析：一棵二叉樹，如果每個(gè)結(jié)點(diǎn)都是是滿的，那么會滿足2Nk-1）1。所以第5層至多有2人（5-1）=16個(gè)結(jié)點(diǎn)！.深度為6的二叉樹最多有（）個(gè)結(jié)點(diǎn)。［單選題］*6463（正確答案）3231答案解析：見二叉樹性質(zhì).一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為（）個(gè)？［單選題］*218216219（正確答案）217答案解析：假設(shè)n表示二叉樹的所有結(jié)點(diǎn)數(shù)，n0表示度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)），n1表示度為1的結(jié)點(diǎn)，n2表示度為2的結(jié)點(diǎn)：n=n0+n1+n2,又由二叉樹性質(zhì)：n2=n0-1，將n2帶入得總結(jié)點(diǎn)數(shù)n=70+80+70-1=219.一棵具有5層的滿二叉樹中結(jié)點(diǎn)數(shù)為（）。［單選題］*A.31（正確答案）B.32C.33D.16.如果根的高度為1,具有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（）。［單選題］*A.56（正確答案）C.7D.8答案解析：根據(jù)二叉樹性質(zhì)，從所給答案中取值計(jì)算。49.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）？［單選題］*二叉樹的高度的公式是什么？1011至1025之間（正確答案）10至1024之間答案解析：若該二叉樹為完全二叉樹，根據(jù)二叉樹性質(zhì)或計(jì)算某一深度的滿二叉樹的結(jié)點(diǎn)總數(shù)，向下取整10g2（1025）+1alog2（102）4+1=log2（2八10）+1=10+1=11；或深度為10的滿二叉樹有2八10-1=1024-1=1023,1025>1023，所以至少11層。該二叉樹有至少有11層。層數(shù)最多時(shí)：每層一個(gè)結(jié)點(diǎn)，有1025層.已知一棵完全二叉樹含有1001個(gè)結(jié)點(diǎn)，那么它有（）個(gè)度為2的結(jié)點(diǎn)。［單選題］*250500（正確答案）501505答案解析：設(shè)二叉樹中度為0的葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為1結(jié)點(diǎn)個(gè)數(shù)為n1，度為2結(jié)點(diǎn)個(gè)數(shù)為n2,于是n0+n1+n2=1001根據(jù)二叉樹性質(zhì)：口0』2+1，代入得到，2n2+1+n1=1001由于完全二叉樹的n1只能是0或者1，為滿足2n2+1+n1=1001，只有n1=0時(shí)上式才能成立，因此n2=500，n0=501。此題有時(shí)也考葉子結(jié)點(diǎn)數(shù)目。.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷是（）。［單選題］*A.acbedB.decabC.deabcD.cedba（正確答案）.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：［單選題］*A.EB.FC.G（正確答案）D.H答案解析：注意審題，要求二叉樹根右子樹的根結(jié)點(diǎn)，由先序序列可知二叉樹的根結(jié)點(diǎn)為E，所以在中序序列中E的左子樹不需考慮。.表達(dá)式a*（b+c）-d的后綴表達(dá)式是：［單選題］*A.abcd*+-B.abc+*d-（正確答案）C.abc*+d-D.-+*abcd.完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點(diǎn)從上至下、從左至右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號位置，則第k號結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組的（）號位置。［單選題］*A.2kB.2k+1C.k/2下取整（正確答案）D.（k+1）/2下取整.以下說法錯(cuò)誤的是（）。［單選題］*樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨（正確答案）線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼樹形結(jié)構(gòu)可以表達(dá)（組織）更復(fù)雜的數(shù)據(jù)樹（及一切樹形結(jié)構(gòu)）是一種“分支層次“結(jié)構(gòu).以下說法正確的是（）。［單選題］*A.二叉樹不能用順序存儲結(jié)構(gòu)存儲B.二叉樹不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲；C.二叉樹順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲;（正確答案）D.二叉樹順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用3個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有（）種［單選題］*

45（正確答案）6.二叉樹的第i層上最多含有結(jié)點(diǎn)數(shù)為（）［單選題］*2的i次方2的i-1次方減12的i-1次方（正確答案）2的i次方減1.下列正確的是（）［單選題］*如圖如圖先序遍歷結(jié)果：ABCDFE中序遍歷結(jié)果：BDCAFE后序遍歷結(jié)果：DCBFEA（正確答案）［單選題］*.如果樹根算第1層，那么一棵n［單選題］*42~-1（正確答案）B.2A(n-1)C.2AnD.2An+1答案解析：根據(jù)二叉樹性質(zhì)，或讓n取簡單的值進(jìn)行計(jì)算，如n=2,n=3等。.已知一棵二叉樹有10個(gè)結(jié)點(diǎn)，則其中至多有()個(gè)度為2的結(jié)點(diǎn)。［單選題］*A.4(正確答案)B.5C.6D.7答案解析：設(shè)總結(jié)點(diǎn)數(shù)為n，度為0,1,2的結(jié)點(diǎn)數(shù)分別為no,n1,n2,則有：n=n0+n1+n2,根據(jù)二叉樹性質(zhì)將n0=n2+1和n=10帶入得：10=2n2+1+n1,要使n2最大，只有取n1=1，此時(shí)n2=4。.完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是()。［單選題］*A.N-1B.N(正確答案)C.2*ND.2*N-1答案解析：取N為某一具體值。.一棵具有5層的滿二叉樹中結(jié)點(diǎn)數(shù)為()。［單選題］*A.31(正確答案)B.32C.33D.16.具有1024個(gè)結(jié)點(diǎn)的二叉樹的深度為()。［單選題］*101024無法確定（正確答案）.線索二叉樹中，（）表示當(dāng)前節(jié)點(diǎn)的前驅(qū)。［單選題］*ltag=0時(shí)Ichildltag=1時(shí)Ichild（正確答案）rtag=1時(shí)rchildrtag=0時(shí)rchild.若二叉樹用二叉鏈表作存儲結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n-1個(gè)空指針域。［判斷題］*對錯(cuò)（正確答案）.某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為（）［單選題］*99100（正確答案）101102.二叉樹的深度為6，則二叉樹最多有（）個(gè)結(jié)點(diǎn)。［單選題］*A.1263（正確答案）C.64D.1169.用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點(diǎn)R[i]有右孩子，則其右孩子是()。[單選題]*A.R[2*i-1]B.R[2*i+1](正確答案)C.R[2*i]D.R[2/i]70.設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是()。[單選題]*A.a在b的右方B.a在b的左方(正確答案)C.a是b的祖先D.a是b的子孫.設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為()。[單選題]*A.adbceB.decabC.debacD.abc