首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{w1,w2,…,wn}构成
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{w1,w2,…,wn}构成
admin
2014-10-11
61
问题
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。
【说明】
Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下:
①根据给定的n各权值{w
1
,w
2
,…,w
n
}构成n棵二叉树的集合F={T
1
,T
2
,…,T
n
},其中每棵树T
i
中只有一个带权为w
i
的根节点,其左右子树均空。②在F中选取两棵根节点的权值较小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左右子树根节点的权值之和。③从F中删除这两棵树,同时将新得到的二叉树加入到F中。重复②③,直到F中只剩一棵树为止。函数中使用的预定义符号如下:
#detineINT—MAX 10000
#define ENCODING—LENGTH 1000
typedef enum(rlone, 1eft一child, right一child) which;
/*标记是左孩子还是右孩子*/
typedef char Elemtype;
typedef struct TNode{//Huffman树节点
Elemtype letter;
int weight; //权值
int parent; //父节点
Which Sigh;
char*code; //节点对应编码
)HTNode,*HuffmanTree;
int n;
char coding[50];//储存代码
【函数】
void Select(HuffmanTree HT,int end,int*s1,int*s2)
/*在0~END之问,找出最小和次小的两个节点序号,返回s1、s2*/
{
int i;
int mini=INT_MAX;
int min2=INT_MAX;
for(i=0;i<=end;i++){/*找最小的节点序号*/
if((1)&&(HT
.weight
*s1=i;
minl=HT
.weight;
}
}
for(i=0;i<=end;i++){/*找次小节点的序号*/
i f((HT
.parent==0)&&((2))
&&(min2 >HT
.weight)){
*S2:i;
min2=HT
.weight:
}
}
}
void HuffmanTreecrea七(HuffmanTree&HT)/*建立HuFFMAN树*/
{
int i;
int m=2*n一1;
int S1,S2;
for(i=n;i
Select((3));
HT[S1].parent=i:
HT[s2].parent=i;
HT[S1].Sigh=1eft_chiid;
HT[s2].Sigh=right—chiid;
HT
.weight= (4);
}
void HuffmanTreeEnc。ding(char sen[],HuffmanTree HT)
{ /*将句子进行编码*/
int i=0;
int j;
while(sen
!=’\0’){
for(J=0;j
i f(HT[j].1etter==sen
)(/*字母匹配则用代码取代*/
strcat(coding, (5));
break;
}
}
i++:
if(sen
==32)i++;
printf(“\n%s”,coding);
}
选项
答案
(1)HT[i].parent==0 (2)*s1!=i (3)HT,i—1,&s1,&s2 (4)HT[s1].weight+HTIs2].weight (5)HT[j].code
解析
根据算法说明的②可知是根据根节点权值选择,即只考察根节点,而根节点对应~parent等于0,故空(1)应填HT
.parent=0。此答案可由空(2)处的i涤件容易得出。至于空(2),此处是找次小的,自然需要排除最小的,S1记录了最小树的下标,故填*s1!=i。仔细参照Select~数的定义,容易得出空(3)答案。应填“HT,i—l,&sl,&s2”,要注意的是后两个参数需要传递地址,因形参是指针。根据算法说明的②,“置新构造二叉树的根节点的权值为其左右子树根节点的权值之和”,而此处HT
的左右子树的根节点分别为HT[s1]和NHT[s2],所以空(4)应填HT[s1].weight+HT[s2].weight。由注释“字母匹配则用代码取代”可知,此处是将对应代码加到coding中,而节点的code字段存储了节点对应编码,故空(5)应填HT[j].code。
转载请注明原文地址:https://kaotiyun.com/show/NaDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的权重表示活动的持续时间(天),则里程碑C在关键路径上。在其他活动按时完成的情况下,活动FJ最多可以晚_______天开始而不影响工期。
函数main()、f()的定义如下所示。调用函数f()时,第一个参数采用传值(callbyvalue)方式,第二个参数采用传引用(callbyreference)方式,main()执行后输出的值为_______。
通常VLAN有静态和动态2种实现方式,这2种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?在VLAN中,STP和VTP是什么协议?各有什么作用?
在由L2TP构建的VPN中,主要由①和②两种类型的服务器构成。1.将图5-1中①和②处空缺名称填写在答题纸的相应位置。2.简要说明两种服务器的主要作用。某路由器(在图5-1中没有标出)的部分配置信息如下所示,请解释其中标有下划线部分的含
限制MailUser邮件主机里每个用户的邮箱大小不超过10MB,如何配置?限制MailUser邮件主机里每个用户邮箱里所能存放的最多邮件数量不超过20个,如何配置?
阅读以下说明,回答问题1~6。[说明]某公司已有一个100用户的有线局域网。由于业务的发展,现有的网络不能满足需求,需要增加40个用户的网络连接,并在公司客户接待室连接网络以满足合作伙伴实时咨询的需求。现结合公司的实际情况组建无线局域网,具体拓扑
认真阅读下列说明信息,回答问题1至问题5。[说明]在一个基于TCP/IP协议的网络中,每台主机都有一个IP地址,根据获得IP地址的方式不同,可以分为静态IP和动态IP。例如:用宽带入网,会有一个固定的IP地址,每次连入Internet,你的IP地
阅读以下有关传统局域网络运行和维护的叙述,将应填入(n)处的字句写在对应栏内。在对网络运行及维护前首先要了解网络,包括识别网络对象的硬件情况、判别局域网的拓扑结构和信道访问方式、确定网络互联以及用户负载等。常见的3种拓扑结构是星形、(1)与(2)拓
请阅读以下说明和Socfort程序,将应填(n)处的字句写在对应栏内。网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。以下是一个简单的客户机程序(服务器程序略),其工作过程非常简单:客
随机试题
左支气管()
男性,19岁,夏天野浴后发热、呕吐咖啡渣样物,查体:T38.5℃,巩膜黄染、全身皮肤散在出血点,心率100次/分,律齐,腹软、无压痛,肝脾未触及,最可能的诊断是
A.单核细胞B.淋巴细胞C.中性粒细胞D.嗜酸性粒细胞E.嗜碱性粒细胞犊牛感染了化脓性棒状杆菌,剖检见肾脏有明显的化脓灶,组织病理学观察见病灶局部有大量的炎性细胞浸润,该疾病炎症病灶中渗出的主要炎性细胞类型是()。[2010年真题]
委托为监理人驻工地监理机构开展正常工作提供协助服务,其服务内容包括()。
以下内容属于水利枢纽工程施工组织设计文件中临时工程施工部分内容的有()。
某建筑装饰公司承担了某宾馆200套客房的装修施工:任务。施工按先木门窗安装、吊顶后铺没实木地板。最后对吊顶及墙面进行涂饰。在涂料施工中,为防止门扇、玻璃及木饰面被污染,在施涂工作面周边粘贴美纹纸。
2011年2月16日,利比亚紧张局势升级,安全形势发生重大变化,我国政府迅速撤离了我在利比亚人员。该行动主要体现了主权国家的()。
国际储备运营管理有三个基本原则是()。
设有定义:inta=1,b=2,c=3;以下语句中执行效果与其它三个不同的是
Georgeisayoungman.Hehasaverybigdogandhehasaverysmallcar,too.Helikesplayingbasketball.LastMondayheplaye
最新回复
(
0
)