3. (1)二叉树 :树形结构同(2)
(2)二叉树的后序后继线索树 a c f b c a b d h j e i d e f g g h i 应的森林j GJHDBEIFCA 4.(1)哈夫曼树 (2)电文中六个字符的哈夫曼编码如下:100 A:01 0 1 B:000 C:111 44 56 D:110 E:10 0 1 0 1 F:001 18 28 28
26 0 1 A E 0 1 8 10 11 17
B F D C
3)二叉树对
(
5. 方案1;哈夫曼编码
先将概率放大100倍,以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10},按哈夫曼规则:
(100) 0 1 0 1 0 1 (40) (6021 ) 19 32 0 1 0 1 0 1 19 21 32 (28)7 10 6 0 1 2 3 (17) (11) 7 10 6 (5) 2 3
方案比较: 字母对应出现字母对应出现 编号 编码 频率 编号 编码 频率 1100 0.07 1 000 0.07 1 2 00 0.19 2 001 0.19 11110 0.02 3 010 0.02 3 4 1110 0.06 4 011 0.06 10 0.32 5 100 0.32 5 6 101 0.03
方案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 结论:哈夫曼编码优于等长二进制编码
三、算法题答案 (1)
// 求位于先序序列中第k个位置的结点的值, // e中存放结点的返回值,i 为计数器
Status PONodeK(TElemType &e, int &i, int k, BiTree &T) {
if(T){
i++;
if(i==k) e=T->data; else{
PONodeK(e,i,k,T->lchild); PONodeK(e,i,k,T->rchild); } }
return OK; }
(2)
// 求二叉树中叶子结点的数目
Status POLeafNodeNum(int &i, BiTree &T) {
if(T){
if(!T->lchild && !T->rchild) i++; POLeafNodeNum(i,T->lchild); POLeafNodeNum(i,T->rchild); }
return OK }
(3)
// 按先序交换二叉树的左右子树 Status ExchangeBiTree(BiTree& T) {
BiTree p; if(T){
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
ExchangeBiTree(T->lchild); ExchangeBiTree(T->rchild); }
return OK;
}
(4)
// 求二叉树的深度 int Depth (BiTree T ){
int depthLeft,depthRight,depthval; if ( !T ) depthval = 0; else {
depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );
if (depthLeft> depthRight ) depthval = 1 + depthLeft; else depthval = 1 + depthRight; }
return depthval; }
第七章 参考答案:
一.单选与填空
1.B 2. C 3.D 4.B 5.C 6.D 7.n(n-1)/2 8. B 9.A 10.A 11. A 12. 15
二.解答题 1.
2. (1)无向图 B ??010010??101001? A C D F ??010110???001001? ???101001??10110?? E ?0?
2)邻接矩阵存储结构A (B E C F D
3) (
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库2014数据结构习题集答案(2)在线全文阅读。
相关推荐: