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

1、數(shù)據(jù)結(jié)構(gòu)第六次作業(yè)選擇題1.表達(dá)式x*(y-z)+u的逆波蘭式（后綴表達(dá)式）表示是（）。A）xyzuu-+B）xyz-*u+C）xyz*-u+D）+-*xyzuB規(guī)則：如表達(dá)式為數(shù)或者簡(jiǎn)單變量，則相應(yīng)二叉樹中只有一個(gè)根節(jié)點(diǎn),其數(shù)據(jù)域存儲(chǔ)此表達(dá)式信息；如表達(dá)式=（第1操作數(shù)）（運(yùn)算符）（第2操作數(shù)），則相應(yīng)的二叉樹中以左子樹表示第1操作數(shù)，右子樹表示第2操作數(shù)，根節(jié)點(diǎn)的數(shù)據(jù)域存儲(chǔ)運(yùn)算符，操作數(shù)本身又可以為表達(dá)式。1設(shè)有表達(dá)式：a*(b-c)/d+f/(g+h*i)，試給出此表達(dá)式的下面結(jié)果：二叉樹表示；逆波蘭式表示；中綴表示；綜合題逆波蘭式表示(后綴即為左右根)： abc-*d/fghi*+/+

2、中綴表示(即為左根右)： a*b-c/d+f/g+h*i3已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8、11，試求對(duì)應(yīng)哈夫曼樹。步驟如下：(1) 將w1、w2、，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。5.28 Build the Huffman coding tree and determine the

3、 codes for the following set of letters and weights: Letter A B C D E F G H I J K L Frequency 2 3 5 7 11 13 17 19 23 31 37 41 What is the expected length in bits of a message containing characters for this frequency distribution? 209 / 83 126 / / l 42 55 71 / / / H I 24 J 34 K / / E F 17 G / D 10 /

4、5 C / A B l 00 h 010 i 011 e 1000 f 1001 j 101 d 11000 a 1100100 b 1100101 c 110011 g 1101 k 111 Ffllengthini1ii其中F代表總頻度或權(quán)值,n代表總個(gè)數(shù),li代表編碼長(zhǎng)度,fi代表頻度本題中長(zhǎng)度為 3.23445 5.25 Show the max-heap that results from running build Heap on the following values stored in an array: 調(diào)整為大頂堆 10 5 12 3 2 1 8 7 9 4 10 / 5

5、 12 / / 3 2 1 8 / / 7 9 4 （10，5，12，3，2，1，8，7，9，4） 從最后一非終端節(jié)點(diǎn)開始篩選 10 / 5 12 / / 3 4 1 8 / / 7 9 2 10 / 5 12 / / 9 4 1 8 / / 7 3 2 10 / 5 12 / / 9 4 1 8 / / 7 3 2 10 / 9 12 / / 7 4 1 8 / / 5 3 2 12 / 9 10 / / 7 4 1 8 / / 5 3 2大頂堆為12,9,10,7,4,1,8,5,3,2 證明：當(dāng)n=1時(shí),即其中的葉子節(jié)點(diǎn)數(shù)為K,滿足(K-1)*1+1=K,即成立；假設(shè)當(dāng)n=x時(shí)，葉子節(jié)點(diǎn)

6、數(shù)為(K-1)x+1成立；那么當(dāng)n=x+1時(shí)，某一個(gè)葉子節(jié)點(diǎn)變成非葉子節(jié)點(diǎn)則會(huì)增加K-1個(gè)葉子節(jié)點(diǎn)。即最終葉子節(jié)點(diǎn)數(shù)目為：(K-1)x+1+K-1=(K-1)(x+1)+1 成立。6.13Use mathematical induction to prove that the number of leaves in a non-empty full K-ary tree is (K-1)n+1, where n is the number of internal nodes. 6.15Find the overhead fraction for a full K-ary tree implem

7、entation with space requirements as follows: 對(duì)于滿足下面空間要求的滿K叉樹實(shí)現(xiàn)方法，計(jì)算其結(jié)構(gòu)性空間開銷比例 (a) All nodes store data, child pointers, and a parent pointer. The data field requires four bytes and each pointer requires four bytes. (b) All nodes store data and child pointers. The data field requires six-teen bytes a

8、nd each pointer requires four bytes. (c) All nodes store data and a parent pointer, and internal nodes store child pointers. The data field requires eight bytes and each pointer requires four bytes. (d) Only leaf nodes store data; only internal nodes store child pointers. The data field requires fou

9、r bytes and each pointer requires two bytes. 2k/(4+2k)4(k+2)/(16+4(k+2)4k/(16+4k)4(k+1)/(4+4(k+1)6.7 Using the weighted union rule and path compression, show the array for the parent pointer implementation that results from the following series of equivalences on a set of objects indexed by the valu

10、es 0 through 15. Initially, each element in the set should be in a separate equivalence class. When two trees to be merged are the same size, make the root with greater index value be the child of the root with lesser index value. 使用重量權(quán)衡合并規(guī)則與路徑壓縮，對(duì)下列從0到15之間數(shù)的等價(jià)對(duì)進(jìn)行合并，并給出所得樹的父指針表示法的數(shù)組表示。在初始情況下，集合中國(guó)的每個(gè)元素分別在獨(dú)立的等價(jià)類中，當(dāng)兩棵樹規(guī)模同樣大時(shí)，使節(jié)點(diǎn)值較大的根節(jié)點(diǎn)作為值較小的根節(jié)點(diǎn)的子節(jié)點(diǎn)。(0, 2) (1, 2) (3, 4) (3, 1) (3, 5) (9, 11) (12, 14) (3, 9) (4, 14) (6, 7) (8, 10) (8, 7) (7, 0) (10, 15) (10, 13) 重量權(quán)衡合并規(guī)則：是在做“