首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
admin
2010-12-17
56
问题
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。
[说明]
HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下:
①根据给定的n各权值{W1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵树Ti中只有一个带权为wi的根节点,其左右子树均空。
②在F中选取两棵根节点的权值较小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左右予树根节点的权值之和。
③从F中删除这两棵树,同时将新得到的二叉树加入到F中。
重复②③,直到F中只剩一棵树为止。
函数中使用的预定义符号如下:
#define INT MAX 10000
#define ENCODING LENGTH 1000
typedef enum(none,left_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 *sl,int *s2)
/*在0~END之间,找出最小和次小的两个节点序号,返吲S1、S2*/
{
int i;
int min 1=INT_MAX;
int min 2=INT_MAX;
for(i=0;i<=end;i++){/*找最小的节点序号*/
if(( (1) )&&(HT
.weight<minl)){
*s1=i;
min 1=HT
.weight;
}
}
for(i=0;i<=end;i++){/*找次小节点的序号*/
if((HT
.parent==0)&&( (2) )
&&(min 2>HT
.weight)){
*s2=i;
min 2=HT
.weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree&HT)/*建立HUFFMAN树*/
{
int i;
int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select( (3) );
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left child;
HT[s2].sigh=right child;
HT
.weight=(4);
}
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)
{ /*将句子进行编码*/
int i=0;
int j;
while(sen
!=’\0’){
for(j=0;j<n;j++){
if(HT[j].letter==sen
)(/*字母吻合则用代码取代*/
strcat(coding, (5) );
break;
}
}
i++;
if (Sen [1]==32) i++;
}
printf("\n%s",coding);
}
(5)
选项
答案
HT[j].code
解析
根据算法说明的②可知是根据根节点权值选择,即只考察根节点,而根节点对应的parent等于0,故空(1)应填HT
.parent==0。此答案可由空(2)处的if条件容易得出。
至于空(2),此处是找次小的,自然需要排除最小的,sl记录了最小树的下标,故填*s1 !=i。
仔细参照Select函数的定义,容易得出空(3)答案。应填“HT,i-1,&s1,&s2”,要注意的是后两个参数需要传递地址,因形参是指针。
根据算法说明的②,“置新构造二又树的根节点的权值为其左右子树根节点的权值之和”,而此处HT
的左右子树的根节点分别为HT[s1]和HT[s2],所以空(4)应填HT[s1].weight+HT[s2].weight。
由注释“字母吻合则用代码取代”可知,此处是将对应代码加到coding中,而节点的code字段存储了节点对应编码,故空(5)应填HT[j].code。
转载请注明原文地址:https://kaotiyun.com/show/5qDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
(3)是指按内容访问的存储器。
为了能按时交付系统,开发小组在实现“确定最优任务分配方案”功能时采用了蛮力的方法。在系统交付后,对可能出现更多任务量的情况,采用更有效的方法来实现该功能,这属于()。
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现他们之间的同步过程如下图所示。其中,信号量S是一个互斥信号量,初值为(1);S1是一个(2);S2是一
分配给某公司网络的地址块是220.17.192.0/20,该网络被划分为(1)个C类子网,不属于该公司网络的子网地址是(2)。(1)
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经()运算得1,则可断定这两个数相加的结果产生了溢出。
正确的集成测试描述包括(43)。①集成测试也叫做组装测试,通常是在单元测试的基础上,将模块按照设计说明书要求进行组装和测试的过程②自顶向下的增殖方式是集成测试的一种组装方式,它能较早地验证主要的控制和判断点,对于输入输出模块、复杂算法模
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。②处应填入?
在性能测试中,关于数据准备,(65)描述是正确的。①识别数据状态验证测试案例。②初始数据提供了基线用来评估测试执行的结果。③业务数据提供负载压力背景。④脚本中参数数据真实模拟负载。
结构化分析(StructuredAnalysis,SA)是面向数据流的需求分析方法,______不属于SA工具。A.分层的数据流图B.数据词典C.问题分析图D.描述加工逻辑的结构化语言、判定表或判定树
随机试题
Wheredoesthisconversationprobablytakeplace?
(2012年4月)______是指对晋升领导职务的公务员在任职前或者任职后一年内进行的培训。
猩红热的主要病位为:
患者张某,女性,62岁。眩晕,头重如蒙,胸闷恶心,食少寐多,舌苔白腻,脉滑。治疗应首选
A.一级召回B.二级召回C.三级召回D.主动召回根据药品安全隐患的严重程度,药品召回分为三级对可能引起暂时的或者可逆的健康危害的药品实施的召回是()
港口与航道工程安全生产要求中,起重作业前必须了解起吊物件的基本情况,如()等,包括施工现场的地形、地貌、水域情况,运输道路及其场地面积等。根据被吊物的特点及周围环境,制订施工方案,在施工方案的内容中,必须制定专门的安全技术措施。
汽车库、修车库的火灾危险性有哪些?
基金托管人对基金运作不需进行独立、专门的会计核算活动,与基金管理人共同核算即可。()
Atthemoment,mobileTVismostlystreamedover3Gnetworks.Butsendinganindividualdatastreamtoeachviewerisinefficien
Oncetheydecidedtohavechildren,MiShelandCarlMeissnertackledthenextbigissue:Shouldtheytrytohaveagirl?Itwas
最新回复
(
0
)