數據結構習題第六章樹和二叉樹-資料下載頁

　　

【正文】 、4（4分）】20．一個有2001個結點的完全二叉樹的高度為______。【南京理工大學 1997 三、2（1分）】21．設F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結點數分別為n1,n2和n3則二叉樹B的左子樹中有__(1)_個結點，右子樹中有_(2)__個結點。【南京理工大學 2000 二、9（3分）】22．一個深度為k的，具有最少結點數的完全二叉樹按層次，（同層次從左到右）用自然數依此對結點編號，則編號最小的葉子的序號是__(1)_；編號是i的結點所在的層次號是_(2)__（根所在的層次號規定為1層）。【南京理工大學 2001 二、2（2分）】23．如某二叉樹有20個葉子結點，有30個結點僅有一個孩子，則該二叉樹的總結點數為______。【南京理工大學 2001 二、3（2分）】24．如果結點A有 3個兄弟，而且B是A的雙親，則B的度是______。【西安電子科技大學1999軟件 一、4（2分）】25．高度為h的23樹中葉子結點的數目至多為______。【西安電子科技大學1999軟件 一、6（2分）】26．完全二叉樹中，結點個數為n，則編號最大的分支結點的編號為______。【北京輕工業學院 2000 一、3 (2分)】27．設一棵完全二叉樹葉子結點數為k,最后一層結點數2，則該二叉樹的高度為______。 【北京科技大學 1998 一、3】28．對于一個具有n個結點的二元樹，當它為一棵_(1)_二元樹時具有最小高度，當它為一棵_(2)_時，具有最大高度。【哈爾濱工業大學 2001 一、3 (2分)】29．具有N個結點的二叉樹，采用二叉鏈表存儲，共有______個空鏈域。【重慶大學 2000 一、8】30．8層完全二叉樹至少有______個結點，擁有100個結點的完全二叉樹的最大層數為______。【西南交通大學 2000 一、1】31．含4個度為2的結點和5個葉子結點的二叉樹，可有______個度為1的結點。【北京工業大學 2001 一、6 (2分)】32．一棵樹T中，包括一個度為1的結點，兩個度為2的結點，三個度為3的結點，四個度為4的結點和若干葉子結點，則T的葉結點數為______。【山東大學 2001 三、2 (2分)】33． n（n大于1）個結點的各棵樹中，其深度最小的那棵樹的深度是_(1)__。它共有_(2)__個葉子結點和_(3)__個非葉子結點，其中深度最大的那棵樹的深度是_(4)__，它共有_(5)__個葉子結點和_(6)__個非葉子結點。【山東大學 2001 三、7 (2分)】34． 每一棵樹都能唯一的轉換為它所對應的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，對稱序列是FEBGCHD，則它的后序序列是_(1)__。設上述二叉樹是由某棵樹轉換而成，則該樹的先根次序序列是_(2)__。【山東工業大學 1997 二、 (6分)】35．先根次序周游樹林正好等同于按_(1)__周游對應的二叉樹，后根次序周游樹林正好等同于按__(2)_周游對應的二叉樹。【山東工業大學 1999 二、1 （4分）】36．二叉樹結點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結點的前序序列為_(1)__,則該二叉樹對應的樹林包括_(2)__棵樹。【北京大學 1997 一、2 （4分）】37．二叉樹的先序序列和中序序列相同的條件是______。【合肥工業大學 2000 三、7（2分）】38．已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1)__，左子樹中有_(2)__， 右子樹中有_(3)__。【南京理工大學 1996 二、1（6分）】39．設二叉樹中每個結點均用一個字母表示，若一個結點的左子樹或右子樹為空，用 ．表示，現前序遍歷二叉樹，.....F．．，則中序遍歷二叉樹時，訪問的結點序列為_(1)__。后序遍歷二叉樹時，訪問的結點序列為_(2)__。【南京理工大學 1999 二、3（4分）】40．已知二叉樹前序為ABDEGCF，中序為DBGEACF，則后序一定是____。【青島大學2000 六、3(2分）】41．現有按中序遍歷二叉樹的結果為abc，問有_(1)__種不同的二叉樹可以得到這一遍歷結果，這些二叉樹分別是_(2)__。【中國礦業大學 2000 一、5（3分）】42．一個無序序列可以通過構造一棵______樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。【西安電子科技大學1999軟件 一、4（2分）】43．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉換為______。【重慶大學 2000 一、9】44．若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的______序列中的最后一個結點。【武漢大學 2000 一、2】45．先根次序周游樹林正好等同于按______周游對應的二叉樹；后根次序周游樹林正好等同于______周游對應的二叉樹。【山東大學 1999 二、１ (４分)】46. 在一棵存儲結構為三叉鏈表的二叉樹中，若有一個結點是它的雙親的左子女，且它的雙親有右子女，則這個結點在后序遍歷中的后繼結點是______。【中國人民大學 2001 一、4 （2分）】47．一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數為：______。【廈門大學 2002 六、1 （4分）】48．具有n個結點的滿二叉樹，其葉結點的個數是______。【北京大學 1994】49．設一棵后序線索樹的高是50，結點x是樹中的一個結點，其雙親是結點y,y的右子樹高度是31，x是y的左孩子。則確定x的后繼最多需經過______中間結點（不含后繼及x本身）【南京理工大學 2000 二、8（）】50．線索二元樹的左線索指向其______，右線索指向其______。【哈爾濱工業大學 2000 二、3 (2分)】51．設y指向二叉線索樹的一葉子，x指向一待插入結點，現x作為y的左孩子插入，樹中標志域為ltag和rtag，并規定標志為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)___。【南京理工大學 1997 三、7 （9分）】52．哈夫曼樹是______。【北京理工大學 2001 七、4 （2）】【 長沙鐵道學院 1998 二、3 (2分)】53．若以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是______。【西安電子科技大學2001軟件 一、3 （2分）】【廈門大學 2002 六、2（4分）】54．有數據WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是_(1)__，帶權路徑長度WPL為_(2)__。【南京理工大學 1999 三、6（4分）】55．有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現頻率依次為2,3,4,7,8,9，試構造一棵哈夫曼樹，則其加權路徑長度WPL為_(1)__，字符c的編碼是_(2)__。【中國礦業大學2000 一、7（3分）】56．設n0為哈夫曼樹的葉子結點數目，則該哈夫曼樹共有______個結點。