【正文】 【西安電子科技大學(xué)2001軟件 一、3 （2分）】【廈門大學(xué) 2002 六、2（4分）】54．有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是_(1)__，帶權(quán)路徑長度WPL為_(2)__。 x^.lchild:= (2)___?！局貞c大學(xué) 2000 一、9】44．若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的______序列中的最后一個結(jié)點?！颈本┐髮W(xué) 1997 一、2 （4分）】37．二叉樹的先序序列和中序序列相同的條件是______?！颈本┕I(yè)大學(xué) 2001 一、6 (2分)】32．一棵樹T中，包括一個度為1的結(jié)點，兩個度為2的結(jié)點，三個度為3的結(jié)點，四個度為4的結(jié)點和若干葉子結(jié)點，則T的葉結(jié)點數(shù)為______?！灸暇├砉ご髮W(xué) 2001 二、3（2分）】24．如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是______?！颈本┐髮W(xué) 1997 一、1 （4分）】16．設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A[1:N]中，其下標(biāo)值最大的分支結(jié)點為______?！狙嗌酱髮W(xué) 1998 一、4 （1分）】7．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點?！灸暇┖娇蘸教齑髮W(xué) 1995 五、6 （1分）】49．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。（3）二叉樹是結(jié)點的集合，滿足如下條件：（a）它或者是空集；（b）或者是由一個根和兩個互不相交的、稱為左子樹和右子樹的二叉樹組成?！緰|南大學(xué) 2001 一、17 （1分）】37. 非空的二叉樹一定滿足：某結(jié)點若有左孩子，則其中序前驅(qū)一定沒有右孩子【合肥工業(yè)大學(xué) 2001 二、5 （1分）】38．在任意一棵非空二叉排序樹，刪除某結(jié)點后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹相同。【青島大學(xué) 2002 一、5 （1分）】27. 用鏈表(llinkrlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n1個空指針?！?長沙鐵道學(xué)院 1998 一、2 (1分)】19．任何二叉樹的后序線索樹進(jìn)行后序遍歷時都必須用棧。【上海海運學(xué)院 1995 一、4 （1分）】10. 二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該樹的根結(jié)點是那一個，則可以確定這棵二叉樹。【山東工業(yè)大學(xué) 1995 三、 (5分)】二、判斷題1. 二叉樹是度為2的有序樹。E．將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點沒有左子樹。 A．二叉排序樹 B．哈夫曼樹 C．AVL樹 D．堆【中國科技大學(xué)1998二、8（2分）】【中科院計算所1998二、8(2分）】60．在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹，該說法（ ）?！疚錆h大學(xué)2000二、4】A．空或只有一個結(jié)點 B．任一結(jié)點無左子樹 C．高度等于其結(jié)點數(shù) D．任一結(jié)點無右子樹45．在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（ ）。A．CBEFDA B． FEDCBA C． CBEDFA D．不定 【浙江大學(xué) 1999 四、2 ( 4分)】34．已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。 D．logn122．深度為h的滿m叉樹的第k層有（ ）個結(jié)點。1 E．233?！颈狈浇煌ù髮W(xué) 2001 一、16 （2分）】A．M1 B．M1+M2 C．M3 D．M2+M311．具有10個葉結(jié)點的二叉樹中有（ ）個度為2的結(jié)點，【北京航空航天大學(xué)2000 一、5（2分)】A．8 B．9 C．10 D．ll12．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）【西安交通大學(xué) 1996 三、2 (3分)】A． 250 B． 500 C．254 D．505 E．以上答案都不對 13. 設(shè)給定權(quán)值總數(shù)有n 個，其哈夫曼樹的結(jié)點總數(shù)為( ) 【福州大學(xué) 1998 一、5 (2分)】A．不確定 B．2n C．2n+1 D．2n114. 有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（ ）。 A．①②③ B．②③④ C．②④ D．①④6. 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ ）A．mn B．mn1 C．n+1 D．條件不足，無法確定 【南京理工大學(xué)2000 一、17（）】7. 樹是結(jié)點的有限集合，它（ (1）)根結(jié)點，記為T。其余結(jié)點分成為m（m0）個(（2）)的集合T1，T2， …，Ｔm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）?！厩鄭u大學(xué) 2002 二、1 （2分）】A．不確定 B．2n C．2n+1 D．2n115．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（ ）。(n+1)/(m+1)249。(1=k=h)【北京航空航天大學(xué)2000一、4（2分）】A．mk1 B．mk1 C．mh1 D．mh123．在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（ ）【北京工商大學(xué) 2001 一、3 (3分)】A．2k1 B．2k C．2k1 D．235。 A．a(chǎn)cbed B．decab C．deabc D．cedba 【山東大學(xué) 2001 二、7 ( 1分)】35. 某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E 則前序序列是：A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不對 【南京理工大學(xué) 2000 一、14 （）】36. 上題的二叉樹對應(yīng)的森林包括多少棵樹（ ）【南京理工大學(xué) 2000 一、15 （）】A．l B．2 C．3 D．概念上是錯誤的 37．二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG ?！颈狈浇煌ù髮W(xué) 2001 一、22 （2分）】 A．左子結(jié)點 B．右子結(jié)點　 C．左子結(jié)點和右子結(jié)點 D．左子結(jié)點，右子結(jié)點和兄弟結(jié)點46．在下列情況中，可稱為二叉樹的是（ ） A．每個結(jié)點至多有兩棵子樹的樹 B. 哈夫曼樹 C．每個結(jié)點至多有兩棵子樹的有序樹 D. 每個結(jié)點只有一棵右子樹 E．以上答案都不對 【西安交通大學(xué) 1996 三、4 (3分)】47. 一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：( )A．不確定 B. 0 C. 1 D. 2 【合肥工業(yè)大學(xué) 1999 一、5 （2分）】48. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：( )。 A．正確 B．錯誤