【正文】 、4（4分）】20．一個有2001個結點的完全二叉樹的高度為______?！灸暇├砉ご髮W 1997 三、2（1分）】21．設F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有__(1)_個結點，右子樹中有_(2)__個結點?！灸暇├砉ご髮W 2000 二、9（3分）】22．一個深度為k的，具有最少結點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結點編號，則編號最小的葉子的序號是__(1)_；編號是i的結點所在的層次號是_(2)__（根所在的層次號規(guī)定為1層）?！灸暇├砉ご髮W 2001 二、2（2分）】23．如某二叉樹有20個葉子結點，有30個結點僅有一個孩子，則該二叉樹的總結點數(shù)為______?！灸暇├砉ご髮W 2001 二、3（2分）】24．如果結點A有 3個兄弟，而且B是A的雙親，則B的度是______?！疚靼搽娮涌萍即髮W1999軟件 一、4（2分）】25．高度為h的23樹中葉子結點的數(shù)目至多為______?！疚靼搽娮涌萍即髮W1999軟件 一、6（2分）】26．完全二叉樹中，結點個數(shù)為n，則編號最大的分支結點的編號為______?！颈本┹p工業(yè)學院 2000 一、3 (2分)】27．設一棵完全二叉樹葉子結點數(shù)為k,最后一層結點數(shù)2，則該二叉樹的高度為______。 【北京科技大學 1998 一、3】28．對于一個具有n個結點的二元樹，當它為一棵_(1)_二元樹時具有最小高度，當它為一棵_(2)_時，具有最大高度。【哈爾濱工業(yè)大學 2001 一、3 (2分)】29．具有N個結點的二叉樹，采用二叉鏈表存儲，共有______個空鏈域?！局貞c大學 2000 一、8】30．8層完全二叉樹至少有______個結點，擁有100個結點的完全二叉樹的最大層數(shù)為______?！疚髂辖煌ù髮W 2000 一、1】31．含4個度為2的結點和5個葉子結點的二叉樹，可有______個度為1的結點?！颈本┕I(yè)大學 2001 一、6 (2分)】32．一棵樹T中，包括一個度為1的結點，兩個度為2的結點，三個度為3的結點，四個度為4的結點和若干葉子結點，則T的葉結點數(shù)為______?！旧綎|大學 2001 三、2 (2分)】33． n（n大于1）個結點的各棵樹中，其深度最小的那棵樹的深度是_(1)__。它共有_(2)__個葉子結點和_(3)__個非葉子結點，其中深度最大的那棵樹的深度是_(4)__，它共有_(5)__個葉子結點和_(6)__個非葉子結點?！旧綎|大學 2001 三、7 (2分)】34． 每一棵樹都能唯一的轉(zhuǎn)換為它所對應的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，對稱序列是FEBGCHD，則它的后序序列是_(1)__。設上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是_(2)__?！旧綎|工業(yè)大學 1997 二、 (6分)】35．先根次序周游樹林正好等同于按_(1)__周游對應的二叉樹，后根次序周游樹林正好等同于按__(2)_周游對應的二叉樹?！旧綎|工業(yè)大學 1999 二、1 （4分）】36．二叉樹結點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結點的前序序列為_(1)__,則該二叉樹對應的樹林包括_(2)__棵樹?！颈本┐髮W 1997 一、2 （4分）】37．二叉樹的先序序列和中序序列相同的條件是______?！竞戏使I(yè)大學 2000 三、7（2分）】38．已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1)__，左子樹中有_(2)__， 右子樹中有_(3)__?！灸暇├砉ご髮W 1996 二、1（6分）】39．設二叉樹中每個結點均用一個字母表示，若一個結點的左子樹或右子樹為空，用 ．表示，現(xiàn)前序遍歷二叉樹，.....F．．，則中序遍歷二叉樹時，訪問的結點序列為_(1)__。后序遍歷二叉樹時，訪問的結點序列為_(2)__。【南京理工大學 1999 二、3（4分）】40．已知二叉樹前序為ABDEGCF，中序為DBGEACF，則后序一定是____?！厩鄭u大學2000 六、3(2分）】41．現(xiàn)有按中序遍歷二叉樹的結果為abc，問有_(1)__種不同的二叉樹可以得到這一遍歷結果，這些二叉樹分別是_(2)__?！局袊V業(yè)大學 2000 一、5（3分）】42．一個無序序列可以通過構造一棵______樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程?！疚靼搽娮涌萍即髮W1999軟件 一、4（2分）】43．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為______?！局貞c大學 2000 一、9】44．若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的______序列中的最后一個結點?！疚錆h大學 2000 一、2】45．先根次序周游樹林正好等同于按______周游對應的二叉樹；后根次序周游樹林正好等同于______周游對應的二叉樹?！旧綎|大學 1999 二、１ (４分)】46. 在一棵存儲結構為三叉鏈表的二叉樹中，若有一個結點是它的雙親的左子女，且它的雙親有右子女，則這個結點在后序遍歷中的后繼結點是______?！局袊嗣翊髮W 2001 一、4 （2分）】47．一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數(shù)為：______?！緩B門大學 2002 六、1 （4分）】48．具有n個結點的滿二叉樹，其葉結點的個數(shù)是______。【北京大學 1994】49．設一棵后序線索樹的高是50，結點x是樹中的一個結點，其雙親是結點y,y的右子樹高度是31，x是y的左孩子。則確定x的后繼最多需經(jīng)過______中間結點（不含后繼及x本身）【南京理工大學 2000 二、8（）】50．線索二元樹的左線索指向其______，右線索指向其______?！竟枮I工業(yè)大學 2000 二、3 (2分)】51．設y指向二叉線索樹的一葉子，x指向一待插入結點，現(xiàn)x作為y的左孩子插入，樹中標志域為ltag和rtag，并規(guī)定標志為1是線索，則下面的一段算法將x插入并修改相應的線索，試補充完整：(lchild,rchild分別代表左，右孩子)x^.ltag:= (1)___。 x^.lchild:= (2)___。 y^.ltag:= (3)___。 y^.lchild:= (4)___。 x^.rtag:= (5)___。 x^.rchild:= (6)___。IF (x^.lchildNIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___?！灸暇├砉ご髮W 1997 三、7 （9分）】52．哈夫曼樹是______?！颈本├砉ご髮W 2001 七、4 （2）】【 長沙鐵道學院 1998 二、3 (2分)】53．若以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是______。【西安電子科技大學2001軟件 一、3 （2分）】【廈門大學 2002 六、2（4分）】54．有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是_(1)__，帶權路徑長度WPL為_(2)__?！灸暇├砉ご髮W 1999 三、6（4分）】55．有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構造一棵哈夫曼樹，則其加權路徑長度WPL為_(1)__，字符c的編碼是_(2)__?！局袊V業(yè)大學2000 一、7（3分）】56．設n0為哈夫曼樹的葉子結點數(shù)目，則該哈夫曼樹共有______個結點。