武漢軟件工程職業(yè)學院軟件技術專業(yè)大二2019數據結構二測樹形結構中元素之間存在一個對多個的關系。［判斷題］*對（正確答案）錯先根遍歷樹正好等同于按—遍歷對應的二叉樹［單選題］*先根（正確答案）中根后根層次將一棵樹轉成二叉樹，根結點沒有左子樹。［判斷題］*對錯（正確答案）后根遍歷樹正好等同于按―遍歷對應的二叉樹。［單選題］*先根中根（正確答案）后根層次赫夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。［判斷題］*對（正確答案）錯赫夫曼樹的結點個數不能是偶數。［判斷題］*對（正確答案）錯答案解析：n個權值構成的赫夫曼樹共有2n-1個節(jié)點，為奇數樹最適合用來表示（）［單選題］*A、 有序數據兀素B、 無序數據元素C、 元素之間具有分支層次關系的數據（正確答案）D、 元素之間無聯(lián)系的數據下面那個是完全二叉樹（）*B

C（正確答案）D（正確答案）以下關于樹和二叉樹的描述，正確的是（）［單選題］*各結點的度均為2的樹即為二叉樹任一遍歷序列可唯一確定一棵二叉樹任何樹都可以轉換為唯一的二叉樹與之對應（正確答案）樹和二叉樹都只能用鏈式存儲實現(xiàn)3個結點構成的二叉樹，共有（）種［單選題］*345（正確答案）由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。［單選題］*24487253（正確答案）若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n-1個非空指針域。［判斷題］*對（正確答案）錯二叉樹中每個結點的兩棵子樹的高度差等于1。［判斷題］*對錯（正確答案）二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。［判斷題］*對錯（正確答案）二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。［判斷題］*對錯（正確答案）二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。［判斷題］*對錯（正確答案）用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。［判斷題］*對（正確答案）錯具有12個結點的完全二叉樹有5個度為2的結點。［判斷題］*對（正確答案）錯二叉樹是非線性數據結構，所以（）。［單選題］*它不能用順序存儲結構存儲它不能用鏈式存儲結構存儲；順序存儲結構和鏈式存儲結構都能存儲;（正確答案）順序存儲結構和鏈式存儲結構都不能使用18.設T是一棵有n個頂點的樹，下列說法不正確的是（）。［單選題］*T有n條邊（正確答案）T是連通的T是無環(huán)的T有n-1條邊14.高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。在這里，樹高等于葉結點的最大深度，根結點的深度為0,如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為（）。［單選題］*1011（正確答案）12135.如果樹根算第1層，那么一棵n層的二叉樹最多有（）個結點。［單選題］*2n-1（正確答案）TOC\o"1-5"\h\z2n2n+12n+114、一個包含n個分支結點（非葉結點）的非空二叉樹，它的葉結點數目最多為（）。［單選題］*A.2n+1B.2n-1C.n-1D.n+1（正確答案）7.如果根結點的深度記為1,則一棵恰有2011個葉結點的二叉樹的深度最少是（）。［單選題］*A.10B.11C.12（正確答案）D.139.已知一棵二叉樹有10個節(jié)點，則其中至多有（）個節(jié)點有2個子節(jié)點。［單選題］*4（正確答案）TOC\o"1-5"\h\z5675.完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數是()。［單選題］*TOC\o"1-5"\h\zN-1N(正確答案)2*N2*N-116.一棵具有5層的滿二叉樹中結點數為()。［單選題］*31(正確答案)32331617.如果根的高度為1,具有61個結點的完全二叉樹的高度為()。［單選題］*56(正確答案)7819.完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上至下、從左至右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置，則第k號結點的父結點如果存在的話，應當存放在數組的()號位置。［單選題］*2k2k+1k/2下取整(正確答案)(k+1)/2下取整20.已知6個結點的二叉樹的先根遍歷是123456（數字為結點的編號，以下同）,后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）［單選題］*321465321546（正確答案）21354623146520.已知7個結點的二叉樹的先根遍歷是1245637（數字為結點的編號，以下同），中根遍歷是4265173，則該二叉樹的后根遍歷是（）［單選題］*4652731（正確答案）46521374231547465317213.二叉樹T，已知其先根遍歷是1243576（數字為結點的編號，以下同），中根遍歷是2415736,則該二叉樹的后根遍歷是（）。［單選題］*42576314275631（正確答案）7425631427653117.一棵二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA,則根結點的左子樹的結點個數可能是（）。［單選題］*2（正確答案）TOC\o"1-5"\h\z3456.如果一棵二叉樹的中序遍歷是BAC，那么它的先序遍歷不可能是（）。［單選題］*A.ABCB.CBAC.ACB（正確答案）D.BAC11.二叉樹的（）第一個訪問的節(jié)點是根節(jié)點。［單選題］*先序遍歷（正確答案）中序遍歷后序遍歷以上都是16.前序遍歷序列與中序遍歷序列相同的二叉樹為（）。［單選題］*根結點無左子樹根結點無右子樹只有根結點的二叉樹或非葉子結點只有左子樹的二叉樹只有根結點的二叉樹或非葉子結點只有右子樹的二叉樹（正確答案）13、表達式a*（b+c）-d的后綴表達式是：［單選題］*abcd*+-abc+*d-（正確答案）abc*+d--+*abcd9.前綴表達式“+3*2+512的值是（）。［單選題］*232537正確答案）65樹最適合用來表示（）單選題］*A、 有序數據元素B、 無序數據元素C、 元素之間具有分支層次關系的數據正確答案）D、 元素之間無聯(lián)系的數據在完全二叉樹中，若一個結點是葉結點，則它沒（）。單選題］*入、左子結點B、 右子結點C、 左子結點和右子結點正確答案）D、 以上說法都不對有三個結點的二叉樹有（）種形態(tài)。單選題］*3正確答案6下面那個是完全二叉樹（）*BC（正確答案）D（正確答案）若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）［單選題］*A、 9B、 11（正確答案）C、 15D、 不確定在一棵二叉樹上第5層的結點數最多是多少（）個？［單選題］*141516（正確答案）17答案解析：一棵二叉樹，如果每個結點都是是滿的，那么會滿足2A（k-1）1o所以第5層至多有2八（5-1）=16個結點！深度為6的二叉樹最多有（）個結點。［單選題］*6463（正確答案）3231答案解析：見二叉樹性質-棵二叉樹中共有70個葉子結點與80個度為1的結點，則該二叉樹中的總結點數為（）個？［單選題］*218216219（正確答案）217答案解析：假設n表示二叉樹的所有結點數，n0表示度為0的結點（葉子結點），n1表示度為1的結點，n2表示度為2的結點：n=n0+n1+n2，又由二叉樹性質：n2=n0-1，將n2帶入得總結點數n=70+80+70-1=219一棵具有5層的滿二叉樹中結點數為（）。［單選題］*31（正確答案）TOC\o"1-5"\h\z323316如果根的高度為1,具有61個結點的完全二叉樹的高度為（）。［單選題］*56（正確答案）78答案解析：根據二叉樹性質，從所給答案中取值計算。-個具有1025個結點的二叉樹的高h為（）？［單選題］*二叉樹的高度的公式是什么？1011至1025之間（正確答案）10至1024之間答案解析：若該二叉樹為完全二叉樹，根據二叉樹性質或計算某一深度的滿二叉樹的結點總數，向下取整log2（1025）+1Qlog2（10羽+1=log2（2A10）+1=10+1=11;或深度為10的滿二叉樹有2八10-1=1024-1=1023,1025>1023,所以至少11層。該二叉樹有至少有11層。層數最多時：每層一個結點，有1025層已知一棵完全二叉樹含有1001個結點，那么它有（）個度為2的結點。［單選題］*250500（正確答案）501505答案解析：設二叉樹中度為0的葉子結點個數為n0，度為1結點個數為n1，度為2結點個數為n2,于是n0+n1+n2=1001根據二叉樹性質：n0=n2+1，代入得到，2n2+1+n1=1001由于完全二叉樹的n1只能是0或者1，為滿足2n2+1+n1=1001，只有n1=0時上式才能成立，因此n2=500，n0=501。此題有時也考葉子結點數目。已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷是（）。［單選題］*acbeddecabdeabccedba（正確答案）二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：［單選題］*EFG（正確答案）H答案解析：注意審題，要求二叉樹根右子樹的根結點，由先序序列可知二叉樹的根結點為E，所以在中序序列中E的左子樹不需考慮。表達式a*（b+c）-d的后綴表達式是：［單選題］*abcd*+-abc+*d-（正確答案）abc*+d--+*abcd完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上至下、從左至右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置，則第k號結點的父結點如果存在的話，應當存放在數組的（）號位置。［單選題］*2k2k+1k/2下取整（正確答案）（k+1）/2下取整以下說法錯誤的是（）。［單選題］*樹形結構的特點是一個結點可以有多個直接前趨（正確答案）線性結構中的一個結點至多只有一個直接后繼樹形結構可以表達（組織）更復雜的數據樹（及一切樹形結構）是一種"分支層次"結構以下說法正確的是（）。［單選題］*'二叉樹不能用順序存儲結構存儲=叉樹不能用鏈式存儲結構存儲；仁二叉樹順序存儲結構和鏈式存儲結構都能存儲;（正確答案）。.二叉樹順序存儲結構和鏈式存儲結構都不能使用3個結點構成的二叉樹，共有（）種［單選題］*

45（正確答案）6二叉樹的第i層上最多含有結點數為（）［單選題］*2的i次方2的i-1次方減12的i-1次方（正確答案）2的i次方減1下列正確的是（）［單選題］*如圖如圖先序遍歷結果：ABCDFE中序遍歷結果：BDCAFE后序遍歷結果：DCBFEA（正確答案）［單選題］*如果樹根算第1層，那么一棵n層的二叉樹最多有（）［單選題］*25-1（正確答案）2A(n-1)2An2An+1答案解析：根據二叉樹性質，或讓n取簡單的值進行計算，如n=2,n=3等。已知一棵二叉樹有10個結點，則其中至多有()個度為2的結點。［單選題］*4(正確答案)TOC\o"1-5"\h\z567答案解析：設總結點數為n，度為0,1,2的結點數分別為no,n1,n2,則有：n=n0+n1+n2,根據二叉樹性質將n0=n2+1和n=10帶入得：10=2n2+1+n1,要使n2最大，只有取n1=1，此時n2=4。完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數是()。［單選題］*TOC\o"1-5"\h\zN-1N(正確答案)2*N2*N-1答案解析：取N為某一具體值。一棵具有5層的滿二叉樹中結點數為()。［單選題］*31(正確答案)323316具有1024個結點的二叉樹的深度為()。［單選題］*1024無法確定（正確答案）線索二叉樹中，（）表示當前節(jié)點的前驅。［單選題］*ltag=0時Ichildltag=1時Ichild（正確答案）rtag=1時rchildrtag=0時rchild若二叉樹用二叉鏈表作存儲結構，則在n個結點的二叉樹鏈表中只有n-1個空指針域。［判斷題］*對錯（正確答案）某哈夫曼樹中有199個結點，則其葉子結點的個數為（）［單選題］*99100（正確答案）101102二叉樹的深度為6，則二叉樹最多有（）個結點。［單選題］*TOC\o"1-5"\h\z1263（正確答案）6411用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數組R[1..N]中，若結點R[i]有右孩子，則其右孩子是()。[單選題]*R[2*i-1]R[2*i+1](正確答案)R[2*i]R[2/i]設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前面的條件是()。[單選題]*a在b的右方a在b的左方(正確答案)a是b的祖先a是b的子孫設一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為()。[單選題]*adbcedecabdebacabcde(正確答案)在一棵具有5層的完全二叉樹中結點總數至少為()。[單選