数据结构自测题及解答

Depth(BinaryTreeT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth8.解:方案1;哈夫曼编码先将概率放大100倍,以方便构造哈夫曼树。w={7,19,2,6,32,3,21,10},按哈夫曼规则:构造哈夫曼树如下:010101213210101106123(100)(60)192132(28)(11)7106(5)23方案比较:字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率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结论:哈夫曼编码优于等长二进制编码9.答:10.voidinsert(parable&x){if(currentSize==array.size()-1)array.resize(array.size()*2);//Percolateupinthole=++currentSize;for(;hole>1&&x<array[hole/2];hole/=2)array[hole]=array[hole/2];?array[0]=array[hole]=x;}11.答:12.A\D/\BJ\/CG/\FH/\EI■