首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。 [说明] (1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。 [说明] (1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如
admin
2010-01-15
98
问题
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。
[说明]
(1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如图3-26所示的最优二叉树,以及相应的结构数组Ht(如表3-12所示,其中数组元素Ht[0]不用)。
结构数组Ht的类型定义如下:
(2)用“0”或“1”标识最优二叉树中分支的规则是:从一个结点进入其左(右)孩子结点,就用“0”(或“1”)标识该分支(示例见图3-26)。
(3)若用上述规则标识最优二叉树的每条分支后,从根结点开始到叶子结点为止,按经过分支的次序将相应标识依次排列,可得到由“0”、“1”组成的一个序列,称此序列为该叶子结点的前缀编码。例如图3-26所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。
[函数说明1]
函数void LeafCode (int root,int n)的功能是:采用非递归方法,遍历最优二叉树的全部叶子结点,为所有的叶子结点构造前缀编码。其中,形参root为最优二叉树的根结点下标;形参n为叶子结点个数。
在函数void LeafCode (int root,int n)构造过程中,将Ht[p].weight域用做被遍历结点的遍历状态标志。
[函数4.1]
[函数说明2]
函数void Decode (char (作图)buff,int root)的功能是:将前缀编码序列翻译成叶子结点的字符序列,并输出。其中,形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。
[函数4.2]
选项
答案
这是一道要求读者在用哈夫曼算法构造的最优二叉树上进行编码和译码的程序设计题。本题的解答思路如下。 哈夫曼算法构造最优二叉树的过程如下。 ①根据给定的n个权值{W1,W2,W3,……Wn)构成n棵二叉树的集合F={T1,T2,T3,……Tn),其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左、右子树均空。 ②在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和。 ③在F中删除这两棵二叉树,同时将新得到的二叉树加入F中。 ④重复步骤②和③,直到F只含一棵树为止。这棵树便是最优二叉树。 综上所述,最优二叉树是从叶子到根构造起来的,每次都是先确定一棵二叉树的左、右子树,然后再构造出树根结点,因此最优二叉树中只有叶子结点和分支数为2的内部结点。若已知叶子的数目为n,则内部结点数比叶子少1,因此整棵树所需的存储空间规模是确定的,可以采用数组空间来存储最优二叉树。 例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,构造最优二叉树的过程如图3-31所示。 由于算法中对构成左、右子树的二叉树不进行限定,因此用哈夫曼算法构造出的最优二叉树的形态不是惟一的。另外,题干中已给出了存放最优二叉树的结构数组Ht的类型定义,以及存储图3-31所构造出的最优二叉树的结构数组Ht(见表3-12)。 [*] 由于二叉树中的结点最多只有两个分支,若用“0”和“1”分别标识最优二叉树中的左子树分支和右子树分支,那么从根结点开始到叶子结点为止,按经过分支的次序将相应标识依次排列,可得到由“0”和“1”组成的一个序列,称此序列为该叶子结点的前缀编码。例如图3-26所示的最优二叉树叶子结点a、 b、c、d的前缀编码分别是110、0、111、10。 当最优二叉树的构造完成后,每个结点的weight域就可挪作他用,在构造哈夫曼编码的过程中,weight域用做被遍历结点的遍历状态标志。从树根出发,以非递归方式遍历最优二叉树的方法是:先沿着树根的左分支向叶子方向搜索,并用code[]记下所经过的分支的标识,同时用cdlen记录结点的路径长度,一直到叶子结点为止,即可得到当前正在访问的叶子的编码。然后,从该叶子结点回退到其父结点F。若刚才是从F的左子树回到F,则下一次应进入F的右子树进行遍历;若是从F的右子树回到F结点,则下一步应继续向F的父结点回退。 由以上分析可知,对于结点F,遍历过程中最多可能以3种不同的情况经过该结点,因此要为F结点的weight域赋予不同的值进行标识。初始时weight=0,当沿遍历路径到达该结点时其weight域值等于0,则进入其左子树分支进行遍历,并将weight置为1;若沿遍历路径到达该结点时其weight域值等于1,则说明刚从其左子树返回,下面应进入其右子树进行遍历并将weight置为2;若沿遍历路径到达该结点时其 weight域值等于2,则说明刚从其右子树返回,下面应继续向该结点的父结点回退,并将weight置为0。遍历路线如图3-32中箭头方向所示。 [*] 函数void LeafCode (int root,int n)的功能是:采用非递归方法,遍历最优二叉树的全部叶子结点,为所有的叶子结点构造前缀编码。由于在该函数(1)空缺处之后的语句“strcpy (Hc[p],code);”,是进行字符串的复制运算,则需要对源串中的串结束标志进行设置,因此(1)空缺处所填写的语句是“code[cdlen] =‘\0’”或“code[cdlen]=0”。 (2)空缺处是从右子树向父结点回退的处理,因此该空缺处所填入的内容是“Ht[p].parent”。由于每向上层回退一次,结点的路径长度就会减1,因此(3)空缺处所填写的语句是“--cdlen”或其等价形式。 函数void Decode (char (作图)buff,int root)的功能是:将前缀编码序列翻译成叶子结点的字符序列,并输出。译码的过程是:从根出发,若编码序列的当前字符是“0”,则进入左子树分支,否则进入右子树分支,直到到达一个叶子结点时为止,此时叶子所表示的字符就是翻译出的字符。若编码序列还没有结束,则重新从树根出发,重复上述过程,直到将编码序列结束。所以(4)空缺处所填写的语句是“(作图)buff==‘0’”或其等价形式。 由于到达一个叶子结点时,超前读入了一个编码序列中的字符,因此(5)空缺处所填写的语句是“buff--”或其等价形式。
解析
转载请注明原文地址:https://kaotiyun.com/show/B0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
()不是良好编码的原则。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(50)
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(42)
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5,2,4,6,1,3}进行从小到大排序,则需要进行(31)
以下关于数据流图的叙述中,不正确的是()。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(28)
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,其中,___________并不是每个编译器都必需的。
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
随机试题
某人氧耗量为300ml/min,动脉氧含量为20ml/100ml血,肺动脉氧含量为15ml/100ml血,心率为60次/分,他的每搏输出量是多少
丁县(省直接管辖)县医院发生医疗事故争议,需进行医疗事故技术鉴定,按照《医疗事故处理条例》的规定,负责首次医疗事故鉴定工作的组织应当是
按FIDIC合同条件规定,在()之后,业主应将剩余的保留金返还给承包商。
用户用电中,属于变更用电的有()。
甲自然人、乙自然人和丙公司共同投资设立A有限合伙企业(以下简称“A企业”),在各方协商一致的合伙协议中约定:甲出资5万元的货币,乙以劳务作价10万元出资,丙公司以作价8万元的实物出资;甲和乙为普通合伙人,丙为有限合伙人;甲和乙共同执行A企业的合伙事务。丙公
珍珠主要产在珍珠蚌体内,是由珍珠蚌内分泌作用生成的含碳酸钙的矿物珠粒。珍珠的养殖受当地气候、水温和日照等因素的影响。我国是世界淡水珍珠养殖规模最大的国家。珍珠养殖多采用网箱吊养方式,以家禽粪便作为肥料。近年来,各地开始限制珍珠养殖。结合材料,完成15~17
有人认为鸡蛋黄的黄色跟鸡所吃的绿色植物性饲料有关,为了验证这个结论,下面哪种实验方法最可靠?
在林园小区,饲养宠物是被禁止的。林园小区的一些宠物爱好者试图改变这一规定,却失败了,因为林园小区规则变更程序规定:只有获得10%的住户签字的提议,才能提交全体住户投票表决。结果,这些宠物爱好者的提议被大多数住户投票否决了。从以上断定最可能推出:
Judgingfromrecentsurveys,mostexpertsinsleepbehavioragreethatthereisvirtuallyanepidemicofsleepinessinthenatio
WetsuitAwetsuitis【T1】______whowantto【T2】______.Wetsuitsareusuallywornbyswimmers,divers,or【T3】______.Wetsuitsh
最新回复
(
0
)