第4–10章作业部分参考解析.doc

第4-5章作业答案： 1. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。 答：不考虑0行0列，利用列优先公式： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 第6章作业答案： 1.画出和下列二叉树相应的森林。 答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。 2.编写递归算法，计算二叉树中叶子结点的数目。 思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。 Int count_leaf(Bitree root,int sum) //采用先序遍历的递归算法 { if ( root!=NULL ) //非空二叉树条件，还可写成if(root) {if(!root-lchild!root-rchild) //是叶子结点则统计并打印 {sum++; printf(%d\n,root-data);} count_leaf(root-lchild); //递归遍历左子树，直到叶子处； count_leaf(root-rchild); } //递归遍历右子树，直到叶子处； } return(0); } 3．编写递归算法，求二叉树中以元素值为a的结点为根的子树的深度。 int Get_Sub_Depth(Bitree T,int a)//求二叉树中以值为x的结点为根的子树深度 { if(T-data==x) { printf(%d\n,Get_Depth(T)); //找到了值为x的结点,求其深度 exit 1; } } else { if(T-lchild) Get_Sub_Depth(T-lchild,a); if(T-rchild) Get_Sub_Depth(T-rchild,a); //在左右子树中继续寻找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子树深度的递归算法 { if(!T) return 0; else { m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; } }//Get_Depth 4.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100） （40） （60） 19 21 32 （28） （11） 7 10 6 （5） 2 3 方案比较： 方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码 第7章作业答案： 第9章作业答案： 1.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素54，需依次与哪些元素比较？ 若查找元素90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： 先画出判定树如下（注：mid=?(1+12)/2?=6）： 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素9