PAGEPAGE2習題答案一、選擇題1-8：DCBBDDBC二、判斷題1-5：錯錯錯對錯三、填空題1.(1)80(2)001（不唯一）2.2n0-13.（1）5（2）964.（1）2h-1（2）2h-15、（1）順序（2）n/2+1（3）n四、應用題1、哈夫曼樹的形態(tài)不唯一2、各字符的二進制編碼為：a：00b：11110c：1110d：11111e：10f：110g：013、①是堆②不是堆調(diào)成堆100,90,80,25,85,75,60,20,10,70,65,504、27565346227565346261908170897875125035036539082754625128978717061(2)求次小值5036535036536127546251228978717090890865361503462512897275170875、(1)哈夫曼樹。(2)譯碼過程：譯碼過程與編碼一樣需要使用哈夫曼樹。譯碼過程為：自左向右逐一掃描碼文，并從哈夫曼樹的根開始，將掃描得到的二進制串中的碼位與哈夫曼樹分支上標的0、1相匹配，以確定一條從根到葉子的路徑，一旦達到葉子，則譯出了一個字符；再回到樹根，從二進位串的下一位開始繼續(xù)譯碼，直到掃描碼文結束。(3)只需判定存儲有字符信息的節(jié)點是否全部為葉子結點即可。若存儲有某個字符信息的節(jié)點非葉子結點，即有子節(jié)點，那么它的0/1編碼一定是它孩子節(jié)點0/1編碼的前綴，違反了前綴特性。五、算法設計1、(1)voidsift(intn){∥假設data[1..n-1]是大堆,本算法把data[1..n]調(diào)成大堆intj=n;data[0]=data[j];for(inti=n/2;i>=1;i=i/2)if(data[0]>data[i]){data[j]=data[i];j=i;}elsebreak;data[j]=data[0];}(2)voidheapBuilder(){for(inti=2;i<=curLength;i++)sift(i);}2、參見代碼7.6【答案要點】(1)算法的基本設計思想：表達式樹的中序序列加上必要的括號即為等價的中綴表達式。可以基于二叉樹的中序遍歷策略得到所需的表達式。(3分)表達式樹中分支結點所對應的子表達式的計算次序，由該分支結點所處的位置決定。為得到正確的中綴表達式，需要在生成遍歷序列的同時，在適當位置增加必要的括號。顯然，表達式的最外層(對應根結點)及操作數(shù)(對應葉結點)不需要添加括號。(2分)(2)算法實現(xiàn)(10分)voidBtreeToE(BTree*root){BtreeToExp(root，1)； //根的高度為1}voidBtreeToExp(BTree*root,intdeep){ //中序遍歷求中綴表達式if(root==NULL)return;elseif(root->left==NULL&&root->right==NULL)//若為葉結點printf(“％s”，root->data)； //輸出操作數(shù)else{if(deep>1)printf(“(”)； //若有子表達式則加1層括號BtreeToExp(root->left，deep+1)； printf(“％s”，root->data)； //輸出操作符Btr