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

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

admin2009-02-15  7
问题 最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度Σ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

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

软考中级

相关试题推荐
随机试题
最新回复(0)