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