最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σwl最小的树，其中对于最优二叉树，n表示(42)；对于最优查找树，n表示(43)；构造这两种树均(44)。

admin2009-02-15 4

问题最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σwl最小的树，其中对于最优二叉树，n表示(42)；对于最优查找树，n表示(43)；构造这两种树均(44)。

选项 A、需要一张n个关键字的有序表
B、需要对n个关键字进行动态插入
C、需要n个关键字的查找概率表
D、无需任何前提

答案B

解析假设有n个权值{w1，w2,...wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL=∑wili最小的二叉树称做最优二叉树或哈夫曼树。所以最优二叉树中n表示叶结点。
如果只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和值PH=∑wili取最小值的二叉树为最优查找树。其中n为二叉树上结点的个数(即有序表的长度)；li为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1,...,n)，其中pi为结点的查找概率，c为某个常量。因此最优查找树中n表示所有结点数。
构造哈夫曼树的步骤为：根据的n个权值构成n棵二叉树的集合F；在F中选取两棵根结点权最小的作为左右子树构造一棵新的二叉树，且置新二叉树的根结点权为左右子树上根结点权之和；在F中删除这两棵树，现时将新得到的二叉树加入F；重复上两步直至只含一棵树。在构造最优查找树的过程中，有可能出现被选为根的关键字权值比与它相邻关键字权值小。此时应作调整。所以构造哈夫曼树和最优查找树均需对n个关键字进行动态插入。

转载请注明原文地址:https://kaotiyun.com/show/fjxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σwl最小的树，其中对于最优二叉树，n表示(42)；对于最优查找树，n表示(43)；构造这两种树均(44)。

软件设计师上午基础知识考试

软考中级

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

为避免路由信息被重复发送，需要对路由信息包进行编号。如果网络中每台路由器每秒钟传送一次路由信息，为确保路由信息包的编号在1个月内不重复使用，则编号的最短长度应为(31)位。

下面的计算公式错误的是()。

按照()分类，人机系统可分为开环人机系统和闭环人机系统。

对于设备磨损的类型和补偿方法，以下说法正确的是()。

下列各项中，应记入“应付利息”科目的有()。

导游人员应性格多变、活泼，待人热情，富有幽默感。()

群体极化

某公司人力资源部人士指出：由于本公司招聘职位有限，在本次招聘考试中，不可能所有的应聘者都被录用。基于以上哪项可以得出该人士的上述结论?

Look!______!