首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
admin
2010-12-17
27
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
GB17859-1999《计算机信息系统安全保护等级划分准则》中将计算机安全保护划分为(53)个级别。
在各种不同的软件需求中,()描述了产品必须要完成的任务,可以在用例模型中予以说明。
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现他们之间的同步过程如下图所示。其中,信号量S是一个互斥信号量,初值为(1);S1是一个(2);S2是一
算术表达式a+(b-c)*d的后缀式是()(一、+、*表示算术的减、加、乘运算,运算符的优先级和结合性遵循惯例)。
统一过程(UP)是一种用例驱动的迭代式增量开发过程,每次迭代过程中主要的工作流包括捕获需求、分析、设计、实现和测试等。这种软件过程的用例图(Use Case Diagram)是通过(19)得到的。
测试记录包括、(64)。①测试计划或包含测试用例的测试规格说明。②测试期间出现问题的评估与分析。③与测试用例相关的所有结果,包括在测试期间出现的所有失败。④测试中涉及的人员身份。
(41)不是易用性测试包括的内容。
在计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA等。其中,采用______方式时,不需要CPU控制数据的传输过程。
序言性注释是指在每个程序或模块开头的一段说明,起辅助理解程序的作用,一般包括:程序的表示、名称和版本号;程序功能描述;接口与界面描述;输入输出数据说明:开发历史;与运行环境有关的信息等。下列叙述中不属于序言性注释的是(23)。
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
随机试题
根据《合同法》,合同的订立需要顺序经过()。
码头接岸结构及岸坡在施工期和使用期整体稳定性验算应符合下列规定:施工期应验算()等各种情况下的岸坡稳定性。
根据现行国家标准《建筑消防设施的维护管理》,在建筑消防设施维护管理时,应对自动喷水灭火系统进行巡查并填写《建筑消防设施巡查记录表》,下列内容中,不属于自动喷水灭火系统巡查记录内容的是()。
企业财务管理体制的核心是()。
某办公用品在公司将顾客细分为两类:一类是大客户,这类顾客由该公司的全国客户经理负责联系,另一类是小客户,由外勤推销人员负责联系。该公司进行市场细分的依据是()。
下列先秦思想家中,主张施仁政行王道的一位是()。
坚持与时俱进,就是党的全部理论和全部工作要
Whenwearrivedattherailwaystation,theywere______there.
ASwedejoinedNapoleon’sArmybecauseheadmiredthegreatgeneralsomuchthathewantedtofightforhim.HeknewnoFrenchb
Whatpurposedoesthispassagepossiblyserve?Howmanycomputermodelsarementionedinthispassage?
最新回复
(
0
)