「第4-10章作业部分参考答案」

第4-５章作业:1.　不包含任何字符（长度为0)的串称为空串;由一个或多个空格(仅由空格符）组成的串　　称为空白串。２、设数组ａ［1…6０,１…70]的基地址为204８,每个元素占2个存储单元，若以列序为主序顺序存储，则元素ａ［32,58］的存储地址为8９50　　。答:不考虑０行0列,利用列优先公式：LOC(aiｊ)=LOC（ａｃ１，c2）＋[（j-ｃ2)*（d1-c1＋1)+i-c1)]*L得：LOC(a32，5８)＝2048+[(5８-1)＊（60－1+1)＋３2-1]]*2=８9５０第６章作业答案:１.画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林,而孩子结点的右子树均为兄弟。２.编写递归算法,计算二叉树中叶子结点的数目。思路：输出叶子结点比较简单,用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。Inｔｃouｎt_leａf(Bitｒｅｅ　root,int&sum)／/采用先序遍历的递归算法{　if(　roｏt!=NULＬ)//非空二叉树条件,还可写成ｉf(root)　｛if(!rｏot－>ｌchｉld&＆!root->rcｈild)//是叶子结点则统计并打印　{sum＋+；prinｔf(＂%ｄ\n＂,root->data）;}　coｕｎt_ｌeaｆ(ｒooｔ-＞ｌcｈild);　/／递归遍历左子树,直到叶子处;count_leａf(ｒｏot－>rchilｄ);}//递归遍历右子树，直到叶子处;}returｎ(０);}３.编写递归算法，求二叉树中以元素值为a的结点为根的子树的深度。int　Get_Sｕb＿Ｄｅpｔh(BitreeT，int　a）／／求二叉树中以值为x的结点为根的子树深度{　if(T-＞data==ｘ）｛　　ｐrintｆ(＂%ｄ＼n",Get_Depth(Ｔ））；／/找到了值为x的结点,求其深度　　exit　1；}　}eｌse　{　　ｉｆ(Ｔ->lｃhild)Get_Sｕb＿Depth(T->ｌchilｄ，ａ)；　　if（Ｔ-＞rｃhiｌｄ）Ｇet_Suｂ_Depth（T->rchiｌｄ,a)；//在左右子树中继续寻找}}//Get＿Ｓuｂ_DepｔhｉntＧｅt_Deptｈ(ＢiｔｒeeT)/／求子树深度的递归算法　{ｉf(!T)reｔurn　０;　else{　　m=Gｅt_Dｅpth(T-＞ｌchilｄ);　　　n＝Geｔ＿Deptｈ（Ｔ－>rchild);　rｅtｕrn（m＞n？ｍ:n)＋1;}}/／Get＿Depth４.假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0．07,０．19，0.0２,０．06，0.３２,0.03，0.２1，０.10。试为这8个字母哈夫曼编码。使用0～7的二进制表示形式是另一种编码。对于上述实例,比较两种方案的优缺点。解:方案1;哈夫曼编码先将概率放大1０0倍，以方便构造哈夫曼树。　w={7,19,2,6,３2,3,21,10},按哈夫曼规则:【[（2,3），6],　(7,10)】，……19,２1,32　　０　1　01　0１21　3210101106123　（10０）(4０）　　　（60)1９　21　32　（２8)（11)７10　６　（5)　　2　3方案比较:字母编号对应编码出现频率1110０0．072０00.19３111100.０24１11００.065100.3２6１11１10．037010.218110１0．10字母编号对应编码出现频率１000０.０720010．193010０.02401１0.0６51000.32６１010.０3７1１０0.２181１１0.１0方案１的WPL=2(0.19+０.32＋0．21)+4（0.0７+0．０6+0.１0）+5(0.02＋０.０3）=1.４4＋０.９2＋０.2５=2．61方案2的WPL＝3(０.1９+0．3２+0.21+０.07+０.06+0.1０+０.０2+0.０3)=3结论：哈夫曼编码优于等长二进制编码第7章作业答案：第9章作业答案:1.假定对有序表:（3,４，５,7，2４,30,42，54,６３,72，８7,95)进行折半查找,试回答下列问题：画出描述折半查找过程的判定树;若查找元素５4，需依次与哪些元素比较？若查找元素90,需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时的平均查找长度。解：先画出判定树如下(注:mid=(1+１2)/2=6）:305　6337　42　　87　　　　4　　　24　　547２　　　９5(2)查找元素５４，需依次与30，6３,　42，　５4　等元素比较；(3）查找元素９0,需依次与3０，63,８7,　9５,7２等元素比较;（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找１+2×2+4×3=17次；但最后一层未满，不能用８×４，只能用5×4＝20次，所以ASL=1/１2（17+20)=３7/12≈３.０8２、设哈希(Haｓh）表的地址范围为0～1７，哈希函数为：Ｈ（Ｋ)＝Ｋ　MＯＤ　16。K为关键字,用线性探测法再散列法处理冲突,输入关键字序列:　　(10,24，3２,17，31,30,4６,47，40，63，49）造出Hash表,试回答下列问题:画出哈希表的示意图;若查找关键字６3，需要依次与哪些关键字进行比较？若查找关键字６0，需要依次与哪些关键字比较?假定每个关键字的查找概率相等,求查找成功时的平均查找长度。解:（1）画表如下:０1２345６7８9１0111２1３１4１516１７3２176３4924401030314647（2）查找63,首先要与H(6３)＝6３%16=１5号单元内容比较,即63vｓ31　，ｎo;然后顺移,与46,47,３2,17,63相比，一共比较了６次！(３）查找６0,首先要与H(60)＝６0%1６=１2号单元内容比较，但因为１2号单元为空（应当有空标记)，所以应当只比较这一次即可。(４)　对于黑色数据元素,各比较1次;共６次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“4９”需要３次，“40”需要２次,“４6”需要3次，“47”需要３次，所以ＡＳL=1/11(6+2＋3×3)=17／1１=1．５454５45４54≈1.５５第10章作业答案:1、设要将序列(Q,　H,C，Y,　P,　A,M,S,　R,D,　F,Ｘ)中的关键码按字母序的升序重新排列,则:冒泡排序一趟扫描的结果是:　HC　ＱPAM　ＳRDF　Ｘ　Y；初始步长为4的希尔(ｓｈell)排序一趟的结果是　P　ACＳQＨ　ＦX　RDMY;二路归并排序一趟扫描的结果是HQCYＡPＭ　SＤRF　X;快速排序一趟扫描的结果是FHＣDＰAMQR　S　YＸ;堆排序初始建堆的结果是　ＡＤCRFＱ　ＭS　YPH　Ｘ。