资源描述：
《第4-10章作业部分参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途第４-5章作业答案：1. 不包含任何字符（长度为０）的串称为空串；由一个或多个空格(仅由空格符）组成的串 称为空白串。２、设数组a[１…6０, 1…7０］的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储，则元素a[32,58]的存储地址为８９50 。答:不考虑0行０列，利用列优先公式:ＬＯC(aiｊ)=ＬOＣ(ac１,c2）+[(j－c２)＊(d1－c1＋1)＋i－ｃ１)]*L得:ＬＯＣ(ａ３2,58)＝2０４８+[(５８-1)*(60-１+1)+32－1]］*2＝８950第6章作业答案：1.画出和下列二叉树相应的森林。答:注意根右边
2、的子树肯定是森林,而孩子结点的右子树均为兄弟。２.编写递归算法,计算二叉树中叶子结点的数目。思路:输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者,则为叶子，将其统计并打印出来。Ｉｎtcounｔ_ｌeaｆ(Biｔreeroｏt,int ＆sｕｍ）／/采用先序遍历的递归算法｛if（roｏt！＝NULL ） //非空二叉树条件，还可写成iｆ(ｒooｔ) {if(!root－>lchild&&！roｏt->rchilｄ)//是叶子结点则统计并打印{ｓｕm++; ｐrinｔf（"%d",rｏot-＞dａta);｝ cｏuｎt＿leaf(root->ｌchｉld); //递
3、归遍历左子树,直到叶子处;count＿leａｆ（roｏt->rcｈｉld）;} //递归遍历右子树,直到叶子处；}retｕrn(0);}３.编写递归算法，求二叉树中以元素值为a的结点为根的子树的深度。ｉnt Geｔ＿Ｓuｂ＿Ｄepth(BitreｅT，ｉntａ)//求二叉树中以值为ｘ的结点为根的子树深度 ｛ iｆ（T->dａｔa==x）{ printf（＂%ｄｎ",Geｔ_Depｔh(T)）;//找到了值为x的结点,求其深度 ｅxit1;个人收集整理勿做商业用途}}elsｅ ｛ iｆ(Ｔ->lchild)Get_Ｓub_Ｄeｐtｈ(Ｔ->lchilｄ,a);if(T->r
4、cｈｉld)Get＿Ｓuｂ＿Dｅpth(T->rcｈild,a);//在左右子树中继续寻找 ｝}//Gｅt＿Sub＿DeptｈiｎｔGet_Deptｈ(Ｂｉtree T）/／求子树深度的递归算法 ｛ ｉf(!T） returｎ0;else{m=Get＿Depｔh(T->lcｈild); n＝Ｇet＿Ｄepth(T->rcｈiｌd); ｒｅtｕｒn(m>n?m:ｎ)＋1; }}/／Ｇet＿Depth4．假设用于通信的电文仅由８个字母组成，字母在电文中出现的频率分别为0.07,0．１9，0.02,0.06，０．32,０.03,0.２1,0.10。试为这８个字母设计哈夫曼编码
5、。使用0～7的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。解:方案1；哈夫曼编码先将概率放大100倍,以方便构造哈夫曼树。w=｛7,19,２,6,32,3，２1,1０}，按哈夫曼规则：【[(2,3),6］,(７，１0）】, ……19,21,32 0 1 0 1 ０ 1192132 0101０ 171060123 (100)(４0） (60）19 21 32 （2８)（17）（11)7 1０ 6 （５） 23方案比较：字母编号对应编码出现频率111000．０72000.193111１00．０24１1100．06510０.326１１１1
6、10.０37０10.２1811０10．10字母编号对应编码出现频率1000０.0７2０0１0.1930１０0.024011０.0６51000.326101０.0371１0０.2181110.1０个人收集整理勿做商业用途方案1的WＰL=２(0．１9+0.32＋０.２1)+4(0．07＋0.0６+０.10)+5（０.02+0.0３)=１.44+０.9２+0．２5=2.61方案2的WPL＝3（0．19＋０.32+0.21+0.07＋0.06+0.10＋０.02＋0．03）=3结论：哈夫曼编码优于等长二进制编码第７章作业答案:第9章作业答案：1.假定对有序表：(３,4，5,7，24,30
7、，42，54,63，７２,８7,95）进行折半查找，试回答下列问题:（1）画出描述折半查找过程的判定树;（2）若查找元素54,需依次与哪些元素比较?（3）若查找元素９0,需依次与哪些元素比较？（4）假定每个元素的查找概率相等,求查找成功时的平均查找长度。解:（1）先画出判定树如下（注：ｍｉd＝ë(1+１２)/２û=６）:305 ６3个人收集整理勿做商业用途3７ ４2 87 ４ 24 5４ ７２ 95(2）查找元素54,需依次与３0,63，４２，５４等元素比较；（
