2014数据结构习题集答案(2)

2020-04-17 22:12

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) (


2014数据结构习题集答案(2).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:服装立体裁剪教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: