工大數(shù)據(jù)結(jié)構(gòu)作業(yè)

1、 工大數(shù)據(jù)結(jié)構(gòu)第三章作業(yè) 作者： 日期: 數(shù)據(jù)結(jié)構(gòu)與算法上機作業(yè) 第三章 樹 、選擇題 、在一棵樹中，如果結(jié)點 A 有 3 個兄弟 ,是 A 的雙親 ,則的度為D ?A 1B 2? . 3? D 2、深度為 h 的完全二叉樹至少有個結(jié)點 ,至多有 個結(jié)點 ?A. h?. 2h-?C. 2+1D. 21 2（ -1） -1 +1 2（h- ） 前（n 1）層滿，第 h 層只有一結(jié)點 3、具有 n 個結(jié)點的滿二叉樹有C 個葉結(jié)點。 A. /2 （-1）/2? . （n+1） 2? D. n/2+1 因為 二叉樹中，有這樣一個性質(zhì)，如果其終端結(jié)點數(shù)（也就是葉子節(jié)點）的個 數(shù)為 n1,度為 2 的結(jié)點

2、數(shù)為 n2，則1n2+1；?假設(shè)葉子節(jié)點有 x 個,則度為 2 的個數(shù)為 x1： 所以： x- ； 所以 x = （n ）/2 （滿二叉樹） 所以 葉子節(jié)點個數(shù)為 :（n+1 ）/2 非終端結(jié)點為 ： （n1）/2- 、一棵具有 2個葉結(jié)點的完全二叉樹最多有 B 個結(jié)點。 A. 48?B. ?C 50 ?D. 5 、已知二叉樹的先根遍歷序列是 BCDE ,中根遍歷序列是 CBA DF,則后根遍歷序列是 A。 ?A. CBEFD ?B. FE B?. EDFD. 不定 6、具有個葉結(jié)點的二叉樹中有 個度為 2 的結(jié)點。 . 8?B 9. 0 ?D. 11 7、一棵非空二叉樹的先序遍歷序列與后序遍

3、歷序列正好相反，則該二叉樹一定滿足 。 A 所有非葉結(jié)點均無左孩子 ? B. 所有非葉結(jié)點均無右孩子 C. 只有一個葉子結(jié)點 ? D A 和 B 同時成立 8、在線索二叉樹中 ,所指結(jié)點沒有左子樹的充要條件是 ?A. t-leftUL? ?B. t-lt g=TRU ? C. t lta =TRU 且 -left=NULL ?D. 以上都不對 、個結(jié)點的 線索 二叉樹上含有的線索數(shù)為 C 。 A 2B. -1 ?C. n+1D. n n-表示結(jié)點的左右子樹，其余n-指針為空 線索取代原來的空鏈 10、二叉樹按照某種順序線索化后，任一結(jié)點都有指向其前驅(qū)和后繼的線索，這種說法 B。 A 正確? B

4、 錯誤 C. 不確定 ? D. 都有可能 1、具有 n（n1）個結(jié)點的完全二叉樹中 ,結(jié)點 （2in ）的左孩子結(jié)點是D 。 ?A. 2i . i+1 2i-1 D. 不存在 1、具有 4 個結(jié)點的完全二叉樹的深度為C 。 A 5?B? ?C ?D?. 8 、將一顆有個結(jié)點的完全二叉樹從上到下、從左到右一次對結(jié)點進行編號,根結(jié) 點的編號為 1 ，則編號為 45 的結(jié)點的右孩子的編號為 C 。 ?A. 46 ?B. 47C. 0 1 2i 舉個簡單的例子就可以看出來，比如 7 個節(jié)點時（也就是三層時 ） ，編 號為 1的左子樹編號是 2，編號 2的左子樹是 4，編號 3 的左子樹編號為 。以此就

5、可以看出來。 左結(jié)點是 2i, 右結(jié)點才是 2i+1 14、在結(jié)點數(shù)為 n 的堆中插入一個結(jié)點時 ,復雜度為C A. O（n）? . （n） ?C. O（log2n）D. O（log n2） 15、兩個二叉樹是等價的，則它們滿足 A 它們都為空 ? ?B 它們的左右子樹都具有相同的結(jié)構(gòu) ?. 它們對應的結(jié)點包含相同的信息?D. A、B 和 C 6、包含 n 個元素的堆的高度為C。（符號 a 表示取不小最小整數(shù) ） A ?B. lognC. log2（+）? . n+ 1、以下說法錯誤的是 。 ?A. 存在這樣的二叉樹 ,對其采用任何次序的遍歷其結(jié)點訪問序列均相同 ?B 二叉樹是樹的特殊情形 C

6、. 由樹轉(zhuǎn)換成二叉樹 ,其根結(jié)點的右子樹總是空的 D. 在二叉樹中只有一棵子樹的情形下，也要指出是左子樹還是右子樹 18、設(shè) F是一個森林，是由 F變換得到的二叉樹。若 F中有 n 個非終端結(jié)點 ,則 B 中沒有 右孩子的結(jié)點有 個。 A. n-1 ?B. ?C. n+D. n+2 19、將一棵樹 T 轉(zhuǎn)換為二叉樹 ,則 T 的后根序列是的B 。 A. 先根序列 ? . 中根序列C. 后根序列 ?D. 層次序列 2、將一棵樹轉(zhuǎn)換為二叉樹后，這顆二叉樹的形態(tài)是A 。 ?. 唯一的 ,根結(jié)點沒有左孩子. 唯一的 ,根結(jié)點沒有右孩子 ?C 有多種 ,根結(jié)點都沒有左孩子D 有多種 ,根結(jié)點都沒有右孩子

7、 樹轉(zhuǎn)換成二叉樹，根節(jié)點是沒有右孩子的，這由轉(zhuǎn)換規(guī)則應該不難理解,且轉(zhuǎn)換 規(guī)則是唯一的 ,所以轉(zhuǎn)換成的二叉樹是唯一的 21、設(shè)樹的度為 4，其中度為 1, 2, 3, 4 的結(jié)點個數(shù)分別為 , 2, 1, ，則 T 中的葉結(jié)點的 個數(shù)為 D 。 A. 5 ?B. 6C. 7D. 8 22、設(shè)森林 F 中有三棵樹，第一、第二、第三棵樹的結(jié)點個數(shù)分別為M1, M2 ， M3。與森 林 F 對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)為 D 。 A. M ?. +2? C. M2 ?D. M23 2、若以二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二 叉樹是 C 。 A. 二叉排序

8、樹 ?B 哈夫曼樹 . 堆? 線索二叉樹 2、用 5 個權(quán)值 3, ， 4, 5， 1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 A. ?B. 3 C. 34? D 1 二、填空題 1、一棵二叉樹有 6個結(jié)點 ,結(jié)點的度是 0 和。問這棵二叉樹中度為 2 的結(jié)點有 3 個。 2、含 , B, C 三個結(jié)點的不同形態(tài)的二叉樹有5 棵。 3、含有個度為的結(jié)點和 5 個葉子結(jié)點的完全二叉樹， 有 1 或 0 個度為 的結(jié)點。 4、具有 0 個結(jié)點的完全二 叉樹的葉子結(jié)點數(shù)為 0。 5、在用左右鏈表示的具有 n 個結(jié)點的二叉樹中 , 共有 2n 個指針域 ,其中 n 1 個指針域用于指向其左右孩子 ,剩下的n+

9、個指針域是空的。 、如果一顆完全二叉樹的任意一個非終結(jié)結(jié)點的元素都 不小于 其左兒子結(jié)點 和右兒子結(jié)點 （如果有的話 ）的元素，則稱此完全二叉樹為最大堆。 、堆是一種特殊形式的 完全 二叉樹，對于最大堆而言，其根結(jié)點的元 素的值應該是所有結(jié)點元素中 最大的。 、二叉樹的復制是指按照一棵已知的二叉樹復制一個副本,使兩者 等價 。復制二 叉樹最長用的方法是 后根遍歷遞歸算法 。 9、在定義堆時，通常采用結(jié)構(gòu)體 方式定義相應的二叉樹，這樣可以很容 易實現(xiàn)其相關(guān)操作。 、在構(gòu)建選擇樹時 , 根據(jù)孩子結(jié)點的獲勝者確定他們雙親結(jié)點所得到的選擇樹稱為 勝者樹 。根據(jù)孩子結(jié)點的失敗者確定他們雙親結(jié)點所得到的選

10、擇樹稱為 敗者樹 。 11、樹的表示方法包括數(shù)組 、 鄰接表 和 左右 鏈。 12、表達式（+b*（ d）f 的波蘭式（前綴式）是-+a*b- /ef，逆波蘭式（后綴式）是 b d-*+ f 13、設(shè) F 是由 T1 、T2、T三棵樹組成的森林， 與 F對應的二叉樹為 B。已知 T, T2， 3 的結(jié)點數(shù)分別為 n1, n2 和 n3, 則二叉樹 B 的左子樹中有n1個結(jié)點， 二叉樹的右子樹中有n2 n3個結(jié)點。 14、設(shè)二叉樹的中根序列為 ABCDE ，后根序列為 B C FGE。則該二叉樹的先根序 列為 AC DGF。該二叉樹對應的森林中包含 2 棵 樹。 15、先根次序遍歷森林等同于按先

11、根 遍歷對應的二叉樹 ,后根次序遍歷 森林等同與按 中根 遍歷對應的二叉樹。 16、一棵哈夫曼樹有 19 個結(jié)點 ,則其葉子結(jié)點的個數(shù)為10 。 1、設(shè)有數(shù)據(jù) WG, 19, 2， , , 3, 2, 0葉節(jié)點權(quán)重集合，則所構(gòu)建哈 夫曼樹的高是 ，帶權(quán)路徑長度 PL 為 169 。 8、設(shè)有一份電文中共使用 6 個字符 , b, c, d, e, f,其中出現(xiàn)頻率依次為 2,3,4,7，8,19, 則字符 c 的哈夫曼編碼是001,電文編碼的總長度為80 。 20、在有個結(jié)點的哈夫曼樹中 ,葉子結(jié)點總數(shù)為（n+1）/2,非葉結(jié)點的總數(shù)為（n 1）/2。 、試分別畫出具有個結(jié)點的二叉樹的所有不同

12、形態(tài)。 四、已知一棵二叉樹的中根序列和后根序列分別是BDCEA G 和 DECBH A，請畫出 此二叉樹。 五、已知非空二叉樹 T,寫一個算法 ,求度為的結(jié)點的個數(shù)。 要求 : ?1、定義二叉樹的抽象數(shù)據(jù)類型和型TREE，并定義基本操作。 2、編寫函數(shù) cou t2（BTRE T），返回度為 2 的節(jié)點的個數(shù)。 3、在主函數(shù)中，構(gòu)建一個二叉樹，并驗證所編寫的算法。 六、用遞歸方法寫一個算法，求二叉樹的葉子結(jié)點數(shù)int leaf u（ BTREE T）。 要求： 1、 定義二叉樹的抽象數(shù)據(jù)類型和型 BTR ，并定義基本操作。 2、 編寫函數(shù) l fnum（BTR E T）,返回樹 T 的葉子節(jié)點

13、的個數(shù)。 在主函數(shù)中 ,構(gòu)建一個二叉樹，并驗證所編寫的算法。 七、畫出下圖所表示的二叉樹的中序線索二叉樹和先序線索二叉樹。 八、已知二叉樹的先根序列是A FB DH KJ,中根序列是 E A CHKIJD, 畫出此二 叉樹，并畫出后序線索二叉樹。 九、在中序線索二叉樹中插入一個結(jié)點 Q 作為樹中某個結(jié)點 P 的左孩子，試給出相應的算 法。 要求 : 1、 定義中序線索二叉樹的型 THRE 以及基本操作。 2、 定義函數(shù) vo nsert（ HT EE P, HTRE ）； 實現(xiàn)題目要求的操作。 在主函數(shù)中， 利用操作 RInrt 和 LInsrt 構(gòu)造一個線索二叉樹 ,并中序輸出二叉樹的結(jié)點

14、的元素 ,驗證結(jié)果。 ncl d # n l de # clud # nclud #i lude si g namespace td; y edef in el mentt p； truct ode /節(jié)點的型 e lchil ; noe* rchi ; bol lt g； ? ol rtg; ?element ype lemen ; ； typede node* ea； /指向樹根 r t ef node* t ee； /指向線索樹的根節(jié)點 oid ak N ll（he d h-ltag=false; ?h- child ； ?h-rt g ru ; head pointToree（head

15、 ?h- tag= rue； ?h rta rue; re ur h; /中根遍歷的下一個節(jié)點 od in ext（ de p） ?n de* q=p- chil ; ? （p t g=true） /如果有右子樹，找出右子樹的最左節(jié)點 ?h le（q-ltag=true） ?q=q- chil ; ? t r q; /中根遍歷的上一個節(jié)點 node* inPr （node* p ） ode *q= p-lchil ; if（ ltag true） /如果 P 的左子樹存在，則其前驅(qū)結(jié)點為左子樹的最右結(jié)點 ? ile（q g=true） ?= - chil ; return ;/左子樹的最右結(jié)點

16、 中序遍歷 vid t InOrder（head h） ?nod* t mp； ?temp=h; ?do ?temp=inNext（t mp） ; f（te p！ h） ? ?cout lement rchild=s-rchild; ?r-rtag s- rtag; r- i d=s； ? lta =false;/新插入的節(jié)點木有左子樹，所以lchi 指向的是父節(jié)點 ? ch ld=r; ?s- a =true;/ 原節(jié)點的右孩子為新插入的節(jié)點 f（r-ra =tr e） ?/這里是神馬意思呢 |?？ |,就是如果被插節(jié)點有右子樹， /找出被插節(jié)點 s 的的 n xt 位置，即右子樹中的最左節(jié)

17、點 ,令其 lchild 指向新添加的節(jié) 點r ?/因為插入前該最左節(jié)點的 l i d指向的是原來節(jié)點 s ? =i Ne t(r); ? -lch ld= ； /插入左孩子 voi lI sert(node s,node ) ?n e* w; l h l =s-lc ild; ?l ta s- l a； -r il =; rtagfa se； ?s-lc ild=l; ?s-lta =true ； ?if( -ltg=t ue)/與插入右孩子方法相似，只需把左右方向?qū)φ{(diào)即可 ?w=inP e(l); ? w- child=l; ? i t mai() ? ead =n nd； nde roo

18、t new node; nd* c ew oe; node* rc=new no e; ?node c e n de; rot- e ent 1; ?lc-element 2； ? c-ele ent=3； c-el m nt ; ? ?h-rc ild=ro ； ?h lchil h； ?h tag=t ; ?h-r ag=true; oot- child h; o t- rch l； ootltag fals ; ?r o-tag=alse; ?/構(gòu)造線索樹 13 In ert( o,lc); ?rInsert(root,rc )； ?thInO der(h); ?c thea. leme

19、nt / . ata） heap.el ments =hea. lements / ; i/=2; epn+； H . lementsi e em ; Elmnttpe DeleteM x（HE P e p） 刪除堆中最大元素 int ar t=1, hi d=2； Elemen t pe le ent,tm ; f（！ He Emp y（ a ） Element=heape em ts1; Tmp= p.e ementshe n; While （chil hap.n） If（ hildheap. ） He p.eleme tspar e = apeem tch d; P ra nt= il

20、; Child*=2; H ap.e en sp raent= ; R tu n el m nt; It nd（H AP,d atyp x） int m=1; While（ （ m H n） else ret r 0; e e m+ ； i （ m=H.n）retu n m; e se return 0; Int m in（） HEP H； E en ty e lement； Int data 1,3， 5,7,9,1,13; H.n=0; or（in i= ;i7;i+） e em nt ke =i+1; Elmnt.ata=data ; I ser （H, lement）; or（int

21、； i H.n;i + ） coutH.elem ntsi at edl; D le eMax （H）； F r（int i=1;i=H. ;i+ ）coutH.el men .dat ; Co t， endl; tx ； CoutF nd（H ， x）endl; 十二、給定葉子結(jié)點的權(quán)值集合 15, 3,1, 2, , 9, 16, 1 ，構(gòu)造相應的哈夫曼樹，并 計算其帶權(quán)路徑長度。 十三、已知 n= 和一組等價關(guān)系： 1 5、 6 8、 7、 8、37、4 2、93 試應用抽象數(shù)據(jù)類型 MSET 設(shè)計一個算法，按輸入的等價關(guān)系進行等價分類。 #incl d dfine n 9/EFET 元

22、素個數(shù) /MST 抽象數(shù)據(jù)型 str c ode int fath r； /指向父節(jié)點的鏈 int co ;/樹結(jié)點個數(shù) ; y ede mfnode MFS n+ ; id Unio （in A, it B, FST ） / 合并 A 和 B if（CA .countCB.coun ） C B ther=A;/B 并入 A A.co t+=CB .c nt; se CA f herB； /A 并入 B B.coun +=CA .co n； int ind（ i , M C） /求包含元素的樹的根 int f; f=x ； while（fa r!=0）/ 未到根 f=C f.father ；

23、re n f; voi Iial（int ， FSET C）集合 A只包含元素 A C . ather0; CA .ou t=1; / 等價分類 void Equ lnce（FST S） int ， j, m, k; f r （ i=1; i ; 0 結(jié)束等價分類 cinj; whil （!（ = m=Find（j ， ）; if （k!=m） Unio （ , ， S） ； ? ini; c n ； vid int_M SET（FSET ） /輸出等價類 int n+1n+1=0, k; for（ i=1; =n; i ） k=F d（ , S） ; rk0 +; rkrk =i; r（ =

24、1; 0） cout ; fo （ t j1; r 0; j+） coutrij ,； o tr r edl; void main（ ） MFST S; Eq ivalence（ ） ; pi _M ET（S）； 十四、畫出下圖所示的森林經(jīng)轉(zhuǎn)換后所對應的二叉樹， 并指出在二叉樹中某結(jié)點為葉子結(jié)點 時，所對應的森林中結(jié)點應滿足的條件。 五、已知森林 F 的先根序列為 :ABCDEF HIJKL, 后根序列為 :CBE DG IKLH ，試畫 出森林 F。 提示:先畫出森林 F 所對應的二叉樹，然后再將轉(zhuǎn)換為森林。 十六、畫出表達式（ B C/D）*E+F*G 所對應的樹結(jié)構(gòu) ,并寫出該表達式的波

25、蘭表示式和 逆波蘭表示式。 具體要求 1 實現(xiàn)二叉樹的基本操作 2 實現(xiàn)將一個四則混合運算轉(zhuǎn)換成二叉樹的函數(shù) 3 4 十七、利用逆波蘭表達式求一個四則混合元算的值。 #inclu e. st .cp 定義二叉樹的型 BT E和位置的型 iion 實現(xiàn)計算四則混合運算的值的函數(shù) :dube computer（BTR t）,其中 ,參數(shù) bt 為四則運算所對應的樹 ,返回值為計算結(jié)果。提示：先求樹的的波蘭表達式,然后利 用棧結(jié)構(gòu)計算表達式的值。 BTRE c nver （ ha *ex ress），其中參數(shù) xpre 為四則混合運算表達式 ,返回值為生成的樹。 在主函數(shù)中進行測試 ,求 +*（5+

26、8）/45 的值 include #icud #defi AX 30 sing a esp ce td; char matc= =; ca opra =+-* （）; cons har ?w ile（o erai!=ch1） i+ ; while（ p a j!= h2） j+ ； ?re rn at hi*7+j ； class T ode public: TNode（ tring st =, nt b=0,T o *l NUL ， TN de *r= ULL ， TNode *p=N LL） ?strcpy（ d,str.c_str（）; ? t=; ?lf=l； ?r gh r； ? p

27、a nt=p ； ?TN d （const ch ch,TNode *l=N LL,TN de NU L,TNode p=NU L） ?id =ch; id1=0 ； b t=0； ?lft=; right= ; p rent=p; ? ont TNo e ? bit=t .bit; eft=tn left； ?r ght t .rih; arent= .parent; hr idA I; ? nt bi； ? o e *p ret,*l ft,* ight; ; nt Rea Expr （ c a tr, h *xpr,it sart，in bit,in i（ trstart =0 ） ex

28、pr; ?r t rn 0； ? els if（s rs a t= * | t s art=/ |st st rt= str t ） ?expr =strsta t; ? ex 1=0; ? leng h 1; ?re urn 2; ? le if（ bit|is igi （ st star）|str tart =） int b= ； t =0; /index fr exp ?while（s r s t= +|s rstart=-） / ead sgn ?i?（ str tar =-） +; ? star +; ? ?lengt + ； ? ? if（ %2） exprk+= ; ?hil （

29、 isd git（st tart ）| s rstart= .） ?e?xprk +=st tart ; ? len th+; ? ? ex k =0; re ur 1； els if （ st star = + | rstart =-） re （|strs art=）| / read digit string a oper or - int =0 ； hile(ststa = |st tar =-) ? f(strsta t=- ) b+; ? tar ; l ngth +； ? f(b%2) xp =-; ?else pr =+; ? expr1=0; ? rtrn 2; ?el re u

30、r -1; /error to a TNoe *Tra s ate(ons tring t) / ra sl te a xpres on srin expres o t e ?char su trMAXSIZE ; Sta k c tk； t ck s ; ? ar *tempstr=new h tr.length() ; int sa =0,bi =; nt t,l ngt； str p (temp tr,sr c_str( ); e tstr.leng h() = ; ? em r tr.len h()+1 0； ? s .pus （ ）; ?t=ReaExpr(tempstr ， ubs

31、tr, tar , t, ngh)； while(c tk.t ( )!= |subst 0 ！=) ?if ( =1)/is a dit string TNode np=n w N e(substr,1)； ?tstk. ush(np) ; bit0; ?else ( t=2) /is a per ?i?f(subtr0=() =1; ? e s i=0； ? hr tc= t top() ； ?if( atch(t h, b tr ) = ) TNod *r t=tstk. op(); t tk.pop(); ? ? Node left= st p(); ? t .po( ) ； ? ?N

32、od *np w Node(tch ， left, i t); ? ?lef arnt np； ? ?righ -pa t np; ? t k.p sh( np) ; ? ? c tk.po (); ?cntn e; ? ? ?ee if(M tch(tc , u s )= left） ? p int（root-l ft） ； ?p int（ o t righ ）; cout； el e co t d; void rin （Noe*）; dou l sove（TNode* ） ; o print x r（ tr g str） TNde * oot Translat （ tr） ?c ut 后綴

33、式 :; ?prin （ oot）; ?co end ; cout 中綴式： ； ?p ts（ro t）; cou = s e（ ot）eft=NULL） couti ;/is a leaf els if（root-pare t= NUL ） ? prnts（r o- left）; ?couti ; ?pri s（r t-righ ）; ?else if（root- ren -le t=root ?out id; ? rnt（ ot-right ） ; ? els if（ro t- are t-right= root） i（Match（oot rent id ,root-id0）=paren

34、- d0= +） ? ri （ro t- eft ）； out id; ? rints （ ro t rgh ）; ? else ?c?outle t）； ?cout id; r s（ oot-ri h ）; cou ）； ? ?else ?coutleft）; ?co tid; ?prit（r ot-right）; ? outleft=N LL） istrng tream in; ? i.str（ oot- id）; dou le va ue; ? invalue ； ?r turn val ； else witch（r o-id 0） cae ? tur lve（root-left）+so

35、lve（ ot ri ）; ca e - re rn s lve（r ot-left）-so ve（ oot-r gh ）; c s re urn olve（root lef ）*sol e（ rot right ） cas /: ?return solv（oo-lft）/ olv（root-right） ； ? ? vo d Chec（ ch r *str） /判斷為帶符號且緊跟括號的情況 ,酌情在前面添 0- ?it k=0,i 0; ?f（str0=+|tr0 =-） ?nt b=0 ； wile（strk=+|strk =-） ? if（ r= ） b+； ? k +; ? ?i（ str !=（ ） ret ； ? ha *np new