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

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

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

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

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

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