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

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

admin2009-02-15  59
问题 最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。
选项 A、节点数
B、叶节点数
C、非叶节点数
D、度为2的节点数
答案B
解析 (31)～(33)(31)假设有n个权值{w1,w2,…，wn)，是构造一棵有n个叶子节点的二又树，每个叶子节点带权wi，则其中带权路径长度WPL=∑wili最小的二又树称做最优二又树或哈夫曼树。所以最优二叉树中n表示叶节点。(32)如果只考虑查找成功的情况，则使查找性能达到最佳的判定树是其带权内路径长度之和值PH=∑wili，取最小值的二叉树为最优查找树。其中n为二叉树上节点的个数(即有序表的长度)；li为第i个节点在二叉树上的层次数；节点的权wi=cpi(i=1～n)，其中pi为节点的查找概率，c为某个常量。因此最优查找树中n表示所有节点数。(33)构造哈夫曼树和最优查找树均需对n个关键字进行动态插入。
转载请注明原文地址:https://kaotiyun.com/show/gkxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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