計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(樹和二叉樹)歷年真題試卷匯編12

1、計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（樹和二叉樹）歷年真題試卷匯編12(總分：62.00，做題時(shí)間：90 分鐘)一、 單項(xiàng)選擇題(總題數(shù)：15，分?jǐn)?shù)：30.00)后的結(jié)點(diǎn)序列為 3，1，7，5，6，2，4，則其遍歷方式是( )?！?009 年全國(guó)試題 3(2 分)】給定二叉樹如下圖所示。設(shè)N 代表二叉樹的根，L 代表根結(jié)點(diǎn)的左子樹，R 代表根結(jié)點(diǎn)的右子樹。若遍歷A.LRN B.NRL C.RLN D.KNL已知一棵完全二叉樹的第6 層(設(shè)根是第1 層)有8 個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是( )【。2009年全國(guó)試題 5(2 分)】A.39 B.52C.11 1D.119本題問“完全二叉樹的結(jié)點(diǎn)

2、個(gè)數(shù)最多是多少”。完全二叉樹的葉子至多只能在最下面兩層上。本題告訴第6 層有 8 個(gè)葉子，還會(huì)有 24 個(gè)分支結(jié)點(diǎn)，其在第 7 層最多有 48 個(gè)葉子，故選 C。若說第 6 層只有 8 個(gè)葉子， 則應(yīng)選 A。將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u 是結(jié)點(diǎn) v 的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u 和 v 可能具有的關(guān)系是( )?！?009 年全國(guó)試題 6(2 分)】I父子關(guān)系 兄弟關(guān)系u 的父結(jié)點(diǎn)與 v 的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有B.I 和C.I 和D.I、和I 指的是二叉樹中v 是u 的左子女的右子女，指的是二叉樹中v 是u 的右子女的右子女。若成立，則森林轉(zhuǎn)換的二叉樹中，u 不可

3、能是v 的父結(jié)點(diǎn)的父結(jié)點(diǎn)。故選B。A.B.下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是( )?！?010 年全國(guó)試題 3(2 分)】C.D.在一棵度為 4 的樹T 中，若有20 個(gè)度為 4 的結(jié)點(diǎn)，10 個(gè)度為 3 的結(jié)點(diǎn)，1 個(gè)度為 2 的結(jié)點(diǎn)，10 個(gè)度為 1 的結(jié)點(diǎn)，則樹 T 的葉結(jié)點(diǎn)個(gè)數(shù)是( )。 【2010 年全國(guó)試題 5(2 分)】A.41B.82 C.113 D.122度為 m 的樹中，葉子結(jié)點(diǎn)個(gè)數(shù)的求解公式是其中，n是度i 的結(jié)點(diǎn)數(shù)。i對(duì)n(n2)個(gè)權(quán)值均不相同的字符構(gòu)造哈夫曼樹。下列關(guān)于該哈夫曼樹的敘述中，錯(cuò)誤的是( )?！?010年全國(guó)試題 6(2 分)】該樹

4、一定是一棵完全二叉樹樹中一定沒有度為 1 的結(jié)點(diǎn)樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值若一棵完全二又樹有 768 個(gè)結(jié)點(diǎn)，則該二又樹中葉結(jié)點(diǎn)的個(gè)數(shù)是( )。 【2011 年全國(guó)試題 4(2 分)】A.257 B.258C.384D.385因?yàn)?n=n+n+n012，n=n20-1，所以n=2n+n0-1。在完全二叉樹中，n1取 1 或 0。這里 n=768，1n。只能為 1，故選C。在完全二叉樹結(jié)點(diǎn)計(jì)算中，僅知一個(gè)量(總結(jié)點(diǎn)數(shù)，葉子數(shù)，度為 2 的結(jié)點(diǎn)數(shù))求1其他量，一般就利用該公式。下面的 3133 題都是該關(guān)系式的應(yīng)用。若一棵二叉樹的前序遍

5、歷序列和后序遍歷序列分別是 1，2，3，4 和 4，3，2，1，則該二叉樹的中序遍歷序列不會(huì)是( )。 【2011 年全國(guó)試題 5(2 分)】A.1，2，3，4 B.2，3，4，1 C.3，2，4，1 D.4，3，2，1前序遍歷序列和后序遍歷序列相反的二叉樹是高度等于結(jié)點(diǎn)數(shù)的二叉樹，或說只有一個(gè)葉子結(jié)點(diǎn)的二叉樹， 或說每個(gè)分支結(jié)點(diǎn)至多只有左子女或只有右子女的二叉樹。中序遍歷的第一個(gè)結(jié)點(diǎn)是二叉樹最左面的結(jié)點(diǎn)。A 是分支結(jié)點(diǎn)只有右子樹的二叉樹，D 是分支結(jié)點(diǎn)只有左子樹的二叉樹，B 是以 1 為根，2 是 1 的左子女，3 是 2 的右子女，4 是 3 的右子女。已知一棵有 2011 個(gè)結(jié)點(diǎn)的樹，其

6、葉結(jié)點(diǎn)個(gè)數(shù)為 116，該樹對(duì)應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是( )。【2011 年全國(guó)試題 6(2 分)】A.115B.1 16 C.1895D.1 896該樹非終端結(jié)點(diǎn)的個(gè)數(shù)為 2011-116=1895。樹在轉(zhuǎn)換成二叉樹時(shí)，非終端結(jié)點(diǎn)子女中的最右子女結(jié)點(diǎn)的右指針為空(即最右子女無右孩子)。另外，森林中各棵樹互為兄弟，轉(zhuǎn)換為二叉樹時(shí)最右一棵樹根結(jié)點(diǎn)的右指針為空。1895+1=1896，故選D。若一棵二叉樹的前序遍歷序列為a，e，b，d,c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)( )。 2012 年全國(guó)試題 3(2 分)】只有e有e、b有e、c D.無法確定二叉樹前序遍歷序列的

7、第一個(gè)結(jié)點(diǎn)是根。若遍歷序列多于一個(gè)結(jié)點(diǎn)，則第二個(gè)結(jié)點(diǎn)應(yīng)是左子樹的根，若無左子樹則是右子樹的根。對(duì)后序遍歷的分析類似。本題從前序序列分析 e 肯定是孩子，b 也可能是，但結(jié)合對(duì)后序序列的分析，孩子只能是 e。另外，本題也可這樣分析。先假定前序序列第二個(gè)結(jié)點(diǎn)e 是根a 的左子女。后序遍歷是“左一右一根”，在后序序列中 e 的左面是以e 為根的左子樹，r 的右面直到最后結(jié)點(diǎn)(根結(jié)點(diǎn))苴的結(jié)點(diǎn)屬于以a 為根的右子樹。實(shí)際上 e 和a 相鄰，說明 a 無右子樹。若前序序列中e 是根a 的右子女(該二叉樹無左子樹)，則后序序列中 e 和 a 應(yīng)該相鄰，事實(shí)的確如此。已知三叉樹T 中 6 個(gè)葉結(jié)點(diǎn)的權(quán)分別是

8、 2，3，4，5，6，7，T 的帶權(quán)(外部)路徑長(zhǎng)度最小是( )。【2013年全國(guó)試題 4(2 分)】A.27B.46 C.54 D.56WPL=(2+3)*3+(4+5)*2+(6+7)*1=46對(duì)尼叉樹，設(shè) m 為葉子數(shù)，若(m 一 1)(k-1)0，要增加虛結(jié)點(diǎn)。第一次構(gòu)造用(m1)(k-1)+1 個(gè)結(jié)點(diǎn)， 之后都用 k 個(gè)結(jié)點(diǎn)構(gòu)造k 叉樹。需要說明，國(guó)內(nèi)多數(shù)教科書對(duì)“帶權(quán)路徑長(zhǎng)度”的定義是所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，而“外部”結(jié)點(diǎn)指不存在的結(jié)點(diǎn)。本題構(gòu)造的三叉樹如右圖。若 X 是后序線索二叉樹中的葉結(jié)點(diǎn)，且X 存在左兄弟結(jié)點(diǎn)Y，則 X 的右線索指向的是( )?！?013 年全國(guó)試題

9、 5(2 分)】A.X 的父結(jié)點(diǎn)B.以Y 為根的子樹的最左下結(jié)點(diǎn)C.X 的左兄弟結(jié)點(diǎn) YD.以Y 為根的子樹的最右下結(jié)點(diǎn)4(2 分)】若對(duì)如下的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)x 的左、右線索指向的結(jié)點(diǎn)分別是( )?！?014 年全國(guó)試題A.c,c B.c，a C.d,c D.b，a將森林F 轉(zhuǎn)換為對(duì)應(yīng)的二又樹T，F(xiàn) 中葉結(jié)點(diǎn)的個(gè)數(shù)等于( )。2014 年全國(guó)試題 5(2 分)】A.T 中葉結(jié)點(diǎn)的個(gè)數(shù)B.T 中度為 1 的結(jié)點(diǎn)個(gè)數(shù)C.T 中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)D.T 中右孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)15.5 個(gè)字符有如下 4 種編碼方案，不是前綴編碼的是( )?！?014 年全國(guó)試題 6(2 分)】

10、A.01，0000，0001，001，1 B.011，000，001，010，1 C.000，001，010，011，100 D.0，100，110，11 10，1100要注意，前綴碼是指一個(gè)編碼不是另一個(gè)編碼的前綴。二、 填空題(總題數(shù)：6，分?jǐn)?shù)：12.00)含有 3 個(gè)結(jié)點(diǎn)的不同的二叉樹有 棵?！倦娮涌萍即髮W(xué) 2005 二、7(1 分)】正確答案：(正確答案：5)一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)在一維數(shù)組 t 中，f=e，a，f,0，d，0，g，0，0，c， j，0，0，1，h，i，0，0，0，0，b(其中 0 代表空樹)，c 在樹中的層次為 。【南京理工大學(xué)2004 三、2(1

11、 分)】正確答案：(正確答案：4)一棵有n 個(gè)結(jié)點(diǎn)的二叉樹，葉子結(jié)點(diǎn)的數(shù)量為加，度為 2 的結(jié)點(diǎn)數(shù)量為，n2，則 n0 與n2 的關(guān)系是(1) ； 如果用二叉鏈表存儲(chǔ)該二叉樹，則空指針數(shù)量為(2)?！倦娮涌萍即髮W(xué) 2013 一、1(2 分)】正確答案：(正確答案：(1)n0=n2+1 (2)n+1)樹在計(jì)算機(jī)內(nèi)的表示方式有(1)，(2)，(3)?！竟枮I工業(yè)大學(xué) 2000 二、4(3 分)】正確答案：(正確答案：(1)雙親鏈表表示法 (2)孩子鏈表表示法 (3)孩子兄弟表示法)在二叉樹中，指針p 所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 ?！竞戏使I(yè)大學(xué) 1999 三、7(2 分)】正確答案：(正確答案：p

12、 一lchild=null&p 一rchlid=ull)中綴式a+b *3+4 *(c-d)對(duì)應(yīng)的前綴式為(1)，若a=1，b=2，c=3，d=4，則后綴式dbcc *a 一b * +的運(yùn)算結(jié)果為(2)?！疚髂辖煌ù髮W(xué) 2000 一、6】正確答案：(正確答案：(1)+a*b3*4 一 cd (2)1 8)三、 判斷題(總題數(shù)：10，分?jǐn)?shù)：20.00)二叉樹是一般樹的特殊情形。( )【北京郵電大學(xué) 2000 一、9(1 分)2002 一、6(1 分)】正確錯(cuò)誤樹與二叉樹是兩種不同的樹形結(jié)構(gòu)。( )【東南大學(xué) 2001 一、1-7(1 分)】正確錯(cuò)誤二叉樹只能采用二叉鏈表來存儲(chǔ)。( )【中南大學(xué) 2005 三、2(2 分)】正確錯(cuò)誤二叉樹中不存在度大于 2 的結(jié)點(diǎn)，當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹時(shí)，無所謂左右子樹之分。( )【中國(guó)海洋大學(xué) 2007 二、9(1 分)】正確錯(cuò)誤二叉樹是度為 2 的有序樹。( )【中科院軟件所 1997 一、9(1 分)】正確錯(cuò)誤如果約定樹中結(jié)點(diǎn)的度數(shù)不超過 2，則它實(shí)際上就是一棵二叉樹。( )【蘭州大學(xué) 2000 一、10(1 分)】正確錯(cuò)誤具有 10 個(gè)葉結(jié)點(diǎn)的二叉樹中，有 9 個(gè)度為 2 的結(jié)點(diǎn)。