第410章作業(yè)部分參考答案

第4-5章作業(yè)答案：1.不包含任何字符（長(zhǎng)度為0）的串稱為空串；由一個(gè)或多個(gè)空格（僅由空格符）組成的串稱為空白串。2、設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為8950。答：不考慮0行0列，利用列優(yōu)先公式：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章作業(yè)答案：1.畫(huà)出和下列二叉樹(shù)相應(yīng)的森林。答：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。2.編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來(lái)。Intcount_leaf(Bitreeroot,int&sum)//采用先序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹(shù)條件，還可寫(xiě)成if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印{sum++;printf("%d\n",root->data);}count_leaf(root->lchild);//遞歸遍歷左子樹(shù)，直到葉子處；count_leaf(root->rchild);}//遞歸遍歷右子樹(shù)，直到葉子處；}return(0);}3．編寫(xiě)遞歸算法，求二叉樹(shù)中以元素值為a的結(jié)點(diǎn)為根的子樹(shù)的深度。intGet_Sub_Depth(BitreeT,inta)//求二叉樹(shù)中以值為x的結(jié)點(diǎn)為根的子樹(shù)深度{if(T->data==x){printf("%d\n",Get_Depth(T));//找到了值為x的結(jié)點(diǎn),求其深度exit1;}}else{if(T->lchild)Get_Sub_Depth(T->lchild,a);if(T->rchild)Get_Sub_Depth(T->rchild,a);//在左右子樹(shù)中繼續(xù)尋找}}//Get_Sub_DepthintGet_Depth(BitreeT)//求子樹(shù)深度的遞歸算法{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth4.假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6],(7,10)】,……19,21,3201010121321010101213210101106123（40）（60）192132（28）（11）7106（5）23方案比較：字母編號(hào)對(duì)應(yīng)編碼字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案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結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼第7章作業(yè)答案：第9章作業(yè)答案：1.假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：畫(huà)出描述折半查找過(guò)程的判定樹(shù)；若查找元素54，需依次與哪些元素比較？若查找元素90，需依次與哪些元素比較？假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：先畫(huà)出判定樹(shù)如下（注：mid=(1+12)/2=6）：30563374287424547295(2)查找元素54，需依次與30,63,42,54等元素比較；(3)查找元素90，需依次與30,63,87,95,72等元素比較；（4）求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹(shù)的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.082、設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問(wèn)題：畫(huà)出哈希表的示意圖；若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：（1）畫(huà)表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?。?）查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。（4）對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55第10章作業(yè)答案：1、設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是：HCQPAMSRDFXY；初始步長(zhǎng)為4的希爾（