77范文网 - 专业文章范例文档资料分享平台

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

来源:网络收集 时间:2020-04-17 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

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)在线全文阅读。

2014数据结构习题集答案(2).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/988127.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: