算法与数据结构（C++语言版）（第2版） 第7章课后习题答案

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、哈夫曼树的形态不唯一2、各字符的二进制编码为：a：00b：11110c：1110d：11111e：10f：110g：013、①是堆②不是堆调成堆100,90,80,25,85,75,60,20,10,70,65,504、27565346227565346261908170897875125035036539082754625128978717061(2)求次小值5036535036536127546251228978717090890865361503462512897275170875、(1)哈夫曼树。(2)译码过程：译码过程与编码一样需要使用哈夫曼树。译码过程为：自左向右逐一扫描码文，并从哈夫曼树的根开始，将扫描得到的二进制串中的码位与哈夫曼树分支上标的0、1相匹配，以确定一条从根到叶子的路径，一旦达到叶子，则译出了一个字符；再回到树根，从二进位串的下一位开始继续译码，直到扫描码文结束。(3)只需判定存储有字符信息的节点是否全部为叶子结点即可。若存储有某个字符信息的节点非叶子结点，即有子节点，那么它的0/1编码一定是它孩子节点0/1编码的前缀，违反了前缀特性。五、算法设计1、(1)voidsift(intn){∥假设data[1..n-1]是大堆,本算法把data[1..n]调成大堆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分)表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。(2分)(2)算法实现(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)； //输出操作数else{if(deep>1)printf(“(”)； //若有子表达式则加1层括号BtreeToExp(root->left，deep+1)； printf(“％s”，root->data)； //输出操作符Btr