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